小爆个标，给出一个 \(\mathcal{O}(n + q + \sqrt{x} + \log \operatorname{mod})\) 的做法。
可能写的有点意识流了，可以结合代码理解或者私信我吧 qaq。
首先对于最大独立集有 DP：
设 \(f'_{i, 0 / 1}\) 表示考虑 \(i\) 的子树，\(i\) 选没选的最大独立集点数。
转移就是 \(f'_{i, 0} = \max\{f'_{ls, 0}, f'_{ls, 1}\} + \max\{f'_{rs, 0}, f'_{rs, 1}\}, f'_{i, 1} = f'_{ls, 0} + f'_{rs, 0} + 1\)。
但是 \(\max\{f'_{ls, 0}, f'_{ls, 1}\}\) 太丑了，考虑换个写法。
记 \(f_{i, 0} = f'_{i, 0}, f_{i, 1} = \max\{f'_{i, 0}, f'_{i, 1}\}\)。
那么转移就是 \(f_{i, 0} = f_{ls, 1} + f_{rs, 1}, f_{i, 1} = \max\{f_{i, 0}, f_{ls, 0} + f_{rs, 0} + 1\}\)。
同时记 \(g_{i} = f_{i, 1} - f_{i, 0}\)。
接下来的给出几个结论，感性理解应该比较简单：
- \(0\le g_i\le 1\)。
证明考虑如果 \(f'_{i, 0}\ge f'_{i, 1}\)，显然 \(g_i\) 为 \(0\)；否则若 \(f'_{i, 0} < f'_{i, 1}\)，那么直接不选 \(i\) 这个点，差也只会为 \(1\)，那么此时 \(g_i = 1\) 得证。 - \(g_{i} = [g_{ls} = 0]\times [g_{rs} = 0]\)，\(f_{i, 1} = f_{ls, 1} + f_{rs, 1} + g_i\)，手玩转移式得到。
那么考虑直接维护 \(f_i = f_{i, 1}\) 与 \(g_i\)，转移式就是上面提到的 \(g_{i} = [g_{ls} = 0]\times [g_{rs} = 0]\)，\(f_{i} = f_{ls} + f_{rs} + g_i\)，最后的 \(f_{rt}\) 即为答案。
接下来考虑如何应用到此问题上。
考虑 \(G_1\) 的操作，能够明确的是实质上只关心右链。
进一步的，发现因为对于 \(f\) 转移就是 \(f_{ls} + f_{rs} + g_i\)，对于最末的右链结点这里只是把 \(f_{rs}\) 给填充了并且可能影响了 \(g_{i}\)。
所以实际上只需要考虑下右链的 \(g\) 即可了，对于 \(f\) 基本是每 \(\operatorname{merge}\) 一次或者 \(G_1\) 一次就是 \(\times 2\)，改变的量放在 \(g\) 中考虑。
考虑到对于右链的节点 \(i\)，如果 \(g_{ls} = 1\)，那么 \(g_i\) 一定为 \(0\)，否则 \(g_{i} = 1 - g_{rs}\)。
于是可以预处理出子树内右链从底到根满足 \(g_{ls(u)} = 1\) 的极长链 \(l\)，然后对这个链进行分讨。
记 \(p\) 为右链末尾节点。
因为第一轮操作比较特殊，不涉及 \(\operatorname{merge}\)，所以第一轮可能需要特殊处理一下。
后面的轮数一概认为是不算第一轮的。
-
这个极长链并非右链。
对于 \(G_1\) 操作，考虑 \(g_{rt}\) 的值：- \(g_{rt} = 0\)，本来就有 \(g_p = 1\)，所以并不影响。
- \(g_{rt} = 1\)，那么 \(g_p\) 原本为 \(0\)，就会变成 \(1\)，对应的就会使得链 \(l\) 上的点的 \(g\) 全部取反。
那么如果链 \(l\) 长度为奇数，原本有 \(g\) 为 \(1\) 的个数比 \(0\) 的个数多一个，取反后就变成了 \(0\) 的个数比 \(1\) 的个数多一个了，于是此时有 \(-1\) 的贡献。
同时因为链 \(l\) 是被阻断的，所以在 \(G_1\) 操作后整颗树的底至根极长链与 \(l\) 是相同的。
考虑 \(\operatorname{merge}\) 操作，这个就比较简单了，因为左右两颗子树是一样的，那么就有 \(g_{rt'} = 1 - g_{rt}\)。
所以当 \(g_{rt} = 0\) 时新产生的 \(g_{rt'} = 1\)，就有 \(+1\) 的新贡献。
且同时极长链 \(l\) 也不会被影响。同时可以知道，此时 \(g_{rt}\) 就以 \(0, 1, 0, 1\)（假设初始 \(g_{rt} = 0\)）这样不断的循环，那么每 \(2\) 轮就会在 \(\operatorname{merge}\) 操作时产生 \(+1\) 的新贡献，如果 \(l\) 长度为奇数也会在下次的 \(G_1\) 操作产生 \(-1\) 的贡献。
如果去考虑产生的新贡献往后影响的系数，能发现这其实对应的是个 \(16\) 为公比的等比数列。 -
这个极长链就是右链。
那么考虑到 \(G_1\) 操作后，右链 \(l\) 的长度也相当于是复制了一遍放到了后面，那么此时右链长度必为偶数。
于是可以知道此时必有 \(g_{rt} = 0, g_{p} = 1\)。
那么对于 \(\operatorname{merge}\) 操作，必定有 \(g_{rt'} = 1\)，能产生 \(+1\) 的贡献。并且在这之后极长链对应会再加上 \(rt'\)，长度就变为奇数了，又因为 \(g_{rt'} = 1\)，所以在 \(G_1\) 操作后会有 \(-1\) 的贡献。
于是分析后可以知道每一轮必定有 \(+1\) 的贡献，对应的贡献系数是个公比为 \(4\) 的等比数列。
分讨完毕！
于是 \(g\) 的这个贡献其实都是公比数列，对于 \(f\) 的贡献因为上面提到的增量算在 \(g\) 中，对应的就是每一轮 \(\times 4\)。
（所以形式这么优美，官解却似乎没往这边想，有点可惜。）
于是可以用光速幂预处理出 \(4\) 的幂次，并预处理出 \(\operatorname{inv}(3), \operatorname{inv}(15)\)。
对于初始 \(f, g\) 及极长链的处理都是可以 \(\mathcal{O}(n)\) 预处理的。
那么就在 \(\mathcal{O}(n + q + \sqrt{x} + \log \operatorname{mod})\) 的时间复杂度做完了。
代码中的 \(f, g\) 含义不变，\(h\) 代表判断极长链是否是右链，\(hd\) 代表右链的长度的奇偶。
需要注意的是里面先直接把第一轮的 \(G_1\) 做了，实际算的 \(g\) 的贡献只涉及了后面的 \(x - 1\) 轮。
#include<bits/stdc++.h>
#define gc getchar_unlocked
inline int read(int x = 0, int c = gc()) {
while (! isdigit(c)) c = gc();
while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
return x;
}
using ll = long long;
constexpr ll mod = 998244353;
constexpr inline ll qpow(ll a, ll b, ll v = 1) {
while (b) {
b & 1 && ((v *= a) %= mod), b >>= 1, (a *= a) %= mod;
}
return v;
}
constexpr ll inv15 = qpow(15ll, mod - 2), inv3 = qpow(3ll, mod - 2);
constexpr int B = 32768, Z = 32767;
ll pw1[B + 1], pw2[B + 1];
inline void init() {
for (int i = pw1[0] = 1; i <= B; i++) {
pw1[i] = (pw1[i - 1] * 4ll) % mod;
}
for (int i = pw2[0] = 1; i <= B; i++) {
pw2[i] = (pw2[i - 1] * pw1[B]) % mod;
}
}
inline ll pw4(int x) {
return pw1[x & Z] * pw2[x >> 15] % mod;
}
const int maxn = 5e5 + 10;
int n, q;
int ls[maxn], rs[maxn], f[maxn], g[maxn], h[maxn], hd[maxn];
void dfs(int u) {
if (! u) return ;
dfs(ls[u]), dfs(rs[u]);
g[u] = ! (g[ls[u]] | g[rs[u]]);
f[u] = f[ls[u]] + f[rs[u]] + g[u];
h[u] = h[rs[u]] & (! g[ls[u]]);
hd[u] = h[u] ? g[u] : hd[rs[u]];
}
int main() {
init();
n = read(), q = read();
for (int i = 1; i <= n; i++) ls[i] = read(), rs[i] = read();
h[0] = 1;
dfs(1);
for (int x, u; q--; ) {
x = read() - 1, u = read();
ll ans;
if (! h[u]) {
ans = 1ll * (f[u] * 2 - (g[u] && hd[u])) * pw4(x) % mod;
if (g[u] == 0 && x >= 1) {
(ans += 1ll * (1 + (! hd[u])) * (pw4(x + 1) - pw4(~ x & 1) + mod) * inv15) %= mod;
}
if (g[u] == 1 && x >= 2) {
(ans += 1ll * (1 + (! hd[u])) * (pw4(x) - pw4(x & 1) + mod) * inv15) %= mod;
}
} else {
ans = 1ll * (f[u] * 2 - hd[u]) * pw4(x) % mod;
(ans += (pw4(x) - 1ll + mod) * inv3) %= mod;
}
printf("%lld\n", ans);
}
return 0;
}