### Ghassane's blog

By Ghassane, history, 14 months ago,

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

• +13

| Write comment?
 » 14 months ago, # |   +20 G: use ETT + Segment Tree (Fenwick Tree usable also). Make sure to use LCA with time complexity $O(\log n)$ or lower.
•  » » 14 months ago, # ^ |   0 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.
 » 14 months ago, # |   +3 this blog may help https://mirror.codeforces.com/blog/entry/78564
 » 14 months ago, # |   +5 How to solve problem D. I am confused about the statements.
 » 14 months ago, # |   +3 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.