I could not find the usual discussion post about the most recent atcoder contest, so I'm posting here. How to solve problem G?

# | User | Rating |
---|---|---|

1 | tourist | 3690 |

2 | jiangly | 3647 |

3 | Benq | 3581 |

4 | orzdevinwang | 3570 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | Radewoosh | 3509 |

8 | ecnerwala | 3486 |

9 | jqdai0815 | 3474 |

10 | gyh20 | 3447 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 173 |

2 | awoo | 164 |

3 | adamant | 163 |

4 | TheScrasse | 159 |

5 | nor | 157 |

6 | maroonrk | 156 |

7 | -is-this-fft- | 152 |

8 | Petr | 146 |

8 | orz | 146 |

10 | pajenegod | 145 |

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/20/2024 12:28:45 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

G: use ETT + Segment Tree (Fenwick Tree usable also). Make sure to use LCA with time complexity $$$O(\log n)$$$ or lower.

Ok thanks! I knew about ETT but not how to use it for path sum queries. Actually this exact task is explained by SecondThread in his tree basics video (in case someone is interested), i wish I knew it earlier.

this blog may help https://mirror.codeforces.com/blog/entry/78564

How to solve problem D. I am confused about the statements.

It is bad, that this problem is quite implementation heavy and is very common, and I had the solution for almost this problem on one archive.

There are two ways to do it.

$$$A$$$. Let's precompute sum on pathes from $$$v$$$ to $$$root$$$. Then answer for $$$v$$$ and $$$u$$$ is $$$sum[v] + sum[u] - 2 \cdot sum[lca(v, u)]$$$, where $$$lca(v, u)$$$ is the least common ansestor of $$$v$$$ and $$$u$$$, which can be calculated using binary lifting. How to answer queries? Well, the query here means "add $$$x$$$ to $$$sum$$$ of all vertices in subtree of vertice $$$v$$$". How we can add value on subtree quickly? There is a technique, which uses some properties of $$$dfs$$$. Let's simply run dfs and every time we visit a vertice or return to it from child, append it to some global array $$$dfsarr$$$. Look at some vertice $$$v$$$: it appears in array several times, and the segment from $$$leftmost[v]$$$ to $$$rightmost[v]$$$ contains all vertices in subtree of this vertice (just draw it, and you will see). Now, instead of working with original array of numbers on vertices, we use that $$$dfsarr$$$. All remaining is range sum: we can use fenwick tree of segment tree.

$$$B$$$. Way for not smart but strong coders. You can use heavy-light decomposition. It is not easy structure and a bit overkill, but I submitted this, because I already had it prewritten.