Solution for Codeforces Round 1073 (Div. 2), F

Preface

这是一篇英文题解。This is an English solution.

Solution

Consider the necessary and sufficient condition for $P(T)=v$:

• Edge $(v,n)$ exists in $T$;
• Let $n$ be the root of $T$. Then, $n-1$ is in the subtree of $v$.

This is because every vertex $u(u< n-1,u\ \text{is not an ancestor of}\ n-1)$ is removed before $n-1$.

If $n-1$ and $n$ are in the same tree, when $v$ is both an ancestor of $n-1$ (including $v$ itself) and a child of $n$, all $n^{k-2}\prod\limits^k_{i=1}s_i$ ways are valid. Otherwise, the answer is $0$.

If $n-1$ and $n$ are in different connected components, calculate answer for each node $v$. When $v$ and $n$ are not connected by an edge, just add the edge $(v,n)$. After that, we could only consider the second constraint. Here’s the critical part: now the answer is $\frac{s_v}{S}n^{k-2}\prod\limits_{i=1}^ks_i$, where $s_v$ is the size of the subtree of $v$, and $S$ is the size of the whole tree containing $n$, since all valid edge additions are equivalent by symmetry (that is, the probability of randomly choosing a way to add the edges, in which the subtree containing $n-1$ is connected to the side of $v$ is $\frac{s_v}{S}$). If we added the edge $(v,n)$ manually, the formula should be applied to the new graph, that is $\frac{s_v}{s_v+S}n^{k-3}(s_v+S)\prod\limits_{i≠c_v,c_n}s_i$, where $c_x$ is the connected component containing $x$.