Star Trek
Contest: Central-European Olympiad in Informatics, CEOI 2020, Day 1 (IOI, Unofficial Mirror Contest, Unrated)
Difficulty rating: 2600
Tags: *special, combinatorics, dfs and similar, dp, games, graphs, matrices, trees

The United Federation of Planets is an alliance of $$$N$$$ planets, they are indexed from $$$1$$$ to $$$N$$$. Some planets are connected by space tunnels. In a space tunnel, a starship can fly both ways really fast. There are exactly $$$N-1$$$ space tunnels, and we can travel from any planet to any other planet in the Federation using these tunnels.

It's well known that there are $$$D$$$ additional parallel universes. These are exact copies of our universe, they have the same planets and space tunnels. They are indexed from $$$1$$$ to $$$D$$$ (our universe has index $$$0$$$). We denote the planet $$$x$$$ in universe $$$i$$$ by $$$P_x^i$$$. We can travel from one universe to another using dimension portals. For every $$$i$$$ ($$$0\leq i \leq D-1$$$), we will place exactly one portal that allows us to fly from $$$P_{A_i}^i$$$ to $$$P_{B_i}^{i+1}$$$, for some planet indices $$$A_i$$$ and $$$B_i$$$ (i.e. $$$1 \leq A_i, B_i \leq N$$$).

Once all the portals are placed, Starship Batthyány will embark on its maiden voyage. It is currently orbiting around $$$P_1^0$$$. Captain Ágnes and Lieutenant Gábor have decided to play the following game: they choose alternately a destination (a planet) to fly to. This planet can be in the same universe, if a space tunnel goes there, or it can be in another universe, if a portal goes there. Their aim is to visit places where no one has gone before. That's why, once they have visited a planet $$$P_x^i$$$, they never go back there (but they can visit the planet $$$x$$$ in another universe). Captain Ágnes chooses the first destination (then Gábor, then Ágnes etc.). If somebody can't choose a planet where they have not been before in his/her turn, he/she loses.

Captain Ágnes and Lieutenant Gábor are both very clever: they know the locations of all tunnels and portals, and they both play optimally. For how many different placements of portals does Captain Ágnes win the game? Two placements are different if there is an index $$$i$$$ ($$$0\leq i \leq D-1$$$), where the $$$i$$$th portal connects different pairs of planets in the two placements (i.e $$$A_i$$$ or $$$B_i$$$ differs).

This number can be very big, so we are interested in it modulo $$$10^9+7$$$.

Input format:
The first line contains two space-separated integers, $$$N$$$ ($$$1\leq N \leq 10^{5}$$$) – the number of planets and $$$D$$$ ($$$1 \leq D \leq 10^{18}$$$) – the number of additional parallel universes.  Each of the next $$$N-1$$$ lines contains two space-separated integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq N$$$), denoting that $$$P_u^i$$$ and $$$P_v^i$$$ are connected by a space tunnel for all $$$i$$$ ($$$0 \leq i \leq D$$$).

