## Editorial for COCI '20 Contest 4 #4 Janjetina

**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.**

First subtask can be solved by checking for each pair if the condition holds.

In the second subtask, the tree is a chain. We will describe a solution using divide-and-conquer method. Let be the number of valid pairs such that , and let . If we calculate the number of valid pairs such that , i.e. the pairs whose path goes through the middle edge , we can calculate as the sum of that number, , and .

Let be the distance between nodes and , and be the maximum weight on the path from to (we can take to be ). Pair is valid if . If we assume that , the condition is .

We can sort nodes ascending by , and go through them in that order. We will use a *Fenwick tree*, where we will store the counts of for processed nodes. Let be the current node. We will first query in our Fenwick tree the sum of the prefix , and then add to the position .

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 , and with nodes , and subtract from the result.

The solution for all points is very similar. Now will be the *centroid* of the current component. Functions and 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 for all subtrees.

The complexity is .

## Comments