【题解 树形dp 拆位】 树上异或

题解 树形dp 拆位】 树上异或"/>

【题解 树形dp 拆位】 树上异或

「KDOI-06-S」树上异或

题目描述

给定一棵包含 n n n 个节点的树，第 i i i 个点有一个点权 x i x_i xi​。

对于树上的 n − 1 n-1 n−1 条边，每条边选择删除或不删除，有 2 n − 1 2^{n-1} 2n−1 种选择是否删除每条边的方案。

对于每种删除边的方案，设删除后的图包含 k k k 个连通块，定义这个方案的权值为图中连通块点权异或和的乘积。形式化地说，若这张图包含连通块 C 1 , C 2 , … , C k C_1,C_2,\ldots,C_k C1​,C2​,…,Ck​，其中 C i C_i Ci​ 是第 i i i 个连通块的顶点集合，设 v i = ⨁ u ∈ C i x u v_i=\bigoplus_{u\in C_i} x_u vi​=⨁u∈Ci​​xu​，则这个方案的权值为 v 1 × v 2 × ⋯ × v k v_1\times v_2\times \cdots\times v_k v1​×v2​×⋯×vk​。

求这 2 n − 1 2^{n-1} 2n−1 种删除边的方案的权值之和，答案对 998 244 353 998~244~353 998 244 353 取模。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 n n n，表示树的节点个数。

第二行 n n n 个非负整数 x 1 , x 2 , … , x n x_1,x_2,\ldots,x_n x1​,x2​,…,xn​，表示每个点的点权。

第三行 n − 1 n-1 n−1 个正整数 f 2 , f 3 , … , f n f_2,f_3,\ldots,f_n f2​,f3​,…,fn​，表示节点 i i i 与 f i f_{i} fi​ 之间有一条无向边。

输出格式

输出到标准输出。

输出包含一行一个整数，表示所有 2 n − 1 2^{n-1} 2n−1 种删除边的方案的权值之和，答案对 998 244 353 998~244~353 998 244 353 取模。

样例 #1

样例输入 #1

3
1 2 3
1 1

样例输出 #1

19

样例 #2

样例输入 #2

5
3 4 5 6 7
1 1 2 2

样例输出 #2

5985

提示

【样例解释 #1】

有四种删除边的方案：

• 不删除边：图有且仅有一个连通块，权值为 1 ⊕ 2 ⊕ 3 = 0 1\oplus2\oplus3=0 1⊕2⊕3=0。
• 删除 ( 1 , 2 ) (1,2) (1,2) 一条边：图包含两个连通块，权值为 ( 1 ⊕ 3 ) × 2 = 4 (1\oplus3)\times2=4 (1⊕3)×2=4。
• 删除 ( 1 , 3 ) (1,3) (1,3) 一条边：图包含两个连通块，权值为 ( 1 ⊕ 2 ) × 3 = 9 (1\oplus2)\times3=9 (1⊕2)×3=9。
• 删除 ( 1 , 2 ) (1,2) (1,2)， ( 1 , 3 ) (1,3) (1,3) 两条边：图包含三个连通块，权值为 1 × 2 × 3 = 6 1\times2\times3=6 1×2×3=6。

所有方案权值的总和为 0 + 4 + 9 + 6 = 19 0+4+9+6=19 0+4+9+6=19。

【样例 #3】

见选手目录下的 xor/xor3.in 与 xor/xor3.ans。

这个样例满足测试点 6 ∼ 7 6\sim7 6∼7 的条件限制。

【样例 #4】

见选手目录下的 xor/xor4.in 与 xor/xor4.ans。

这个样例满足测试点 8 8 8 的条件限制。

【样例 #5】

见选手目录下的 xor/xor5.in 与 xor/xor5.ans。

这个样例满足测试点 9 9 9 的条件限制。

【样例 #6】

见选手目录下的 xor/xor6.in 与 xor/xor6.ans。

这个样例满足测试点 19 ∼ 21 19\sim21 19∼21 的条件限制。

---

【数据范围】

对于所有数据保证： 1 ≤ n ≤ 5 × 1 0 5 1\leq n\leq5\times10^5 1≤n≤5×105， 0 ≤ x i ≤ 1 0 18 0\leq x_i\leq10^{18} 0≤xi​≤1018， 1 ≤ f i < i 1\leq f_i<i 1≤fi​<i。

