Codeforces 766E Mahmoud and a xor trip [二进制,]【数学+思维】

2019-11-09 21:15:48

字体：大中小

来源：转载

供稿：网友

题目连接:http://codeforces.com/contest/766/PRoblem/E ——————————————————————————. ——————————————————————————. 题目大意: 就是在一个生成树上求任意两点的距离的和,距离定义为两点间路上所有点权值的异或和,

解题思路:

想法就是将结果的异或和拆分成每一位的,就是对于二进制数上对于第i位,有多少个距离为1的路径,然后在总结果上+路径数(1<<i) $+路径数(1<<i)$ 即可,这样最多按二进制位数个的搜索一遍树就行了. cnt[][0]是以u为根0的个数,cnt[][1]同理.

听闻这题还有树分治和数dp的做法,有兴趣可以百度一发.

附本题代码 ——————————————————————————.

int a[N],b[N],cnt[N][2];vector<int >E[N];LL sum ;void dfs(int u,int fa){ cnt[u][0]=cnt[u][1]=0; cnt[u][b[u]]++; sum+=b[u]; int v; for(int i=0;i<E[u].size();i++){ v = E[u][i]; if(v==fa) continue; dfs(v,u); sum+=cnt[u][0]*cnt[v][1]+cnt[u][1]*cnt[v][0]; cnt[u][b[u]]+=cnt[v][0]; cnt[u][b[u]^1]+=cnt[v][1]; }}int main(){ int n,u,v; n = read(); Rep(i,1,n) a[i]=read(),E[i].clear(); Rep(i,2,n){ u=read(),v=read(); E[u].pb(v); E[v].pb(u); } LL ans = 0ll; Rep(i,0,20){ Rep(j,1,n){ if(a[j]&(1<<i)) b[j]=1; else b[j]=0; } sum = 0ll; dfs(1,-1); ans += sum*(1<<i); } printf("%I64d/n",ans); return 0;}

对于对树、图进行dfs的要好好练练总是搜不明白.

上一篇：转：Django 安全配置(setting.py)详解

下一篇：Leetcode 204. Count Primes