题目链接:http://codeforces.com/contest/766/problem/E
Examples
input
3
1 2 3
1 2
2 3
out
10
题意:
给你一棵n个点的树,每个点有点权,求所有不同的路径异或和的总和
题解:
DP
任选一个root,设定dp[i][j][0]为以i为最高点的路径异或和中,二进制上第j为分别是0,1的数量
记录答案
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
const long long INF = 1e17+1LL;
const double Pi = acos(-1.0);
const int N = 1e5+, M = 1e3+, mod = 1e9+, inf = 2e9+;
int n,a[N];
LL dp[N][][],ans;
vector<int > G[N];
void dfs(int u,int fa) {
for(int i = ; i < ; ++i)
dp[u][i][(a[u]>>i)&] = ;
ans+=a[u];
for(int i = ; i < G[u].size(); ++i) {
int to = G[u][i];
if(to == fa) continue;
dfs(to,u);
for(int j = ; j < ; ++j) {
ans += 1LL*(<<j)*(dp[u][j][]*dp[to][j][] + dp[u][j][]*dp[to][j][]);
}
for(int j = ; j < ; ++j) {
int p = ((a[u]>>j)&);
dp[u][j][] += dp[to][j][p^],
dp[u][j][] += dp[to][j][p^];
}
}
}
int main() {
scanf("%d",&n);
for(int i = ; i <= n; ++i) scanf("%d",&a[i]);
for(int i = ; i < n; ++i) {
int x,y;
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(,-);
cout<<ans<<endl;
return ;
}