测试点编号	n ≤ n\leq n≤	x i x_i xi​	特殊性质
1 ∼ 2 1\sim2 1∼2	12 12 12	≤ 1 0 9 \leq10^9 ≤109	无
3 3 3	2000 2000 2000	= 1 =1 =1	无
4 4 4	1 0 5 10^5 105	= 1 =1 =1	A
5 5 5	1 0 5 10^5 105	= 1 =1 =1	B
6 ∼ 7 6\sim7 6∼7	1 0 5 10^5 105	= 1 =1 =1	无
8 8 8	1 0 5 10^5 105	≤ 7 \leq7 ≤7	A
9 9 9	1 0 5 10^5 105	≤ 7 \leq7 ≤7	B
10 ∼ 11 10\sim11 10∼11	1 0 5 10^5 105	≤ 7 \leq7 ≤7	无
12 ∼ 16 12\sim16 12∼16	200 200 200	≤ 8191 \leq8191 ≤8191	无
17 17 17	1 0 5 10^5 105	≤ 1 0 9 \leq10^9 ≤109	A
18 18 18	1 0 5 10^5 105	≤ 1 0 9 \leq10^9 ≤109	B
19 ∼ 21 19\sim21 19∼21	1 0 5 10^5 105	≤ 1 0 9 \leq10^9 ≤109	无
22 ∼ 25 22\sim25 22∼25	5 × 1 0 5 5\times10^5 5×105	≤ 1 0 18 \leq10^{18} ≤1018	无

• 特殊性质 A：保证对于任意 1 < i ≤ n 1< i\le n 1<i≤n， f i = i − 1 f_i=i-1 fi​=i−1。
• 特殊性质 B：保证对于任意 1 < i ≤ n 1< i\le n 1<i≤n， f i = 1 f_i=1 fi​=1。

---

【提示】

⊕ \oplus ⊕ 表示按位异或运算。

本题输入输出量较大，请使用适当的 I/O 方式。

请注意常数因子对程序运行效率产生的影响。

---

分析：

树上问题一下子不好分析，我们首先从链的问题来考虑
一一枚举所有的断边情况，时间复杂度是 O ( 2 n ) O(2^n) O(2n)，显然爆炸

我们考虑dp
设 f i f_i fi​表示第i个点的答案( ∑ ∏ \sum\prod ∑∏)
我们考虑枚举前面的断边,
f i = ∑ f j ∗ ( s i x o r s j ) f_i=\sum f_j*(s_i xor s_j) fi​=∑fj​∗(si​xorsj​)

这样 O ( n 2 ) O(n_2) O(n2​)就能把问题全部解决，但是还是不够

怎么办？
我们考虑拆位
设 g i , j , 0 / 1 g_{i,j,0/1} gi,j,0/1​表示第i个点，i所在的联通块的点权二进制的第j位为0/1时，与i所在连通块断开的连通块的答案是多少

对于当前边，我们有断和不断两个选择，如果不断，那么i的前一个点也包含在了i所在的连通块上，需要根据情况去转移对应点的01值，如果当前边断掉，那么前一个点的二进制值就当做0来考虑

于是我们进行以下转移：

感谢大佬的博客
而后f加起来即可

---

#include<bits/stdc++.h>
using namespace std;#define ll long longll Mo = 998244353;const int N = 5e5+10;
int n;
ll a[N],f[N],g[N][64][2];
struct Node{int y,Next;
}e[2*N];
int len , Linkk[N];#define gc getchar()
ll read(){ll s = 0 , ff = 0; char ch = gc;while (ch < '0' || ch > '9') ff|=ch == '-' , ch = gc;while (ch >= '0' && ch <= '9') s = s*10+ch-48 , ch = gc;return ff?-s:s;
} void Insert(int x,int y){e[++len] = (Node){y,Linkk[x]};Linkk[x] = len;
}void Dfs(int x,int faa){for (int i = 0; i < 64; i++){int xx = (a[x]>>i)&1;g[x][i][xx] = 1;}for (int j = Linkk[x]; j; j = e[j].Next){int y = e[j].y;if (y == faa) continue;Dfs(y,x);for (int i = 0; i < 64; i++){int t0 = g[x][i][0] , t1 = g[x][i][1];g[x][i][0] = (t0*((g[y][i][0]+f[y]))+t1*g[y][i][1])%Mo;g[x][i][1] = (t1*((g[y][i][0]+f[y]))+t0*g[y][i][1])%Mo;}}for (int i = 0; i < 64; i++)f[x] = (f[x]+(1ll<<i)%Mo*g[x][i][1])%Mo;return;
}signed main(){n = read();for (int i = 1; i <= n; i++) a[i] = read();for (int i = 2,x; i <= n; i++)x = read(),Insert(i,x),Insert(x,i);Dfs(1,0);printf("%lld",f[1]%Mo);return 0;
}