Editorial for An Animal Contest 6 P6 - Generous Grizzly Gift Giving
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