P7310 [COCI 2018/2019 #2] Deblo
题目描述
给定一个包含n nn个结点的树，其中每个结点都有一个权值。一条路径的权值定义为该路径经过的所有结点的权值异或后的结果。
你的任务是求出所有路径的权值之和。
输入格式
第一行输入正整数N NN，表示树的结点个数。
第二行输入N NN个用空格分隔的整数v i v_ivi，第i ii个整数表示结点i ii的权值。
接下来的N − 1 N-1N−1行，每行输入整数a j , b j a_j,b_jaj,bj，表示a j , b j a_j,b_jaj,bj之间有一条边。
输出格式
输出所有路径的权值之和。
输入输出样例 #1
输入 #1
3 1 2 3 1 2 2 3输出 #1
10输入输出样例 #2
输入 #2
5 2 3 4 2 1 1 2 1 3 3 4 3 5输出 #2
64输入输出样例 #3
输入 #3
6 5 4 1 3 3 3 3 1 3 5 4 3 4 2 2 6输出 #3
85说明/提示
样例 1 解释
路径1 → 1 1 \to 11→1的权值为1 11；
路径1 → 2 1 \to 21→2的权值为1 ⊕ 2 = 3 1⊕2=31⊕2=3；
路径1 → 3 1 \to 31→3的权值为1 ⊕ 2 ⊕ 3 = 0 1⊕2⊕3=01⊕2⊕3=0；
路径2 → 2 2 \to 22→2的权值为2 22；
路径2 → 3 2 \to 32→3的权值为2 ⊕ 3 = 1 2⊕3=12⊕3=1；
路径3 → 3 3 \to 33→3的权值为3 33。
所有路径的权值之和为1 + 3 + 0 + 2 + 1 + 3 = 10 1+3+0+2+1+3=101+3+0+2+1+3=10。
数据规模与约定
对于30 % 30\%30%的数据，N ≤ 200 N \le 200N≤200。
对于50 % 50\%50%的数据，N ≤ 1000 N \le 1000N≤1000。
对于另外20 % 20\%20%的数据，x = 1 , 2 , ⋯ , N − 1 x=1,2,\cdots,N-1x=1,2,⋯,N−1中的每个结点都和结点x + 1 x+1x+1之间有一条边。
对于100 % 100\%100%的数据，1 ≤ a j , b j ≤ N ≤ 10 5 1 \le a_j,b_j \le N \le 10^51≤aj,bj≤N≤105，0 ≤ v i ≤ 3 × 10 6 0 \le v_i \le 3 \times 10^60≤vi≤3×106。
说明
本题分值按 COCI 原题设置，满分90 9090。
题目译自 COCI2018-2019 CONTEST #2T3 Deblo。
C++实现
#include<bits/stdc++.h>usingnamespacestd;inlineintread(){intx=0,f=1;charch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();returnx*f;}#definelllonglongconstintmaxn=1e5+20;inta[maxn],n,head[maxn],idx,dp[maxn][2],mul[40];ll ans;structnode{intnxt,to;}e[maxn<<1];inlinevoidadd(intu,intv){e[++idx].to=v,e[idx].nxt=head[u],head[u]=idx;}voiddfs(intu,intfa,intw){for(inti=head[u];i;i=e[i].nxt){intv=e[i].to;if(v==fa)continue;dfs(v,u,w);ans+=1ll*dp[u][1]*dp[v][0]*mul[w]+1ll*dp[u][0]*dp[v][1]*mul[w];if(a[u]&1)dp[u][0]+=dp[v][1],dp[u][1]+=dp[v][0];elsedp[u][0]+=dp[v][0],dp[u][1]+=dp[v][1];}dp[u][a[u]&1]++;ans+=1ll*dp[u][1]*mul[w];}intmain(){mul[0]=1;for(inti=1;i<=30;i++)mul[i]=mul[i-1]*2;n=read();for(inti=1;i<=n;i++)a[i]=read();intu,v;for(inti=1;i<n;i++)u=read(),v=read(),add(u,v),add(v,u);for(inti=0;i<=30;i++){dfs(1,0,i);for(intj=1;j<=n;j++)a[j]>>=1,dp[j][0]=dp[j][1]=0;}printf("%lld\n",ans);return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
