First subtask can be solved by checking for each pair ~(x, y)~ if the condition holds.

In the second subtask, the tree is a chain. We will describe a solution using divide-and-conquer method. Let ~f(l, r)~ be the number of valid pairs such that ~l \le x < y \le r~, and let ~m = \left\lfloor \frac{l+r}{2} \right\rfloor~. If we calculate the number of valid pairs ~(x, y)~ such that ~1 \le x \le m < y \le r~, i.e. the pairs whose path goes through the middle edge ~m \leftrightarrow m+1~, we can calculate ~f(l, r)~ as the sum of that number, ~f(l, m)~, and ~f(m+1, r)~.

Let ~d(x)~ be the distance between nodes ~x~ and ~m~, and ~v(x)~ be the maximum weight on the path from ~x~ to ~m~ (we can take ~v(m)~ to be ~-\infty~). Pair ~(x, y)~ is valid if ~\max(v(x), v(y)) - (d(x)+d(y)) \ge k~. If we assume that ~v(x) \le v(y)~, the condition is ~v(y) - (d(x)+d(y)) \ge k \iff d(x) \le v(y)-d(y)-k~.

We can sort nodes ~l, \dots, r~ ascending by ~v(x)~, and go through them in that order. We will use a Fenwick tree, where we will store the counts of ~d(x)~ for processed nodes. Let ~y~ be the current node. We will first query in our Fenwick tree the sum of the prefix ~v(y)-d(y)-k~, and then add ~1~ to the position ~d(y)~.

By doing this, we have counted all valid pairs, but also all pairs that are in either the left or the right half that fulfill the condition, which we don't want. So, we will repeat the procedure with nodes ~l, \dots, m~, and with nodes ~m+1, \dots, r~, and subtract from the result.

The solution for all points is very similar. Now ~m~ will be the centroid of the current component. Functions ~d~ and ~v~ are defined in the same way. Instead of two halves, we now have some number of subtrees. We first calculate the result with all nodes, and then subtract results for each subtree. Finally, we recursively call ~f~ for all subtrees.

The complexity is ~\mathcal O(n \log^2 n)~.