题解：P6803 [CEOI 2020] 星际迷航
JHR100330
·
·
题解
推导过程较长，考察知识点较多的题。
前置考虑
首先考虑只有本身一棵树的情况，此时是一个博弈论，从根节点 1 开始，当走到一个点 i 时，若现在的先手必输，记点 i 为败点；若现在的先手必胜，记点 i 为胜点。
显然，叶子节点均为败点，不可以继续往下走了，也不能往回走了。
其次，如果有一个孩子 v_x 为败点，则当前的先手可以主动走到 v_x，使当前的后手（下一手的先手）必输，即该点为胜点。
若孩子均为胜点，则当前的先手无论走到哪个孩子，都会使当前的后手（下一手的先手）必赢，即该点为败点。
树形 DP 即可：
树形 DP：
$$
t_u = t_u + [t_v = 0]
$$
若 $t_1=0$，即根节点 $1$ 为败点，答案为 $0$；若 $t_1 \ge 1$，即根节点 $1$ 为胜点，答案为 $1$。
## $38$ 分做法
再考虑 $d = 1$ 的情况。以 $i$ 为根时，若根 $i$ 为胜点，记 $i$ 为**胜根**；若根 $i$ 为败点，记 $i$ 为**败根**。
连接第一棵树的任意一点 $u$ 和第二棵树的任意一点 $v$，相当于将以 $v$ 为**根**的树接到 $u$ 下方，变成一棵更大的树。
考虑何时才会改变某些点的胜负情况。
当**胜点** $u$ 接**胜根** $v$ 时，$u$ 本来就有一个孩子为败点，胜负情况**不会改变**。
当**胜点** $u$ 接**败根** $v$ 时，与上同理，胜负情况**不会改变**。
当**败点** $u$ 接**胜根** $v$ 时，$u$ 的孩子依然全部都为胜点，胜负情况**不会改变**。
当**败点** $u$ 接**败根** $v$ 时，$u$ 此时有一个孩子 $v$ 为败点了，所以 $u$ 会变成胜点，胜负情况**会改变**。
所以只有**败点接败根**时，该败点胜负状态才会改变。
但是，**该点**胜负状态改变**不代表根**的状态也会改变，所以需要统计以 $1$ 为根的时候，有多少个点**接败根**以后，会改变**根节点** $1$ 的状态，同样在树形 DP 的时候处理。还要处理树的**败根个数**，需要换根 DP。
$t_u$ 表示 $u$ 所有**子节点**中**败点的个数**。
$g_u$ 表示 $u$ 的**子树**中有多少个点**接败根**会改变 $u$ 的状态。
$s_u$ 表示 $u$ 所有**败子结点** $v$ 的 $g_v$ 之和。
$S_u$ 表示 $u$ 所有**子结点** $v$ 的 $g_v$ 之和。
$k_u$ 表示 $u$ **是否为败根**（$k_u = 1$ 表示 $u$ 为败根；$k_u = 0$ 表示 $u$ 不为败根，即 $u$ 为胜根）。
树形 DP：
$$
t_u = t_u + [t_v = 0]
$$
$$
s_u = s_u + g_v[t_v = 0]
$$
$$
S_u = S_u + g_v
$$
$$
g_u =
\begin{cases}
S_u + 1 & (t_u = 0) \\
g_v[t_v = 0] = s_u & (t_u = 1)
\end{cases}
$$
这里详细解释一下 $g_u$ 的转移，其他比较简单，自行理解。
当 $u$ 为败点时，所有子结点 $v$ **均为胜点**，只要有一个 $v$ 变为败点，$u$ 就会变为胜点，$u$ 的胜负状态改变了。同时，若 $u$ **本身**接了一个败点，也会变成胜点，所以 $g_u = S_u + 1$。
当 $u$ 为胜点时，如果有 $\ge 2$ 个子结点为败点，无论改变哪个子结点的胜负情况，$u$ 都**至少有一个子结点为败点**，$u$ 仍为胜点，胜负情况不改变，$g_u$ 为 $0$；如果有**恰好** $1$ 个子结点 $v_x$ 为败点，只有将 $v_x$ 改变为胜点，$u$ 才会变为败点，$u$ 的胜负状态改变，所以 $g_u = g_v[t_v = 0] = s_u$。
换根 DP：
$$
k_u = [t_u = 0]
$$
$$
t_u = t_u - [t_v = 0]\\
t_v = t_v + [t_u = 0]
$$
注意，将根从 $u$ 换到 $v$ 时，一定要先去掉 $u$ 中关于 $v$ 的状态，再让 $v$ 加上关于 $u$ 的状态。
此时若根节点 $1$ 为败根，需要**改变根的胜负情况**才能获胜，答案即为 $\displaystyle {g_1\sum_{u=1}^n k_u}$（第一棵树中以 $1$ 为根，**接败点会改变根节点的胜负情况的点的个数**，乘上第二棵树中的**败点个数**，即为**改变根结胜负情况的方案数**）。
否则若根节点 $1$ 为胜根，需要**不改变根的胜负情况**才能获胜，答案即为 $\displaystyle {n^2 - g_1 \sum_{u=1}^n k_u}$（两棵树，每棵树 $n$ 个点，连接方式总共有 $n^2$ 种，减去**改变根结胜负情况的方案数**，即为**不改变根结点胜负情况的方案数**），$38$ 分到手（**注意数据范围，记得取模**）：
```cpp
for(int i = 1; i <= n; i ++)
sum += k[i];
if(d == 1){
if(k[1]) cout << (sum * r[1]) % MOD;
else cout << (n * n % MOD - sum * r[1] % MOD + MOD) % MOD;
}
```
## $78$ 分做法
继续推广，考虑 $d \ge 2$ 的情况。
先看 $d = 2$，此时一共有三棵树，我们考虑**将后面两棵树合并成一棵树**，这样就变成了 $d = 1$ 的情况了。
根据 $38$ 分做法，我们只需要知道后面两棵树合并以后会出现多少个败根。
因为**第一棵树只能连向第二棵树**，所以合并后只能**将第二棵树的点作为根**，然而第二棵树**任意一个点都可以作为根**，所以仅统计 $g_1$ 是不够的，我们需要统计以**每个点** $u$ **为根**的整棵树中，有多少个点**接败点**，会改变 $u$ 的状态，记为 $r_u$，同样需要换根处理。
$t_u$ 表示 $u$ 所有**子节点**中**败点的个数**。
$g_u$ 表示 $u$ 的**子树**中有多少个点**接败根**会改变 $u$ 的状态。
$s_u$ 表示 $u$ 所有**败子结点** $v$ 的 $g_v$ 之和。
$S_u$ 表示 $u$ 所有**子结点** $v$ 的 $g_v$ 之和。
$r_u$ 表示以 $u$ 为**根**的**整棵树**中有多少个点接败点会改变 $u$ 的状态。
$k_u$ 表示 $u$ **是否为败根**（$k_u = 1$ 表示 $u$ 为败根；$k_u = 0$ 表示 $u$ 不为败根，即 $u$ 为胜根）。
树形 DP：
$$
t_u = t_u + [t_v = 0]
$$
$$
s_u = s_u + g_v[t_v = 0]
$$
$$
S_u = S_u + g_v
$$
$$
g_u =
\begin{cases}
S_u + 1& (t_u = 0) \\
g_v(t_v = 0) & (t_u = 1)
\end{cases}
$$
换根 DP：
$$
k_u = [t_u = 0]
$$
$$
r_u = g_u
$$
$$
g_u =
\begin{cases}
g_u - g_v &(t_u = 0) \\
S_u - g_v + 1 &(t_u = 1,t_v = 0) \\
s_u - g_v &(t_u = 2,t_v = 0) \\
\end{cases}
$$
$$
s_u = s_u - g_v[t_v = 0]\\
S_u = S_u - g_v
$$
$$
t_u = t_u - [t_v = 0]\\
t_v = t_v + [t_u = 0]
$$
$$
s_v = s_v + g_u[t_u = 0]\\
S_v = S_v + g_u
$$
$$
g_v =
\begin{cases}
g_v + g_u &(t_v = 0) \\
g_u &(t_v = 1,t_u = 0) \\
0 &(t_v \ge 2) \\
\end{cases}
$$
这里详细解释一下换根时 $g_u$ 和 $g_v$ 的转移，其他比较简单，自行理解。
当 $u$ **换根前**为败点时，$g_u$ 为所有 $g_v$ 之和再加 $1$，将根从 $u$ 换到 $v$ 时，$v$ 已经**不是** $u$ 的子结点了，使 $g_u$ 减去 $g_v$ 即可。
当 $u$ **换根前**只有 $v$ 一个败子结点时，将根从 $u$ 换到 $v$ 时，$v$ 已经不是 $u$ 的子结点了，$u$ 其余的所有子结点 $v$ **均为胜点**，则$g_u = S_u - g_v + 1$。
当 $u$ **换根前**有两个败子结点 $v,v'$ 时，将根从 $u$ 换到 $v$ 时，$v$ 已经不是 $u$ 的子结点了，则 $u$ 此时只有 $v'$ 一个败子节点了，则 $g_u$ 从 $0$ 变为 $g_{v'} = s_u - g_v$。
其余情况 $g_u$ 不变。
当 $v$ **换根后**为败点，则原来也为败点，只需要累加 $g_u$ 即可。
当 $v$ **换根后**为胜点且只有 $u$ 一个败子节点，令 $g_v = g_u$ 即可。
当 $v$ **换根后**有两个及以上个败子节点，此时任意改变一个孩子的胜负情况，$v$ 都至少有一个败子节点，始终为胜点，胜负状态始终不变，$g_v = 0$。
其余情况 $g_v$ 不变。
然后就 $O(n)$ 求出 $r_i$ 了（换完根记得回溯）：
```cpp
void dfs1(int u, int fa){
for(int v : e[u]){
if(v == fa) continue;
dfs1(v, u);
t[u] += (t[v] == 0);
if(t[v] == 0) s[u] += g[v];
S[u] += g[v];
}
if(t[u] == 0)
g[u] = S[u] + 1;
if(t[u] == 1)
g[u] = s[u];
}
void rt(int u, int v){
if(t[u] == 0) g[u] -= g[v];
if(t[u] == 1 && t[v] == 0) g[u] = S[u] - g[v] + 1;
if(t[u] == 2 && t[v] == 0) g[u] = s[u] - g[v];
if(t[v] == 0) s[u] -= g[v];
S[u] -= g[v];
t[u] -= (t[v] == 0);
t[v] += (t[u] == 0);
if(t[u] == 0) s[v] += g[u];
S[v] += g[u];
if(t[v] == 0) g[v] += g[u];
if(t[v] == 1 && t[u] == 0) g[v] = g[u];
if(t[v] >= 2) g[v] = 0;
}
void dfs2(int u, int fa){
r[u] = g[u];
k[u] = !t[u];
for(int v : e[u]){
if(v == fa) continue;
rt(u, v);
dfs2(v, u);
rt(v, u);
}
}
```
当 $d = 3, 4, \cdots$ 时也同理，我们每一步尝试将第 $d - 1$ 棵树和第 $d$ 棵树合并，这样就可可以一步步缩小范围，最后变成 $d = 1$ 的情况。
然后就是递推式。
设 $dp_i$ 表示任意合并最后 $i$ 棵树后败根的**总个数**。
要**使根节点为败根**，分两种情况：原本就是**败根**，连接后**不改变**根节点的胜负情况；原本是**胜根**，连接后**改变**根节点的胜负情况。
与 $d = 1$ 时的式子同理，根据上面两种情况写出式子并化简（特别注意：$k_u$ 表示 $u$ **是否为败根**，$k_u = 1$ 表示 $u$ 为败根；$k_u = 0$ 表示 $u$ 不为败根，即 $u$ 为胜根）：
$$
\begin{aligned}
dp_{i} &= \displaystyle{\bigg (\sum_{u = 1}^n \big ([k_u = 0] \times r_u \times dp_{i - 1} \big ) \bigg ) + \bigg (\sum_{u = 1}^n \big ([k_u = 1] \times ((n^2)^{i-1} - r_u \times dp_{i - 1}) \big ) \bigg )} \\
&= \displaystyle{\bigg (\sum_{u = 1}^n \big ([k_u = 0] \times r_u \times dp_{i - 1} \big ) \bigg ) + \bigg (\sum_{u = 1}^n \big ([k_u = 1] \times (n^2)^{i-1} \big ) \bigg ) - \bigg (\sum_{u = 1}^n \big ([k_u = 1] \times r_u \times dp_{i - 1} \big ) \bigg )} \\
&= \displaystyle{\bigg (dp_{i - 1} \times \sum_{u = 1}^n \big ([k_u = 0] \times r_u \big ) \bigg ) + \bigg ((n^2)^{i-1} \times \sum_{u = 1}^n [k_u = 1] \bigg ) - \bigg (dp_{i - 1} \times \sum_{u = 1}^n \big ([k_u = 1] \times r_u \big ) \bigg )} \\
&= \displaystyle{\bigg (dp_{i - 1} \times \sum_{u = 1}^n \big ([k_u = 0] \times r_u - [k_u = 1] \times r_u \big ) \bigg ) + \bigg ((n^2)^{i-1} \times \sum_{u = 1}^n [k_u = 1] \bigg )} \\
\end{aligned}
$$
这里的 $(n^2)^{i-1}$ 表示最后 $i$ 棵树任意连边的方案数，因为每相邻两颗树之间有 $n^2$ 种连法，一共就有 $(n^2)^{i-1}$ 种连法。
令 $\displaystyle{x = \sum_{u = 1}^n \big ([k_u = 0] \times r_u - [k_u = 1] \times r_u \big ),y = \sum_{u = 1}^n [k_u = 1]}$。
此时可以发现 $x,y$ 为可 $O(n)$ 预处理的常数，递推式变为 $dp_i = x \times dp_{i - 1} + y \times (n^2)^{i-1}$。
初始值：$dp_1 = \displaystyle {\sum_{u=1}^n k_u}$。
与 $d = 1$ 时同理，若根节点 $1$ 为败根，答案即为 $r_1 \times dp_d$；若根节点 $1$ 为胜根，答案即为 $(n^2)^{d} - r_1 \times dp_d$，$78$ 分到手：
```cpp
for(int i = 1; i <= n; i ++){
dp[1] += k[i];
if(k[i]) x = (x - r[i] + MOD) % MOD;
else x = (x + r[i]) % MOD;
y += k[i];
}
for(int i = 2; i <= d; i ++)
dp[i] = (dp[i - 1] * x % MOD + y * qpow(n * n % MOD, i - 1)) % MOD;
if(k[1]) cout << r[1] * dp[d] % MOD;
else cout << (qpow(n * n % MOD, d) - r[1] * dp[d] % MOD + MOD) % MOD;
```
## $100$ 分做法
然后可以发现 $(n^2)^{i}$ 可以用 $(n^2)^{i-1}$ 转移，$dp_{i}$ 可以用 $dp_{i-1}$ 和 $(n^2)^{i-1}$ 转移，使用矩阵快速幂加速递推即可。
初始矩阵：
$$
A =
\begin{bmatrix}
\displaystyle {\sum_{u=1}^n k_u} & n^2 \\
\end{bmatrix}
$$
转移矩阵：
$$
B =
\begin{bmatrix}
x & 0 \\
y & n^2
\end{bmatrix}
$$
$dp_d$ 即为：
$$
A \times B^{d-1}
$$
因为以 $dp_1$ 为初始值，所以只需要递推 $d - 1$ 次。
答案同上，若根节点 $1$ 为**败根**，答案即为 $r_1 \times dp_d$；若根节点 $1$ 为**胜根**，答案即为 $(n^2)^{d} - r_1 \times dp_d$，$100$ 分，完结撒花！
## 参考代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100050, M = 3, MOD = 1e9 + 7;
struct matrix{
ll c[M][M];
matrix(){memset(c, 0, sizeof c);}
};
matrix ans, u;
matrix operator*(matrix &x, matrix &y){
matrix t;
for(int i = 1; i <= 2; i ++)
for(int j = 1; j <= 2; j ++)
for(int k = 1; k <= 2; k ++)
t.c[i][j] = (t.c[i][j] + x.c[i][k] * y.c[k][j] % MOD) % MOD;
return t;
}
matrix mqpow(matrix a, ll b){
matrix x, sum;
x = a;
for(int i = 1; i <= 2; i ++)
sum.c[i][i] = 1;
for(; b; b >>= 1){
if(b & 1) sum = sum * x;
x = x * x;
}
return sum;
}
ll qpow(ll a, ll b){
ll t = 1;
for(; b; b >>= 1){
if(b & 1) t = t * a % MOD;
a = a * a % MOD;
}
return t;
}
ll n, d;
ll t[N], g[N], s[N], S[N], r[N], k[N], x = 0, y = 0;
vector<int> e[N];
void dfs1(int u, int fa){
for(int v : e[u]){
if(v == fa) continue;
dfs1(v, u);
t[u] += (t[v] == 0);
if(t[v] == 0) s[u] += g[v];
S[u] += g[v];
}
if(t[u] == 0)
g[u] = S[u] + 1;
if(t[u] == 1)
g[u] = s[u];
}
void rt(int u, int v){
if(t[u] == 0) g[u] -= g[v];
if(t[u] == 1 && t[v] == 0) g[u] = S[u] - g[v] + 1;
if(t[u] == 2 && t[v] == 0) g[u] = s[u] - g[v];
if(t[v] == 0) s[u] -= g[v];
S[u] -= g[v];
t[u] -= (t[v] == 0);
t[v] += (t[u] == 0);
if(t[u] == 0) s[v] += g[u];
S[v] += g[u];
if(t[v] == 0) g[v] += g[u];
if(t[v] == 1 && t[u] == 0) g[v] = g[u];
if(t[v] >= 2) g[v] = 0;
}
void dfs2(int u, int fa){
r[u] = g[u];
k[u] = !t[u];
for(int v : e[u]){
if(v == fa) continue;
rt(u, v);
dfs2(v, u);
rt(v, u);
}
}
int main() {
scanf("%lld%lld", &n, &d);
for(int i = 1, u, v; i < n; i ++){
scanf("%d%d", &u, &v);
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1, -1);
dfs2(1, -1);
for(int i = 1; i <= n; i ++){
ans.c[1][1] += k[i];
if(k[i]) x = (x - r[i] + MOD) % MOD;
else x = (x + r[i]) % MOD;
y += k[i];
}
ans.c[1][2] = n * n % MOD;
u.c[1][1] = x, u.c[1][2] = 0, u.c[2][1] = y, u.c[2][2] = n * n % MOD;
matrix f = mqpow(u, d - 1);
ans = ans * f;
if(k[1]) cout << r[1] * ans.c[1][1] % MOD;
else cout << (qpow(n * n % MOD, d) - r[1] * ans.c[1][1] % MOD + MOD) % MOD;
return 0;
}
```