\(\text{P6803 [CEOI2020] 星际迷航 题解}\)
观察这个从第 \(0\) 棵树走向第 \(D\) 棵树的过程是困难的，我们难以判定走到下一棵树的情况。于是我们不妨从第 \(D\) 棵树向第 \(0\) 棵树来倒推。从第 \(i\) 层走向第 \(i+1\) 层的边为 \(x\to y\) 时，事实上此时 \(y\) 就是第 \(i+1\) 棵子树的根。当我们在处理连边 \(x\to y\) 时，也就是在为 \(y\) 寻找一个合适的 \(x\) 的过程。于是我们设 \(f(i,0/1)\) 表示考虑了 \(i\) 层树，从第 \(1\) 棵树的某个节点开始走，此时根节点先手必败/必胜的方案数。
根据我们刚才的分析，现在需要考虑的是在第 \(1\) 棵树前面加上第 \(0\) 棵树的情形。记这条边为 \(x\to y\)。设此时第 \(0\) 棵树的根节点为 \(p\)。考虑当 \(p\) 先手必胜，即 \(f(i+1,1)\) 时：
- 若 \(p\) 原本先手必胜，则添加的 \(x\to y\) 不能改变 \(p\) 现在的状态；
- 否则必须改变 \(p\) 的状态。
\(p\) 先手必败时是同理的。于是我们分析 \(x\to y\) 改变 \(p\) 状态的条件。若 \(x\) 原先是必胜的，那么无论如何也不会改变 \(x\) 的状态，\(x\) 原先必败时，也只有 \(y\) 同样为必败才能改变 \(p\) 的状态。那么此时 \(y\) 的状态包含在 \(f\) 中，我们需要求的是向必败点连边后可以改变根节点个数的点。我们设它为 \(g(x)\)，同时设 \(t(x)\) 表示以 \(x\) 为根使先手必败/必胜。
那么 \(f\) 的转移式是容易的：
\[f(i+1,0)\longleftarrow\sum_{x=1}^{n}\left\{\begin{matrix} g(x)f(i,0), &t(x)=0 \\ n(f(i,0)+f(i,1))-g(x)f(i,0), &t(x)=1 \end{matrix}\right. \]\[f(i+1,1)\longleftarrow\sum_{x=1}^{n}\left\{\begin{matrix} g(x)f(i,0), &t(x)=1 \\ n(f(i,0)+f(i,1))-g(x)f(i,0), &t(x)=0 \end{matrix}\right. \]现在的目标是求出 \(t\) 和 \(g\)。对于容易一些的 \(t\)，我们设 \(h(x)\) 表示 \(x\) 儿子中必败点的个数，那么 \(h\) 的转移是显然的，\(t\) 的转移也容易得到。现在的问题是求出 \(g\)。那这个东西还是要按 \(h\) 的取值分类讨论。当 \(h(x)>1\) 时，显然 \(g(x)=0\)，\(h(x)=1\) 时，记必败的儿子为 \(y\)，那么 \(g(x)=g(y)\)，\(h(x)=0\) 时，\(g(x)\) 就是 \(\sum g(\operatorname{son_x})+1\)，加上的 \(1\) 是 \(x\) 本身。
为了方便一些，可以记 \(w(x,0/1)\) 表示以 \(x\) 为根时，\(x\) 儿子里必胜/必败的点的 \(g\) 的和。这里给出 \(g\) 的形式化转移式：
\[g(x)=\left\{\begin{matrix} w(x,1)+1, &h(x)=0 \\ w(x,0), &h(x)=1 \\ 0,&\text{Other.} \end{matrix}\right.\\ \]那么我们知道了 \(t(1),g(1)\) 后做一个换根就可以求出所有的 \(t,g\) 值了。对于 \(f\) 的转移，用矩阵是好维护的。
代码：
#include <bits/stdc++.h>
#define N 100005
#define int long long
#define mod 1000000007
using namespace std;
int n, d;
vector<int>v[N];
int h[N];
int w[N][2];
int g[N];
void dfs1(int x, int fa) {
for (auto y : v[x]) {
if (y == fa) continue;
dfs1(y, x);
h[x] += !h[y];
w[x][h[y] > 0] += g[y];
}
if (h[x] == 0) g[x] = w[x][1] + 1;
else if(h[x] == 1) g[x] = w[x][0];
else g[x] = 0;
}
int ct;
int dth, dtg, dtw[2];
void dfs2(int x, int fa) {
if (h[x] == 0) ++ct;
for (auto y : v[x]) {
if (y == fa) continue;
dtw[0] = w[x][0], dtw[1] = w[x][1];
dth = h[x] - !h[y];
dtw[h[y] > 0] -= g[y];
if (dth == 0) dtg = dtw[1] + 1;
else if(dth == 1) dtg = dtw[0];
else dtg = 0;
h[y] += !dth;
w[y][dth > 0] += dtg;
if (h[y] == 0) g[y] = w[y][1] + 1;
else if(h[y] == 1) g[y] = w[y][0];
else g[y] = 0;
dfs2(y, x);
}
}
struct Mar {
int a[2][2];
Mar() {
memset(a, 0, sizeof a);
}
};
void add(int &x, int y) {
x = ((x + y) % mod + mod) % mod;
}
Mar operator * (Mar &a, Mar &b) {
Mar res;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
add(res.a[i][j], a.a[i][k] * b.a[k][j] % mod);
return res;
}
Mar qpow(Mar x, int y) {
Mar ans;
ans.a[0][0] = ans.a[1][1] = 1;
while (y) {
if (y & 1) ans = ans * x;
x = x * x;
y >>= 1;
}
return ans;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> d;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs1(1, 0);
dfs2(1, 0);
Mar res;
for (int i = 1; i <= n; i++) {
if (h[i]) {
add(res.a[0][0], g[i]);
add(res.a[0][1], n - g[i]);
add(res.a[1][1], n);
}
else {
add(res.a[0][0], n - g[i]);
add(res.a[0][1], g[i]);
add(res.a[1][0], n);
}
}
res = qpow(res, d - 1);
Mar ans;
ans.a[0][0] = ct, ans.a[0][1] = n - ct;
ans = ans * res;
if (h[1]) cout << (n * (ans.a[0][0] + ans.a[0][1]) % mod - g[1] * ans.a[0][0] % mod + mod) % mod << "\n";
else cout << g[1] * ans.a[0][0] % mod << "\n";
return 0;
}