自动搬运

查看原文

来自洛谷，原作者为

	喵仔牛奶 黄昏再美终要黑夜。

搬运于2025-08-24 22:51:25，当前版本为作者最后更新于2023-10-15 19:41:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution

树形 DP 好题。

Part I 部分分类比

下文为简单，我们称一个连通块的权值为连通块内点的异或和。

考虑链的部分分，显然可以设 $f_{i}$ 是前 $i$ 个点所有断边方案的权值和，对于每个点枚举上一条断的边转移。令 $s_i=\bigoplus_{j=1}^{i}a_j$，则 $f_i=\sum_{j=0}^{i-1}(s_i\oplus s_{j})\times f_j$。

这样是 $\mathcal{O}(n^2)$ 的，我们拆位算贡献，就可以做到 $\mathcal{O}(n\log V)$。

具体地，设 $g_{i,j,k}$ 是所有断边方案中，与 $i$ 相连的连通块的价值在二进制下第 $j$ 位是 $k$ 的，不与 $i$ 相连的连通块的价值乘积的和。

初始状态：若 $a_u$ 第 $j$ 位为 $1$，则 $g_{i,j,1}=1$，否则 $g_{i,j,0}=1$。

转移如下：

• 为了避免后效性，先保存 $t_0=g_{i,j,0},t_1=g_{i,j,1}$。
• $\begin{cases} g_{i,j,0}=t_{0}\times(g_{i-1,j,0}+f_{i-1})+t_{1}\times g_{i-1,j,1}\\ g_{i,j,1}=t_{0}\times g_{i-1,j,1}+t_{1}\times (g_{i-1,j,0}+f_{i-1})\\ f_{i}=\sum_{j=0}^{63}2^j\times g_{i,j,1} \end{cases}$

同理，对于树我们也通过断边来转移。

Part II 解决问题

设 $f_{u}$ 是以 $u$ 为根的子树的所有断边方案的权值和。

为了转移，再设 $g_{u,i,j}$ 是以 $u$ 为根的子树里断开若干边，所有断边方案中，与 $u$ 相连的连通块的价值在二进制下第 $i$ 位是 $j$ 的，不与 $u$ 相连的连通块的价值乘积的和。

初始状态：若 $a_u$ 第 $i$ 位为 $1$，则 $g_{u,i,1}=1$，否则 $g_{u,i,0}=1$。

对于每个儿子，枚举二进制下每位 $i$ 转移。

• 不断儿子相当于当前连通块的异或和第 $i$ 位异或上儿子连通块的第 $i$ 位，断掉儿子相当于异或上 $0$。
• 为了避免后效性，先保存 $t_0=g_{u,i,0},t_1=g_{u,i,1}$。
• $\begin{cases} g_{u,i,0}\gets t_0\times(g_{v,i,0}+f_{v})+t_1\times g_{v,i,1} \\ g_{u,i,1}\gets t_0\times g_{v,i,1}+t_1\times(g_{v,i,0}+f_{v}) \end{cases}$

转移完后，$f_{u}$ 就可以简单地计算啦。

• $f_{u}=\sum_{i=0}^{63}2^i\times g_{u,i,1}$。

答案显然就是 $f_{1}$。

Part III 小结

不难发现该算法时空复杂度均为 $\mathcal{O}(n\log V)$，需要将 $g_{u,i,j}$ 用 int 类型保存才能通过。

启示：

• 树形 DP 的题可以用链的部分分类比得出正解。
• 树形 DP 需要想清楚状态、列明白转移方程再写，否则在调试过程中通常会越写越复杂，导致耗费大量时间而最终一分也不得。

Code

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
using namespace std;
namespace Milkcat {
    typedef long long LL;
    typedef pair<LL, LL> pii;
    const int N = 1e6 + 5, mod = 998244353;
    LL n, u, v, a[N], f[N]; int g[N][64][2];
    vector<int> G[N];
    void dfs(int u, int fa) {
    	REP(i, 0, 63) g[u][i][a[u] >> i & 1] = 1;
    	for (int v : G[u]) {
    		if (v == fa) continue;
    		dfs(v, u);
    		REP(i, 0, 63) {
    			LL t0 = g[u][i][0], t1 = g[u][i][1];
    			g[u][i][0] = (t0 * (g[v][i][0] + f[v]) + t1 * g[v][i][1]) % mod;
    			g[u][i][1] = (t0 * g[v][i][1] + t1 * (g[v][i][0] + f[v])) % mod;
    		}
		}
		REP(i, 0, 63) f[u] = (f[u] + (1LL << i) % mod * g[u][i][1]) % mod;
	}
    int main() {
		cin >> n;
		REP(i, 1, n) cin >> a[i];
		REP(i, 2, n)
			cin >> u, G[u].push_back(i), G[i].push_back(u);
		dfs(1, 0);
		cout << f[1] << '\n';
        return 0;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}