首页 > 代码库 > codeforces 766E Mahmoud and a xor trip

codeforces 766E Mahmoud and a xor trip

2024-09-03 14:45:35   208人阅读

题目链接：http://codeforces.com/problemset/problem/766/E

大意，给出一个$n$个点的树，每个点都有一个权值，令$Disx$为$u$到$v$路径上的异或和求：

$${\sum _{i=1}^{n-1}\sum _{j=i}^{n}Disx(i,j)}$$

 

 枚举我当前处理的是这个二进制位上第$k$位的值,就只需要统计每个点的子树中有多少个点到当前点的第$k$位的异或和为$0$，为$1$的分别有多少个，统计答案即可。
 
 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 100010010 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);12 llg n,m,k,wei,val[maxn],ans;13 vector<llg>a[maxn];14 15 struct node16 {17     llg v1,v2;18 };19 20 void init()21 {22     cin>>n;23     for (llg i=1;i<=n;i++) scanf("%lld",&val[i]),ans+=val[i];24     llg x,y;25     for (llg i=1;i<n;i++)26     {27         scanf("%lld%lld",&x,&y);28         a[x].push_back(y),a[y].push_back(x);29     }30 }31 32 node dfs(llg x,llg fa)33 {34     llg w=a[x].size(),v;35     node now;36     now.v1=now.v2=0;37     if (val[x]&wei) now.v1=1;else now.v2=1;38     for (llg i=0;i<w;i++) 39     {40           v=a[x][i];41         if (v==fa) continue;42         node ne=dfs(v,x);43         ans+=now.v1*ne.v2*wei,ans+=now.v2*ne.v1*wei;44         if (val[x]&wei) now.v1+=ne.v2,now.v2+=ne.v1; else now.v1+=ne.v1,now.v2+=ne.v2;     45     }46     return now;47 }48 49 int main()50 {51     yyj("E");52     init();53     for (k=0;k<=20;k++)54     {55         wei=(1<<k);56         dfs(1,-1);57     }58     cout<<ans;59     return 0;60 }

 

codeforces 766E Mahmoud and a xor trip


联系
我们