[1]#1
Author: | Anton Trygub |
Developer: | Maksym Zub |
Editorialist: | Stanislav Bezkorovainyi |
It is easy to notice that if a vertex is an ancestor of vertex , then vertex is a descendant of vertex . And thus if we can move the chip from to vertex , then we can also move the chip from vertex to vertex .
Now let's build a new undirected graph , that consists of vertices. In graph two vertices and are connected with an edge if and only if is an ancestor of or is an ancestor in the original tree.
Obviously, playing the game on the tree is equivalent to playing the game on this graph, just with a small change. In the tree we could move the chip from vertex to vertex if and only if was either ancestor of or descendant of . In graph we can move the chip from vertex to vertex iff and are connected with an edge.
Now let's find a maximum matching of the graph. More information about matchings of graphs and their properties can be read on page http://bit.ly/seerc-2019-matching. But I'll provide a few definitions here:
A matching in a graph is a set of edges without common vertices.
A maximum matching is a matching that contains the largest possible number of edges.
A perfect matching is a matching which matches all vertices of the graph.
Claim. If a maximum matching of graph is a perfect matching, then the second player wins. Otherwise, the first one wins.
Proof.
At first, let's proof that if the matching is perfect, then the second player wins. Let's suppose that set of edges is a perfect matching of graph . As we all know, every edge in an undirected graph can be defined by a pair a numbers — pair of vertices that the edge connects. So, actually, by building a perfect matching we divide vertices into \frac{n}{2} pairs of vertices (v_1, u_1), (v_2, u_2), \ldots, (v_{\frac{n}{2}}, u_{\frac{n}{2}}), such that every vertex from graph belongs to exactly one pair.
Let's see how Bob has to play in order to win this game. Let's say that on the first turn Alice chooses to put the chip on vertex . Since the matching is perfect, vertex belongs to some pair. Let it be . Then Bob chooses to move the chip to vertex . So now, all the vertices from the pair are used, so the players won't be able to the chip on neither vertex nor on vertex . Now Alice has to put the chip in a vertex that belongs to another pair. And so on.
In general, if on turn Alice decides to put the chip on vertex a_k, Bob finds the pair (a_k, b_k) to which a_k belongs and moves the chip to vertex b_k. Since we know that wherever Alice decides to put the chip Bob will still have the next vertex to go, it is obvious that Alice will loose, and thus Bob will win.
Now let's proof that if the maximum matching is not perfect, then Alice can always win.
Let be a maximum matching of graph . is a set of edges and thus, it can be also represented as a set of pairs of vertices (v_1, u_1), (v_2, u_2), \ldots, (v_m, u_m), where is the size of . Since is not a perfect matching there is at least one vertex that does not belong to any of the pairs.
At the first turn, Alice should choose any vertex that does not belong to any of the pairs. At the second turn, Bob will either have no vertices to go (and thus lose the game) or the only vertex he can go will belong to one of the pairs in matching . Now the game is just the same as in the previous case, but now Bob is the first one to put the chip on a vertex that belongs to one of the pairs of the matching and because of that Bob will definitely lose.
But wait a second... In the previous case every vertex belonged to exactly one pair. Since in this case is not perfect, there can be lots of vertices that do not belong to any of the pairs. Why can't Bob move to a vertex that does not belong to any of the pairs, just like Alice did in the first turn?
Let's suppose that Bob can do so. There are two possible cases:
Bob decides to move the chip on a vertex that does not belong to any of the pairs on the second turn. If he can do so, the previous vertex and the new one can be matched, and thus is not a maximum matching. Contradiction.
Bob decides to move the chip on a vertex that does not belong to any of the pair on the -th turn. Let vertices v_1, v_2, v_3, \ldots, v_{k-1}, v_k be vertices on which the chip was placed on turns , , , ..., k-1 and respectively. Since Alice plays the game just like Bob in the case when was perfect, k-1 unordered pairs (v_2, v_3), (v_4, v_5), \ldots, (v_{k-2}, v_{k-1}) belong to . Whats more, there are edges between pairs of vertices (v_1, v_2), (v_3, v_4), \ldots (v_{k-1}, v_k). We can delete the k-1 pairs from mentioned earlier and insert pairs (v_1, v_2), (v_3, v_4), \ldots, (v_{k-1}, v_k). By doing that we create a new matching E_2 that has size greater than that of matching . That means that is not a maximum matching. Contradiction.
So now we know how to solve the problem if know the size of maximum matching of the tree. But how to find it? You may try to use standard approaches for finding maximum matching, but these are very likely to get "Time limit exceeded" verdict. Here is author's approach that works in that capitalizes on the way how graph was built.
We will use recursion + dynamic programming on the initial tree. Let's define dp_v as the minimal number of vertices that are left unmatched if we try to match all the vertices in the subtree of vertex .
Let's say that we want to calculate dp_v for some vertex . Now there are two possible senarios:
Vertex is a leaf. Obviously, dp_v = 1.
Vertex is not a leaf, so it has one or more direct descendants. Let's denote the direct descendants of vertex as d_1, d_2, \ldots, d_k. At first, let's calculate values of dp_{d_1}, dp_{d_2}, \ldots, dp_{d_k}. Let's define D = \sum_{i=1}^{k}dp_{d_i}. If is greater than , then we can match vertex with one of it's unmatched descendants and get dp_v = D - 1. Otherwise, all of the descendants of vertex were matched, so obviously vertex has no vertex to match with, so dp_v = 1. We get the formula:
If dp_1 = 0, then we can match all of the vertices and thus the maximum matching is perfect, which means Bob will win. Otherwise, Alice will win.