This problem seems to have various solutions. For example, an ingenious solution utilizing Heavy-Light Decomposition (HLD) has been suggested by a generative AI. Other approaches include using a top tree.
This editorial describes a solution using Static top tree.

Please refer to ABC351-G official editorial for a detailed explanation of a static top tree. Here, let us review the significance of static top tree.

A static top tree is, in a nutshell, “segment-tree-like decomposition of a tree.” More specifically, “a binary tree of depth \(\mathrm{O}(\log N)\) representing the process of splitting a tree.”
A tree is to a static top tree as a sequence is to a segment tree. Let us first recall the relationship between a sequence and a segment tree.
For a sequence \(a\), suppose we are interested in some information \(F(a)\). (An easy example is \(\max\). That is, for a sequence \(a=(1,2,4)\), we are interested in \(F(a) = \max(a) = 4\).) When it comes to designing an algorithm for such a situation, it is effective to consider “a binary tree of depth \(\log |a|\) representing the process of halving a sequence until it has one element” (\(\simeq\) segment tree). Even the direct applications include:

• recomputing \(F(a)\) after updating an element of sequence \(a\) (element-wise update on a segment tree)
• retrieving and updating information about a subarray, such as segment-wise retrieval/update queries on a segment tree
• in case computing \(F(a)\) costs \(\mathrm{O}(|a|)\) space complexity, computing the information on the entire sequence fast (so-called merging technique of a sequence)
  \(\vdots\)

and indirect applications include even more, such as a Merge sort tree. Thus, a segment tree can be regarded as a generic methodology to decompose a sequence toward processing information on a sequence.

If we want an analogous approach for a tree, a static top tree is exactly to a tree what a segment tree is to a sequence.
For a tree \(T\), suppose we are interested in some information \(F(T)\). (Example of \(F(T)\): the weight of a maximum weighted independent set.) Then, just as we did for a sequence, we can consider “a binary tree of depth \(\mathrm{O}(\log N)\) representing the process of decomposing a tree” to support, for example:

• recomputing \(F(T)\) after updating an element of \(T\)
• retrieving and updating information about a subtree
• in case computing \(F(T)\) costs \(\mathrm{O}(\text{\# vertices in }T)\), computing the information on the entire tree fast \(\vdots\)

In other words, various algorithms on a sequence can be realized on a tree too via a static top tree.

The origin of a static top tree is considered a mention by noshi91 on Twitter (currently X) in 2021. As such, this is a relatively modern concept in the history of competitive programming, but due to its versatility and usability, nowadays in 2026 it is widely known to Japanese top players.

To understand the convenience of a static top tree, let us take a look at the previous F problem. While the intended solution adopts ingenious observations, this problem can be viewed as a “vertex-wise update / tree-DP (Dynamic Programming) result retrieval” problem, and this viewpoint immediately allows a static top tree to solve the problem. (Since a tree DP is an algorithm to compute some information \(F(U)\) about subtrees \(U\), it matches the aforementioned situation where we want to “compute the information on the entire tree.”) For more details on how to apply it, please refer to ABC351-G official editorial. Sample code

Let us now consider solving Problem G with a static top tree. Problem G can be considered as “vertex-wise update / tree-DP result retrieval rooted at any vertex” problem. In other words, this problem asks to dynamically update the results of rerooting DP. This can also be processed with a static top tree, but it is not mentioned on the ABC351-G editorial, so we will briefly explain how.
(The following description requires the knowledge of the ABC351-G editorial.) Since rerooting DP is more advanced than an ordinary DP, rerooting on a static top tree seems also confusing, but actually, the principle itself is not very difficult. Let \(v\) be the root of DP. When vertex \(v\) is removed from the tree, if we know the results of DP for the remaining connected components, we can obtain the results of DP rooted at \(v\), too. Here, due to the nature of a static top tree, it turns out that the information about the remaining connected components is stored in \(\mathrm{O}(\log N)\) clusters. Therefore, by appropriately managing and updating the information store on each cluster, a retrieval and update can be processed in \(\mathrm{O}(\log N)\) time, just as an ordinary tree DP.
Note however that, unlike what we did to make tree DP dynamic, where we just needed to maintain “bottom-up accumulation, i.e. the DP values when assuming that the DP root is contained in the boundary-vertex side closer to the root” when merging path clusters, in case of reordering DP, we also need to maintain “top-down accumulation, i.e. the DP values when assuming that the DP root is contained in the boundary-vertex side closer to leaves,” which somewhat complicates implementation.

The complexity is \(\mathrm{O}(N + Q \log N)\), which is fast enough.