题目链接：

Examples

input

3

1 2 3

1 2

2 3

out

10

 

题意：

　　给你一棵n个点的树，每个点有点权，求所有不同的路径异或和的总和

题解：

　　DP

　　任选一个root，设定dp[i][j][0]为以i为最高点的路径异或和中，二进制上第j为分别是0，1的数量

　　记录答案

 

#include
       
        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
        
         #define MP make_pairtypedef long long LL;const long long INF = 1e17+1LL;const double Pi = acos(-1.0);const int N = 1e5+10, M = 1e3+20, mod = 1e9+7, inf = 2e9+10;int n,a[N];LL dp[N][40][2],ans;vector
         
           G[N];void dfs(int u,int fa) {    for(int i = 0; i < 30; ++i)        dp[u][i][(a[u]>>i)&1] = 1;    ans+=a[u];    for(int i = 0 ; i < G[u].size(); ++i) {        int to = G[u][i];        if(to == fa) continue;        dfs(to,u);        for(int j = 0; j < 30; ++j) {            ans += 1LL*(1<
          
           >j)&1);            dp[u][j][1] += dp[to][j][p^1],            dp[u][j][0] += dp[to][j][p^0];        }    }}int main() {    scanf("%d",&n);    for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);    for(int i = 1; i < n; ++i) {        int x,y;        scanf("%d%d",&x,&y);        G[x].push_back(y);        G[y].push_back(x);    }    dfs(1,-1);    cout<
           
            <