题解：
二营长！你他娘的意大利炮呢？
dp[i][j][0]: 从i，跋涉到以i为根的子树的每一个节点，在第j个数位上一共产生了多少个0。
dp[i][j][1]: 从i，跋涉到以i为根的子树的每一个节点，在第j个数位上一共产生了多少个1。
转移式：(cur为i的儿子，t = (a[i]>>j)&1）
dp[i][j][0^t] += dp[cur][j][0];
dp[i][j][1^t] += dp[cur][j][1];
初始化:
dp[i][j][0] = (t==0);
dp[i][j][1] = (t==1);
跑一遍dfs，意大利炮充能[MAX]!
我们接下来求以节点x为rank最小点的路径给答案的贡献。
这个地方需要维护，关于x的儿子のdp数组的前缀和。
而预处理时的转移式，恰好做到了这一点。
所以，加上一个式子，在dfs过程，就能计算答案。
code:
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
typedef long long LL;
const int NICO = 100000 + 10;
int n, a[NICO];
vector<int> vec[NICO];
int dp[NICO][31][2];LL res;
void dfs(int x, int par)
{
for(int i=0;i<30;i++)
{
if((1<<i)&a[x]) dp[x][i][1] = 1;
else dp[x][i][0] = 1;
}
for(int i=0;i<vec[x].size();i++)
{
int cur = vec[x][i];
if(cur == par) continue;
dfs(cur, x);
for(int j=0;j<30;j++)
{
res += ((LL)dp[cur][j][0]*dp[x][j][1] + (LL)dp[cur][j][1]*dp[x][j][0]) << j;//请机智の读者自行思考该式。
int t = (a[x]>>j)&1;
dp[x][j][0^t] += dp[cur][j][0];
dp[x][j][1^t] += dp[cur][j][1];
}
}
}
int main()
{
scanf("%d", &n);
for(int i=1;i<=n;i++)
{
scanf("%d", &a[i]);
res += a[i]; //长度为0的路径还没考虑！
}
for(int i=1;i<n;i++)
{
int u, v;
scanf("%d %d", &u, &v);
vec[u].push_back(v);
vec[v].push_back(u);
}
dfs(1, 0);
cout << res << endl;
}
比赛的时候，意识到了这题得从每一个数位的角度来考虑，但被两点之间的公共祖先怼得想咬人！(? ?′?`? ?)
2333333。总之，这个题的预处理过程挺值得回味的。看来，举步维艰之时架好意大利炮，的确能扭转战局啊！
CF766 E. Mahmoud and a xor trip [预处理][树形dp]
原文：http://www.cnblogs.com/RUSH-D-CAT/p/6395007.html