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 ~i~, we can find the number of indices ~j~ such that the sum of all edges between nodes ~i~ to ~j~ equals ~K~, and add ~1~ to the nodes ~i, i+1, \dots, j~.

Time Complexity: ~\mathcal O(N^3)~

For the second subtask, we can root the tree at ~i~ for ~i = 1, 2, \dots, N~, and then perform a DFS from the root to every other node. If the path from node ~i~ to node ~j~ has sum ~K~, then we can add ~1~ to node ~j~.

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

Time Complexity: ~\mathcal O(N^2)~

There is no intended solution for subtask 3.

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

Counting the number of paths of length ~K~ that pass through node ~C~ is a classical problem. For every other node ~i \ne C~ in ~C~'s subtree, we can count the number of nodes ~j~ that come before ~i~ in the Euler tour of the tree such that ~D[i] + D[j] = K~, and ~\operatorname{LCA}(i, j) = C~. Let this number be ~x~. Then we have to add ~x~ to the path from ~C~ to ~i~. This can be done in constant time.

We then repeat this process, but with a slight modification. For every other node ~i \ne C~ in ~C~'s subtree, we can count the number of nodes ~k~ that come after ~i~ in the Euler tour of the tree such that ~D[i] + D[k] = K~, and ~\operatorname{LCA}(i, k) = C~. Let this number be ~x~. Then we have to add ~x~ to the path from ~C~ to ~i~. This can be done in constant time.

Time Complexity: ~\mathcal O(N \log N)~