题解：P6803 [CEOI 2020] 星际迷航

推导过程较长，考察知识点较多的题。

前置考虑

首先考虑只有本身一棵树的情况，此时是一个博弈论，从根节点

1

开始，当走到一个点

i

时，若现在的先手必输，记点

i

为败点；若现在的先手必胜，记点

i

为胜点。

显然，叶子节点均为败点，不可以继续往下走了，也不能往回走了。

其次，如果有一个孩子

v_x

为败点，则当前的先手可以主动走到

v_x

，使当前的后手（下一手的先手）必输，即该点为胜点。

若孩子均为胜点，则当前的先手无论走到哪个孩子，都会使当前的后手（下一手的先手）必赢，即该点为败点。

树形 DP 即可：

t_u

表示

u

所有子节点中败点的个数（当

t_i = 0

时，点

i

为败点；当

t_i \ge 1

时，点

i

为胜点）。

树形 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;
}

题解：P6803 [CEOI 2020] 星际迷航

文章操作

前置考虑

$38$ 分做法

$78$ 分做法

$100$ 分做法

参考代码：

相关推荐

评论

题解：P6803 [CEOI 2020] 星际迷航

文章操作

前置考虑

383838 分做法

787878 分做法

100100100 分做法

参考代码：

相关推荐

评论

$38$ 分做法

$78$ 分做法

$100$ 分做法