[Codeforces] 766E. Mahmoud and a xor trip

題目連結:http://codeforces.com/problemset/problem/766/E

---

貌似是某種樹DP的東東，看到xor就要先想到把bit拆開，這樣的話問題就被轉化成說給你一堆0, 1的節點，問你所有路徑的和。這樣的話有個好處就是，因為只有0跟1，所以我們其實只要計算他的奇偶，然後偶爾交換一下之類的。接下來發現要枚舉所有路徑，其實枚舉lca就好了，所以就先走下去，把子樹算一算，之後提上來的時候稍微看一下自己是0還是1再把大家乘一乘之類的就好了。(想睡覺，可能有點不知所云

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef pair<int,int> PII;
#define FF first
#define SS second
#define PB push_back
const int N = 100000 + 5;

int arr[N];
vector<int> G[N];
lld ans = 0;

PII dfs(int,int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=1;i<=n;i++) cin>>arr[i];
	for(int i=0;i<n-1;i++){
		int u, v; cin>>u>>v;
		G[u].PB(v);
		G[v].PB(u);
	}
	for(int i=0;i<20;i++) dfs(1, 1, i);
	cout<<ans<<'\n';
	return 0;
}

PII dfs(int w, int f, int d){
	queue<PII> qq;
	PII ret = {0, 0};
	for(auto i: G[w]){
		if(i==f) continue;
		PII sub = dfs(i, w, d);
		qq.push(sub);
		ret.FF += sub.FF;
		ret.SS += sub.SS;
	}
	lld cnt = 0;
	while(!qq.empty()){
		auto cur = qq.front(); qq.pop();
		if(arr[w] & (1<<d)){
			cnt += (lld)(cur.FF * (ret.FF-cur.FF));
			cnt += (lld)(cur.SS * (ret.SS-cur.SS));
		}else{
			cnt += (lld)(cur.SS * (ret.FF-cur.FF));
			cnt += (lld)(cur.FF * (ret.SS-cur.SS));
		}
	}
	ans += (cnt/2)<<d;
	ret.FF++;
	if(arr[w] & (1<<d)) swap(ret.FF, ret.SS);
	ans += (lld)ret.SS<<d;
	return ret;
}