怎么做网站排名优化,西安网站建设外包服务,店务系统,台州公司网站建设「KDOI-06-S」树上异或
题目描述
给定一棵包含 n n n 个节点的树#xff0c;第 i i i 个点有一个点权 x i x_i xi。
对于树上的 n − 1 n-1 n−1 条边#xff0c;每条边选择删除或不删除#xff0c;有 2 n − 1 2^{n-1} 2n−1 种选择是否删除每条边的方案。
对于…「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∈Cixu则这个方案的权值为 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\oplus30 1⊕2⊕30。删除 ( 1 , 2 ) (1,2) (1,2) 一条边图包含两个连通块权值为 ( 1 ⊕ 3 ) × 2 4 (1\oplus3)\times24 (1⊕3)×24。删除 ( 1 , 3 ) (1,3) (1,3) 一条边图包含两个连通块权值为 ( 1 ⊕ 2 ) × 3 9 (1\oplus2)\times39 (1⊕2)×39。删除 ( 1 , 2 ) (1,2) (1,2) ( 1 , 3 ) (1,3) (1,3) 两条边图包含三个连通块权值为 1 × 2 × 3 6 1\times2\times36 1×2×36。
所有方案权值的总和为 0 4 9 6 19 049619 049619。
【样例 #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_ii 1≤fii。
测试点编号 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 1A 5 5 5 1 0 5 10^5 105 1 1 1B 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 ≤7A 9 9 9 1 0 5 10^5 105 ≤ 7 \leq7 ≤7B 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 ≤109A 18 18 18 1 0 5 10^5 105 ≤ 1 0 9 \leq10^9 ≤109B 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 1i≤n f i i − 1 f_ii-1 fii−1。特殊性质 B保证对于任意 1 i ≤ n 1 i\le n 1i≤n f i 1 f_i1 fi1。 【提示】 ⊕ \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∗(sixorsj)
这样 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加起来即可 #includebits/stdc.h
using namespace std;#define ll long longll Mo 998244353;const int N 5e510;
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*10ch-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](1lli)%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;
}
