自动搬运

查看原文

来自洛谷，原作者为

	滑蒻稽 **

搬运于2025-08-24 22:24:08，当前版本为作者最后更新于2022-03-08 10:24:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Des

P6803 [CEOI2020]星际迷航

Sol

首先设败点为先手必败的点，胜点为先手必胜的点。记胜点 $dp_u=1$，败点 $dp_u=0$。

在不同树之间连边相当于给被连上的树换一个根。

如果一个点接上一个败点，那么自己有可能变成胜点，从而导致根的胜负情况发生逆转（变成胜点或败点都有可能）。如果一个点接上一个胜点那么没有影响。

于是换根 DP 求出有多少个点连接败点后会使根的胜负情况发生逆转，记为 $R_u$。

记整棵树败点数目为 $c$，考虑 $D=1$ 的情况。如果 $1$ 号点是胜点，那么答案为 $(n-R_1)\times c+(n-c)\times n$；如果 $1$ 号点是败点，那么答案为 $R_1\times c$。

然后考虑 $D=2$ 的情况。设以第二棵树败点的答案总和为 $f0$，胜点答案总和为 $f1$。那么对于第 0 颗树的根，如果根是胜点，那么答案为 $(n-R_1)f0+nf1$。如果根是败点，那么答案为 $R_1f0$。

考虑 $f0,f1$ 怎么求。$f0$ 可能由胜点转败点或败点不变组成，$f1$ 同理。于是有

$$f0=\sum_u[dp_u=0](n-R_u)c+\sum_u[dp_u=1]R_uc+\sum_u[dp_u=0]n(n-c) $$$$f1=\sum_u[dp_u=1](n-R_u)c+\sum_u[dp_u=0]R_uc+\sum_u[dp_u=1]n(n-c) $$

对于 $D=3$ 的情况，第一棵树的 $f0',f1'$ 可以用第二棵树的 $f0,f1$ 迭代得到，只需把上面公式中的 $c$ 替换为 $f0$，$n-c$ 替换为 $f1$。$D$ 更大的情况可以用矩阵快速幂优化。

我们设转移矩阵为 $T$，算出 $T^{D-1}\times \begin{matrix}[c&n-c]\end{matrix}$ 得到 $\begin{matrix}[f0&f1]\end{matrix}$。再根据一号点是胜点还是败点输出答案为 $(n-R_1)\times f0+n\times f1$ 或 $R_1\times f0$ 即可。

然后讲一下换根 DP。$R_u$ 的值在两种 情况下不为 $0$。一是节点全都是败点，这样 $R_u$ 就等于所有儿子 $R_v$ 之和。二是节点恰有一个为败点，这样 $R_u$ 就等于该点 $R_v$。于是只需要维护儿子败点的数量即可换根 DP。

最后复杂度 $O(n+\log D)$。

这道题比较麻烦地方在于 $R_u$ 的设置。如果分根从胜点变败点和从败点变胜点处理，那你大概就要写两个 换根 DP，比较麻烦。但用 $R_u$ 表示 $u$ 的胜负逆转后就变得简单了。

My Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 5, D = 1e9 + 7;
inline void Add(int &a, ll b) { a = (a + b) % D; }
int n, c;
ll K;
struct mat {
	int a[2][2];
	mat(bool e = false) {
		memset(a, 0, sizeof a);
		if(e) a[0][0] = a[1][1] = 1;
	}
	mat operator*(const mat &x) {
		mat y;
		for(int i = 0; i < 2; i++)
			for(int j = 0; j < 2; j++)
				y.a[i][j] = ((ll)a[i][0] * x.a[0][j] + (ll)a[i][1] * x.a[1][j]) % D;
		return y;
	}
};
mat fpm(mat a, ll b) {
	mat res(true);
	while(b) {
		if(b & 1) res = res * a;
		b >>= 1, a = a * a;
	}
	return res;
}
vector<int> g[N];
int dp[N], s0[N], R[N], SR[N][2];
// SR[i][0] 表示 i 号点所有 dp 值为 0 的儿子的 R 的和，SR[i][1] 同理 
void dfs1(int u, int f) {
	for(int v : g[u]) {
		if(v == f) continue;
		dfs1(v, u);
		s0[u] += !dp[v];
		SR[u][dp[v]] += R[v];
	}
	dp[u] = (s0[u] > 0);
	if(s0[u] == 1) R[u] = SR[u][0];
	else if(s0[u] == 0) R[u] = SR[u][1] + 1;
}
int dp2[N], R2[N];
// 换根 DP 
void dfs2(int u, int f) {
	if(!dp[u]) ++c;
	R2[u] = R[u], dp2[u] = dp[u];
	for(int v : g[u]) {
		if(v == f) continue;
		int s0u = s0[u], dpu = dp[u], Ru = R[u], SRu0 = SR[u][0], SRu1 = SR[u][1];
		int s0v = s0[v], dpv = dp[v], Rv = R[v], SRv0 = SR[v][0], SRv1 = SR[v][1];

		s0[u] -= !dp[v];
		dp[u] = (s0[u] > 0);
		SR[u][dp[v]] -= R[v];
		if(s0[u] == 1) R[u] = SR[u][0];
		else if(s0[u] == 0) R[u] = SR[u][1] + 1;
		else R[u] = 0;
		dp[v] |= !dp[u];
		s0[v] += !dp[u];
		SR[v][dp[u]] += R[u];
		if(s0[v] == 1) R[v] = SR[v][0];
		else if(s0[v] == 0) R[v] = SR[v][1] + 1;
		else R[v] = 0;
		dfs2(v, u);

		s0[u] = s0u, dp[u] = dpu, R[u] = Ru, SR[u][0] = SRu0, SR[u][1] = SRu1;
		s0[v] = s0v, dp[v] = dpv, R[v] = Rv, SR[v][0] = SRv0, SR[v][1] = SRv1;
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n >> K;
	for(int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		g[u].emplace_back(v), g[v].emplace_back(u);
	}
	dfs1(1, 0);
	dfs2(1, 0);
	
	mat p, T;
	// 处理转移矩阵 
	for(int i = 1; i <= n; i++) {
		if(dp2[i] == 0) {
			Add(T.a[0][0], n - R2[i]);
			Add(T.a[1][0], n);
			Add(T.a[0][1], R2[i]);
		} else if (dp2[i] == 1) {
			Add(T.a[0][0], R2[i]);
			Add(T.a[0][1], n - R2[i]);
			Add(T.a[1][1], n);
		}
	}
	p.a[0][0] = c, p.a[0][1] = n - c;
	p = p * fpm(T, K - 1);

	int f0 = p.a[0][0], f1 = p.a[0][1];
	if(dp[1]) cout << ((ll)(n - R2[1]) * f0 + (ll)n * f1) % D << '\n';
	else cout << (ll)R2[1] * f0 % D << '\n';

	return 0;
}