自动搬运

查看原文

来自洛谷，原作者为

	Leasier 我们所知的是沧海一粟，我们所不知的是汪洋大海。

搬运于2025-08-24 22:45:16，当前版本为作者最后更新于2024-02-12 22:34:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

来点对注意力要求不高的做法。

Subtask $1 \sim 4$

首先可以直接 dp 求出每个子树的最大独立集。

接下来不难发现从 $G_{x - 1}(T)$ 到 $G_x(T)$ 的过程中我们只关心根和右链端点选不选，于是设 $dp_{x, i = 0/1, j = 0/1}$ 表示 $G_x(T)$ 中根选的情况为 $i$，右链端点选的情况为 $j$，此时的最大独立集为多少。

$dp_{1, i, j}$ 不难简单讨论得出，$\forall x > 1, dp_{x, i, j}$ 不难复杂讨论得出 $dp_{x - 1, i, j}$ 到其的转移。

暴力实现即可。时间复杂度为 $O(n + qx)$。

无特殊限制

类似于 [SDOI / SXOI2022] 小 N 的独立集，我们有结论：

• 当二叉树 $T$ 的右链长度 $> 2$，$f(T, i, j)$ 的极差 $\leq 2$，这里 $f$ 的定义基本同 $dp_{x, i, j}$。

证明：

• 考虑一个独立集去掉一个点还是一个独立集，有 $T(x, 0, i) \geq T(x, 1, i) - 1, T(x, i, 0) \geq T(x, i, 1) - 1$。
• 考虑强行将根或右链端点加入独立集并删去周围点，有 $T(x, 1, i) \geq T(x, 0, i) - 1, T(x, i, 1) \geq T(x, i, 0) - 1$。
• 综合上式，有 $|T(x, 0, i) - T(x, 1, i)| \leq 1, |T(x, i, 0) - T(x, i, 1)| \leq 1$。
• 于是 $|T(x, 0, 0) - T(x, 1, 1)| \leq 2, |T(x, 0, 1) - T(x, 1, 0)| \leq 2$，遂得证。

于是我们可以这样表出一个 $x$ 对应的状态：

• $(base, v_{0/1, 0/1})$，表示 $dp_{x, i, j} = v_{i, j} + base$。
• 其中 $\min(v_{i, j}) = 0, \max(v_{i, j}) \leq 2$。

可见后面 $v_{0/1, 0/1}$ 的状态数 $\leq 81$（实际上打表可知只有 $30$ 个）。

每次转移 $dp_{x - 1, i, j} \to dp_{x, i, j}$ 时，我们可以预处理出其从 $v_{0/1, 0/1}$ 转移到了 $v'_{0/1, 0/1}$，且 $base \leftarrow 4base + \Delta$。

在此基础上倍增即可。时间复杂度为 $O(n + q \log x)$。

我的实现中直接把表放在预处理函数里了（下示代码中略去）。

代码：

#include <stdio.h>

typedef long long ll;

const int N = 66, M = 29, K = 1e6 + 7, P = 1 + 1, mod = 998244353;
int to[N + 7][M + 7], delta[N + 7][M + 7], power[M + 7], ls[K], rs[K], dp[K][P][P], g1[K][P][P], temp[P][P];

inline int add(int x, int y){
	return x + y >= mod ? x + y - mod : x + y;
}

inline void init(){
	// 打表结果放这里
	power[0] = 4;
	for (register int i = 1; i <= M; i++){
		for (register int j = 0; j <= N; j++){
			to[j][i] = to[to[j][i - 1]][i - 1];
			delta[j][i] = add(1ll * delta[j][i - 1] * power[i - 1] % mod, delta[to[j][i - 1]][i - 1]);
		}
		power[i] = 1ll * power[i - 1] * power[i - 1] % mod;
	}
}

inline int read(){
	int ans = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9'){
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9'){
		ans = ans * 10 + (ch ^ 48);
		ch = getchar();
	}
	return ans;
}

inline int max(int a, int b){
	return a > b ? a : b;
}

void dfs(int u){
	if (ls[u] != 0) dfs(ls[u]);
	if (rs[u] != 0) dfs(rs[u]);
	int p = max(dp[ls[u]][0][0], dp[ls[u]][0][1]), q = max(p, max(dp[ls[u]][1][0], dp[ls[u]][1][1]));
	if (rs[u] == 0){
		dp[u][0][0] = max(p, max(dp[ls[u]][1][0], dp[ls[u]][1][1]));
		dp[u][0][1] = dp[u][1][0] = 0x80000000;
		dp[u][1][1] = p + 1;
	} else {
		dp[u][0][0] = q + max(dp[rs[u]][0][0], dp[rs[u]][1][0]);
		dp[u][0][1] = q + max(dp[rs[u]][0][1], dp[rs[u]][1][1]);
		dp[u][1][0] = p + dp[rs[u]][0][0] + 1;
		dp[u][1][1] = p + dp[rs[u]][0][1] + 1;
	}
	for (register int i = 0; i <= 1; i++){
		for (register int j = 0; j <= 1; j++){
			g1[u][i][j] = max(dp[u][i][0] + max(dp[u][0][j], dp[u][1][j]), dp[u][i][1] + dp[u][0][j]);
		}
	}
}

inline int min(int a, int b){
	return a < b ? a : b;
}

inline void trans(int f[P][P], int &base, int &state){
	for (register int i = 0; i <= 1; i++){
		for (register int j = 0; j <= 1; j++){
			temp[i][j] = 0x80000000;
		}
	}
	for (register int i = 0; i <= 1; i++){
		for (register int j = 0; j <= 1; j++){
			for (register int k = 0; i + k <= 1; k++){
				for (register int l = 0; l <= 1; l++){
					for (register int x = 0; i + x <= 1; x++){
						for (register int y = 0; y <= 1; y++){
							for (register int z = 0; y + z <= 1; z++){
								for (register int w = 0; z + w <= 1; w++){
									for (register int p = 0; p <= 1; p++){
										for (register int q = 0; z + q <= 1; q++){
											temp[i][j] = max(temp[i][j], f[k][l] + f[x][y] + f[w][p] + f[q][j] + i + z);
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	base = min(temp[0][0], min(temp[0][1], min(temp[1][0], temp[1][1])));
	state = (temp[0][0] - base) + (temp[0][1] - base) * 3 + (temp[1][0] - base) * 9 + (temp[1][1] - base) * 27;
}

int main(){
	int n = read(), q = read();
	init();
	for (register int i = 1; i <= n; i++){
		ls[i] = read();
		rs[i] = read();
	}
	dfs(1);
	for (register int I = 1; I <= q; I++){
		int x = read(), i = read();
		if (--x == 0){
			printf("%d\n", max(g1[i][0][0], max(g1[i][0][1], max(g1[i][1][0], g1[i][1][1]))));
			continue;
		}
		int base, state;
		trans(g1[i], base, state);
		x--;
		for (register int j = 0; (1 << j) <= x; j++){
			if (x >> j & 1){
				base = add(1ll * base * power[j] % mod, delta[state][j]);
				state = to[state][j];
			}
		}
		printf("%d\n", max(state % 3, max(state / 3 % 3, max(state / 9 % 3, state / 27))) + base);
	}
	return 0;
}