CF E

題解：給你一棵n個節點的樹以及每個節點的權值，點權。dis(u,v)表示節點u到v路徑上的異或和，求不大于i的節點與i組成的有序對的距離的和（1<=i<=n）。

題解：樹形dp。因為XOR時每一位的操作都是獨立的，所以我們可以考慮將這些數的二進制按位拆分考慮。枚舉二進制的每一位對，統計對答案的貢獻。考慮當前的根節點為cur，那么：

dp[cur][0]表示以cur為根節點的異或值為0的路徑的數量。dp[cur][1]表示以cur為根節點的異或值為1的路徑的數量 。

代碼：

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e5 + 10;ll dp[N][2];ll a[N];ll ans = 0;vector<int> G[N];void dfs(int cur, int fa, int bit){    ll res = 0;    int b = (a[cur] >> bit) & 1;//取得當前的a[cur]在第bit位是0還是1    //這里好巧妙啊...     dp[cur][b] = 1;//初始化    dp[cur][b ^ 1] = 0;//初始化        for(auto v:G[cur]){    	if(v!=fa){    		dfs(v, cur, bit);        	res += dp[cur][0] * dp[v][1] + dp[cur][1] * dp[v][0];//統計子節點到cur的路徑上異或和，只需算1^0與0^1即可         	dp[cur][b ^ 0] += dp[v][0];//更新異或操作后的狀態值        	dp[cur][b ^ 1] += dp[v][1];//更新異或操作后的狀態值		}	}		/*    for (int i = 0; i<G[cur].size(); i++)	{        int v = G[cur][i];        if (v == fa)continue;        dfs(v, cur, bit);        q += dp[cur][0] * dp[v][1] + dp[cur][1] * dp[v][0];        dp[cur][b ^ 0] += dp[v][0];        dp[cur][b ^ 1] += dp[v][1];    }    */    ans += (res << bit);//更新答案}int main(){    int n, u, v;    cin >> n;    for (int i = 1; i <= n; i++){	    cin >> a[i];        ans += a[i];    }    for (int i = 0; i<n - 1; i++){        cin >> u >> v;        G[u].push_back(v);        G[v].push_back(u);    }    //由于權值最大為1e6，所以只需要枚舉到20位。2^20=1048576     for (int i = 0; i <= 20; i++)        dfs(1, 0, i);   return 0*PRintf("%I64d/n",ans);}/*51 2 3 4 51 22 33 43 552*/