Output format:
You should print a single integer, the number of possible placements of portals where Captain Ágnes wins modulo $$$10^9+7$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Scoring:
$$$ \begin{array}{|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & 0 & \text{samples}\\ \hline 2 & 7 & N=2 \\ \hline 3 & 8 & N \leq 100 \: \text{and} \: D = 1 \\ \hline 4 & 15 & N \leq 1000 \: \text{and} \: D = 1\\ \hline 5 & 15 & D=1 \\ \hline 6 & 20 & N \leq 1000 \: \text{and} \: D \leq 10^5\\ \hline 7 & 20 & D \leq 10^5\\ \hline 8 & 15 & \text{no additional constraints}\\ \hline \end{array} $$$

There is only 1 portal and $$$3 \cdot 3 = 9$$$ different placements.  The following 4 placements are when the Captain wins.

Example input:
3 1
1 2
2 3

Example output:
4

Editorial:
Subtask 2
$$$N = 2$$$
The Captain always wins.  A possible winning strategy: she uses only tunnels.  In this way, Gábor is forced to use only portals. After using a portal they will be in a new universe where the Captain can use the tunnel. So Captain can always move after Gábor, but there is a point where Gábor can't move. That's why Gábor can't win.  The answer is the total number of possible placements: $$$4^D$$$. it can be computed in $$$O(logD)$$$ operations via fast exponentiation.
This subtask can be solved in $$$O(logD)$$$
Winning-Losing states
Lets play this game in a rooted tree where the first player moves from the root $$$r$$$.  Let's call a node L(osing)-state if the player moving from there can't win. Call that node W(inning)-state otherwise.  The players can only increase the distance from $$$r$$$; that's why every leaf is an L-state.  A node is W-state iff it has an L-state child.  The root's state can be calculated in $$$O(N)$$$ operation with dfs if the size of the tree is $$$N$$$.
$$$\mathbf{L}$$$ : set of nodes that are L-states as the root  $$$\mathbf{W}$$$ : set of nodes that are W-states as the root
Subtask 3
$$$N \leq 100, D = 1$$$
We test all possible placements. A placement will give us a tree of size $$$2N$$$ rooted at $$$P_1^0$$$. For all possibility we check the root's state. There are $$$O(N^2)$$$ different placements and it takes $$$O(N)$$$ operation to check a single one.
This subtask can be solved in $$$O(N^3)$$$
Critical L-state
It's clear that we have $$$D+1$$$ trees of the same structure and they are connected into a bigger tree. This big tree is rooted at $$$P_1^0$$$, but all small trees have a root-like node in the big tree ($$$P_1^0$$$ in the first universe and $$$P_{B_{i-1}}^i$$$ in the $$$i$$$th parallel universe).  We will work now with the small tree of size $$$N$$$.
Let's root this tree in an arbitrary node $$$r$$$. Let's call this tree $$$tree_r$$$. Let's denote the parent of node $$$c$$$ by $$$P(c)$$$.  Connecting a new node $$$y$$$ with a given state to a node $$$x$$$ (of the original tree) may change some states.
It can be proved that the state of $$$x$$$ changes iff $$$x$$$ and $$$y$$$ are both L-states. In this case, $$$x$$$ will become W-state. This may cause further changes in the tree:  If $$$P(x)$$$ has only one L-state child ($$$x$$$), then its state will also change from W to L.  If $$$P(P(x))$$$ is L-state, then its state will also change from L to W.  $$$P(P(P(x)))$$$ will act like $$$P(x)$$$. This wave of change will stop at some node $$$z$$$, where $$$z$$$ will be the uppermost node whose state changed. We call $$$x$$$ a critical L-state if $$$z = r$$$.
$$$\mathbf{C_r}$$$ : set of nodes that are critical L-states when $$$r$$$ is the root.  $$$\mathbf{C_r}$$$ can be computed in $$$O(N)$$$ time for a given $$$r$$$ using dfs.
Subtask 4
$$$N \leq 1000$$$ and $$$D = 1$$$
We should connect 2 uniform trees of size N. The first tree is rooted at index 1 (the starting node).  If the root of $$$tree_1$$$ is W-state it will only change it's state if we connect a L-state to one of its critical node. That's why; the answer is $$$N*|W| + (N-|C_1|)*|L|$$$.  If the root of $$$tree_1$$$ is L-state it will only change it's state if we connect a L-state to one of its critical node. That's why; the answer is $$$|C_1|*|L|$$$.
Calculating $$$|C_1|$$$ requires $$$O(N)$$$ time while calculating $$$|L|$$$ and $$$|W|$$$ requires $$$O(N^2)$$$.
This subtask can be solved in $$$O(N^2)$$$
Subtask 5
$$$D = 1$$$
We must calculate $$$|L|$$$ and $$$|W|$$$ faster than in subtask 4.  Let's say the original tree is rooted in $$$v$$$ and we want to reroot this tree in one of its neighbors, $$$u$$$. We can see that only $$$v$$$'s and $$$u$$$'s state may change while doing this. The new states can be computed in constant time if we know the number of L-state children for every node (which can be computed by a single dfs).  We can reroot the tree easily in all nodes with one dfs.
This subtask can be solved in $$$O(N)$$$
Subtask 6
$$$N \leq 1000, D \leq 10^5$$$
For all possible roots $$$r$$$ we calculate $$$|C_r|$$$. This takes $$$O(N^2)$$$ time.  Let us define $$$L_D$$$ as the number of ways to
• choose a starting node, and
• install portals,
By definition, the W/L status of the starting node $$$v$$$ will change if and only if we add an edge from a node in $$$\mathbf{C_v}$$$ leading to an L state. Therefore, the number of ways to add all $$$D$$$ portals in a way that changes the status of the starting node is $$$$$$\left|\mathbf{C_v}\right| L_{D-1}.$$$$$$
We can now calculate $$$(L_D)_v$$$, the number of ways to make $$$v$$$ a losing root with respect to the remaining $$$D$$$ (plus one) universes: if $$$v$$$ is W, then we have to add the remaining portals in a way that changes the status of $$$v$$$; if $$$v$$$ is L, then we have to add them in any other way. Hence, $$$$$$(L_D)_v = \begin{cases} \left|\mathbf{C_v}\right| L_{D-1}& \textit{if } v\in W\\ N^{2D} - \left|\mathbf{C_v}\right| L_{D-1} & \textit{if }v\in L. \end{cases}$$$$$$ Clearly, $$$$$$  L_D = \sum_{v} (L_D)_v\\   = \sum_{v\in W}\left|\mathbf{C_v}\right| L_{D-1} + \sum_{v\in L}(N^{2D} - \left|\mathbf{C_v}\right| L_{D-1})\\   = \left|\mathbf{L}\right|N^{2D} + \left(\sum_{v\in W}\left|\mathbf{C_v}\right| - \sum_{v\in L}\left|\mathbf{C_v}\right|\right) L_{D-1}\\   = \left|\mathbf{L}\right|N^{2D} + E \cdot L_{D-1} \textit{where }E\triangleq \left(\sum_{v\in W}\left|\mathbf{C_v}\right| - \sum_{v\in L}\left|\mathbf{C_v}\right|\right). $$$$$$
In the last universe, we have $$$L_0 = |\mathbf{L}|$$$, by definition.
The answer to the original question is the number of ways to make the starting node $$$v_1$$$ into W, which is given by $$$$$$\textit{Solution} = N^{2D} - (L_D)_{v_1}.$$$$$$
We can calculate this value in $$$O(D)$$$ time using dynamic programming.
This subtask can be solved in $$$O(N^2+D)$$$
Subtask 7
$$$D \leq 10^5$$$
We must calculate $$$|C_r|$$$ for all $$$r$$$ faster than in subtask 6.  We can use the idea described in subtask 5 (when calculating $$$|L|$$$ and $$$|W|$$$ fast).
This subtask can be solved in $$$O(N+D)$$$
Subtask 8
Original constraints.
Solution 1:
This subtask can be solved like subtask 6 but we calculate $$$L_1$$$, $$$L_2$$$, $$$L_4$$$, $$$L_8$$$ ... (i.e. $$$L_{2^i}$$$), where we can compute $$$L_{2^i}$$$ from $$$L_{2^{i-1}}$$$. With the bit-representation of $$$D-1$$$ we can calculate $$$L_{D-1}$$$ in $$$O(logD)$$$ operations.
This subtask can be solved in $$$O(N+logD)$$$
Solution 2: Closed Form
To solve the last subtask, we need to calculate $$$L_{D-1}$$$ in sub-linear time. To do this, we can solve the recurrence relation, which yields the closed form $$$$$$L_{D-1} = |L| \frac{N^{2D} - E^{D}}{N^2 - E}.$$$$$$
This could be calculated via $$$O(\log D)$$$ exponentiation and modular inverse, but this is not necessary: we can easily eliminate the division by writing $$$a \triangleq N^2$$$ and $$$b \triangleq E$$$, and using the well-known identity for $$$(a^D - b^D)$$$ to get $$$$$$L_X = |L| \sum_{k=0}^{X} a^{k} b^{X-k}.$$$$$$ This can be calculated in $$$O(\log D)$$$ time, by repeatedly halving: $$$$$$  L_{2X+1} = (b^{X+1} + a^{X+1}) L_{X}\\  L_{2X} = b^{X+1} L_{X-1} + |L| a^X b^X + a^{X+1} L_{X-1}. $$$$$$