Hello everyone, I have been stuck on this problem for a while, can anyone please give me an idea to solve this problem?
The statement: Given a tree of $$$n$$$ nodes and weighted edges (numbered from $$$1$$$ to $$$n-1$$$) and $$$q$$$ queries of 2 types:
Type 1: gives $$$k$$$ distinct nodes $$$u_1,u_2,...,u_k$$$ and a node $$$v$$$ different from the given nodes and asks for the maximum sum of edge weights of a path coming from node $$$v$$$ to another node that doesn't go through any of the node $$$u_1,u_2,...u_k$$$.
Type 2: updates the weight of the $$$i^{th}$$$ edge to $$$w$$$.
$$$n,q\leq 2\cdot 10^5,w\leq 10^9$$$, the sum of $$$k$$$ of all queries doesnt exceed $$$2\cdot 10^5$$$.
original statement (in Vietnamese): https://lqdoj.edu.vn/problem/lqdojcontest15bai5
I've tried constructing virtual trees for each type 1 query but couldn't handle the nodes not included in the query, also tried using centroid decomposition, each node on the centroid tree storing a segment tree for Euler tour but couldn't do the edge updates efficiently.
Thank you for your attention.
https://codeforces.me/blog/entry/123160
See the 2nd solution to problem E here. You can calculate node distances dynamically by maintaining a second segment tree on the Euler tour which maintains for each node its distance to the root. The type 2 update for this problem can be done by first updating this second segment tree, then recalculating the diameters for $$$O(\log n)$$$ nodes each query for the main segment tree.
Thank you so much for sending me the original problem!!!!
Well it's not exactly the same. It doesn't have update queries
at least i can get some idea after reading the solution