題目連接:http://codeforces.com/contest/766/PRoblem/E ——————————————————————————. ——————————————————————————. 題目大意: 就是在一個生成樹上求任意兩點的距離的和,距離定義為兩點間路上所有點權值的異或和,
解題思路:
想法就是將結果的異或和拆分成每一位的,就是對于二進制數上對于第i位,有多少個距離為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的要好好練練 總是搜不明白.
新聞熱點
疑難解答
