## Editorial for An Animal Contest 6 P6 - Generous Grizzly Gift Giving

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

First of all, root the tree at city . Denote the size of city 's subtree as , denote the depth of city as , and denote the lowest common ancestor of cities and as .

**Observation 1:** The number of gifts from city that a grizzly receives is equal to the number of cities , such that .

With this observation, we can begin tackling subtask 1. We will find the confusion value of each grizzly by performing a DFS on the tree and dynamically maintaining the inversions using a sparse 2D Fenwick tree. First of all, when we are at city , all of the gifts received should be from city . So initially, we should have inversions, and our Fenwick tree should be updated with the value at . When we enter a child city from parent city , exactly of the gifts from city should be converted to gifts from city . However, since a grizzly does not receive a gift from himself, we also gain a gift from city and lose a gift from city . Update the inversion count and the Fenwick tree accordingly. When we exit city and return to its parent , we simply reverse the changes that we made. In this way, when we are at a particular city , the inversion count and Fenwick tree are representative of the gifts that grizzly will receive. So, when we sum up the inversion counts across all cities, we have our answer.

To solve subtask 2, we have to perform the same DFS traversal as in subtask 1, but we also need some additional information. More specifically, for each query, the answer is the total number of inversions minus any inversions that a particular grizzly is involved in. A grizzly can be involved in an inversion in two ways: first, the inversions formed by the gifts that grizzly receives, and second, the inversions formed by the gifts that grizzly gives. We will preprocess the answer for all using the DFS. The first case can be handled by saving the inversion count at all cities . The second case is quite a bit harder, since we cannot find the number of inversions for each city one at a time. Instead, we will consider the inversions caused by each gift and update all of the relevant grizzlies. Note that a gift from city can only be given to a grizzly that comes from city 's subtree. Suppose we are at city in the DFS and we want to find all of the inversions caused by the gift from city . For simplicity, denote the state of the Fenwick tree at city as state . First of all, let's handle the case when a gift from city is given to grizzly . We can simply query state of the Fenwick tree using the point and then update 's subtree excluding itself. For all of 's children , consider that the gift is given to a grizzly from 's subtree. We want to query the point over all states in 's subtree, and then update 's subtree excluding 's subtree. However, naively implementing this would be too slow. We need a better solution.

Note that each time we update the Fenwick tree at a city , the update affects the states of all the cities in 's subtree and none others. In other words, the update affects exactly cities. So, what we will do is maintain a second Fenwick tree. In this Fenwick tree, when we perform an update in the first Fenwick tree, we will also update the second Fenwick tree to use multiplied by the update value in the first Fenwick tree. When we need to query over all states in 's subtree, we can use the two Fenwick trees in combination. First of all, query the inversions in the first Fenwick tree—these will affect all of the states in the subtree, so we will use this value multiplied by . Then, subtract the inversions in the second Fenwick tree from *before* we enter city . Finally, add the inversions in the second Fenwick tree from *after* we finish our DFS on city .

To solve subtask 3, we will do the same process as in subtask 2. We will find the total number of inversions and subtract the inversions which grizzlies and are involved in. However, we must also consider that grizzly and may be involved in the same inversion. As a result, we have subtracted some inversions twice, and therefore, we must add the inversions back. Grizzly and can be involved in the same inversion in two ways: first, grizzly gives a gift to grizzly that forms an inversion with another gift that grizzly received (or vice versa, gives a gift to ), and second, grizzly and each give a gift to a third grizzly , and the gifts that they give form an inversion. Obviously, we can not preprocess the answer for all , so instead, we will perform offline processing for only the pairs of grizzlies that are queried. The first case can be handled by simply querying the gift from at both and . The second case is not quite so simple, and it requires additional observation.

**Observation 2:** For any three cities , if , then . Otherwise, at least one of or is equal to .

This implies that if grizzly and each give a gift to a third grizzly , and the gifts that they give form an inversion, then one of the gifts is from city . The other is along the path from to or the path from to . Another smaller observation is that the set of gifts that a grizzly gives is the same as the set of gifts that a grizzly receives. Therefore, while we are performing our DFS we will reuse our first Fenwick tree, but this time it represents the set of gifts that the current grizzly *gives*. When we want the inversions that and cause for the second case, we query the inversions of the gift from at both and using the first Fenwick tree. However, we may have counted some inversions with gifts from a city , such that . Therefore, we subtract the number of inverted gifts twice when we are at , and we are done.

## Comments