Ghassane's blog

By Ghassane, history, 12 months ago, In English

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

  • Vote: I like it
  • +13
  • Vote: I do not like it

| Write comment?
»
12 months ago, # |
  Vote: I like it +20 Vote: I do not like it

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

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it
»
12 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.