## Editorial for DMPG '19 G5 - Hunting the White Whale

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

This problem was greatly inspired by IOI '11 B - Race. Also, Re:Zero season 2 hype!!!

For the first subtask, the tree forms a chain. Thus for each , we can find the number of indices such that the sum of all edges between nodes to equals , and add to the nodes .

Time Complexity:

For the second subtask, we can root the tree at for , and then perform a DFS from the root to every other node. If the path from node to node has sum , then we can add to node .

The update can be achieved by adding to node , and then propagating this change upwards to the root in a single DFS performed at the end.

Time Complexity:

There is no intended solution for subtask 3.

For the final subtask, we can perform centroid decomposition. Consider the tree with centroid . We want to update all paths with LCA . We reroot the tree such that is the root. For every node in the subtree, let denote the sum of the values from to .

Counting the number of paths of length that pass through node is a classical problem. For every other node in 's subtree, we can count the number of nodes that come before in the Euler tour of the tree such that , and . Let this number be . Then we have to add to the path from to . This can be done in constant time.

We then repeat this process, but with a slight modification. For every other node in 's subtree, we can count the number of nodes that come after in the Euler tour of the tree such that , and . Let this number be . Then we have to add to the path from to . This can be done in constant time.

Time Complexity: