Temotoloraia's blog

By Temotoloraia, history, 4 months ago, In English

Can anyone solve this? Problem G

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

»
4 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

If my understanding is correct the problem statement reduces to (assuming we can replace each node with an edge of the same weight)- Given a tree, find its diameter and there are updates that increase the weight of some edges? In that case, I don't understand why mod 1e9+7

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

I understand the statement as follows: You are given a tree with weights on edges ($$$b$$$) and vertices ($$$a$$$), calculate the sum over all pairs of vertices $$$\sum_i \sum_j \texttt{dist}(i, j) \cdot a_i \cdot a_j$$$. Queries may modify the weight of edges and vertices, and we have to report the value of the sum after each query.

If it is okay, then it can be solved with centroid decomposition in $$$\mathcal{O}((n + q) \log^2 n)$$$. When we modify the weight of a vertex $$$i$$$ we want to answer the sum $$$a_i \cdot \sum_i \texttt{dist}(i, j) \cdot a_j$$$, when we modify the weight of an edge $$$b_i$$$, we change the answer by a sum over $$$a_i$$$ in its subtree multiplied by the rest of weights. The latter can be done with one segment tree.

So we have to quickly answer, for a vertex, the sum of distances (multiplied by some coefficient) to all the other vertices. We keep the centroid decomposition, and for each subtree, in the decomposition, we keep a segment tree with distances from the root to the vertex, multiplied by the weight of the vertex. This requires some formulas, but we can update the weight of an edge (update on interval), the weight of a vertex (just one path to change), and query for the sum paths, which we need to answer when we change the weight of a vertex.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can solve this problem here