Official

L - Lulu, the Magician Editorial by Lulusphere


For each query \(2\ u\ v\), we need to compute

\[ \sum_{x\in P(u,v)}\sum_{r=1}^{N} W_r d(r,x). \]

Let

\[ F(x)=\sum_{r=1}^{N} W_r d(r,x). \]

Then the query asks for the sum of \(F(x)\) over all vertices \(x\) on the path \(P(u,v)\).

First, suppose that all values \(W_r\) are fixed. We can compute all values \(F(x)\) by rerooting DP.

Root the tree at vertex \(1\). Let \(cnt_v\) be the sum of \(W_r\) over all vertices \(r\) in the subtree of \(v\), and let

\[ down_v=\sum_{r\in subtree(v)} W_r d(v,r). \]

These values can be computed by a bottom-up tree DP. Since

\[ F(1)=down_1, \]

we can compute the remaining values by rerooting. Suppose we move the root from a vertex \(p\) to its child \(c\). Vertices inside the subtree of \(c\) become closer by \(1\), while all other vertices become farther by \(1\). If

\[ T=\sum_{r=1}^{N} W_r, \]

then

\[ F(c)=F(p)+T-2cnt_c. \]

After computing all \(F(x)\), store the prefix sum of \(F\) values on the path from the root to each vertex. Then, if \(l=\operatorname{lca}(u,v)\), the path sum of \(F\) over \(P(u,v)\) is

\[ pref_u+pref_v-2pref_l+F(l). \]

Thus, if there were no updates, each query could be answered quickly after one rerooting DP.

Now consider the updates. Recomputing all values \(F(x)\) after every update is too expensive, so we process updates in buckets.

At the beginning of each bucket, rebuild all static information using the current values of \(W_r\). Updates inside the current bucket are not reflected in this rebuilt information yet.

For a query \(2\ u\ v\), the answer is divided into two parts:

\[ \text{answer} = \text{rebuilt path sum} + \text{contribution of pending updates}. \]

The rebuilt path sum is computed using the prefix sums described above.

Now consider one pending update. Suppose the value of vertex \(r\) was increased by \(w\). Its additional contribution to the query \(2\ u\ v\) is

\[ w\sum_{x\in P(u,v)} d(r,x). \]

Therefore, it remains to compute

\[ \sum_{x\in P(u,v)} d(r,x) \]

efficiently.

Let \(y\) be the vertex on \(P(u,v)\) closest to \(r\). Define

\[ a=d(u,y),\quad b=d(v,y),\quad h=d(r,y). \]

For every \(x\in P(u,v)\),

\[ d(r,x)=h+d(y,x). \]

The path has \(a+b+1\) vertices, so the value \(h\) is added \(a+b+1\) times. The remaining distances form two arithmetic sums. Hence,

\[ \sum_{x\in P(u,v)} d(r,x) = h(a+b+1)+\frac{a(a+1)}2+\frac{b(b+1)}2. \]

It remains to obtain \(a,b,h\). Let

\[ A=d(u,v),\quad B=d(r,u),\quad C=d(r,v). \]

Then

\[ A=a+b,\quad B=h+a,\quad C=h+b. \]

Solving these equations gives

\[ a=\frac{A+B-C}{2},\quad b=\frac{A+C-B}{2},\quad h=\frac{B+C-A}{2}. \]

All distances can be computed using LCA, so the contribution of one pending update can be computed in \(O(\log N)\) time, or \(O(1)\) time after LCA preprocessing depending on the implementation.

Now we summarize the algorithm.

At the beginning of each bucket, rebuild all values \(F(x)\) using rerooting DP, and rebuild the prefix sums of \(F\) from the root. When a query is given, first compute the rebuilt path sum. Then iterate over all pending updates in the current bucket and add their contributions using the formula above.

Let the bucket size be \(B\). Each query checks at most \(B\) pending updates, while rebuilding is done once per bucket. Therefore, the total time complexity is

\[ O(BQ+NQ/B) \]

up to the cost of LCA queries. By taking \(B=\Theta(\sqrt N)\) or choosing an appropriate value depending on the constraints, this is fast enough.