【題目鏈接】:http://codeforces.com/contest/766/problem/E

【題意】

定義樹上任意兩點之間的距離為這條簡單路徑上經過的點;
那些點上的權值的所有異或;
求任意兩點之間的距離和;

【題解】

權值最大為1e6
所以每個點的權值的二進制形式最多20位左右;
則我們可以對權值的二進制形式的每一位獨立考慮;
我們枚舉第i位;
并且在計算的時候只考慮這第i位;
可以做樹形dp;
算出穿過當前這個節點的路徑(并且以其為lca->最高點)
異或和的二進制形式在第i為上權值為1的路徑的個數x;
則(1<<i)?x就是答案了;
累加這個答案就好;
這里穿過當前這個節點且路徑的距離(異或和)在第i位的權值為1；
也就是說剩余的節點,要么左邊異或和為0且右邊異或和為1或者是左邊疑惑和為1右邊疑惑和為0;同時為1或同時為0都不行;
記錄每個節點下到該節點的異或和第i位為0和1的路徑個數就好;這個很容易維護的;
當然因為有說起點和終點可以相同;所以一開始累加a[i]值;

【完整代碼】

#include <bits/stdc++.h> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define LL long long #define rep1(i,a,b) for (int i = a;i <= b;i++) #define rep2(i,a,b) for (int i = a;i >= b;i--) #define mp make_pair #define ps push_back #define fi first #define se second #define rei(x) scanf("%d",&x) #define rel(x) scanf("%lld",&x) #define ref(x) scanf("%lf",&x)typedef pair<int, int> pii; typedef pair<LL, LL> pll;const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 }; const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 }; const double pi = acos(-1.0); const int N = 1e5+100;int n,a[N],bit; LL ans = 0,cnt[N][2]; vector <int> G[N];void dfs(int x, int fa) {int t = (a[x] >> bit) & 1;cnt[x][t] = 1, cnt[x][1 - t] = 0;for (int y : G[x]){if (y == fa) continue;dfs(y, x);ans += ((cnt[x][0] * cnt[y][1] + cnt[x][1] * cnt[y][0])<<bit);cnt[x][t ^ 1] += cnt[y][1];cnt[x][t ^ 0] += cnt[y][0];} }int main(){//freopen("F:\\rush.txt", "r", stdin);rei(n);rep1(i, 1, n) rei(a[i]),ans+=a[i];rep1(i, 1, n - 1) {int x, y;rei(x), rei(y);G[x].ps(y), G[y].ps(x);}for (bit = 0;bit <= 22;bit++) dfs(1, 0);printf("%lld\n", ans);//printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);return 0; }

轉載于:https://www.cnblogs.com/AWCXV/p/7626477.html

總結

以上是生活随笔為你收集整理的【codeforces 766E】Mahmoud and a xor trip的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。