Guest User

Untitled

a guest
Feb 7th, 2017
1,835
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <string.h>
  4. #include <vector>
  5. using namespace std;
  6. vector<int> v[100005];
  7. int arr[100005][25];
  8. long long dp[100005][25][2],ans[25];
  9. void dfs(int node,int pnode)
  10. {
  11.     long long s[25][2];
  12.     memset(s,0,sizeof(s));
  13.     for (int i=0;i<25;i++)
  14.     dp[node][i][arr[node][i]]=1;
  15.     for (int i=0;i<v[node].size();i++)
  16.     {
  17.         if (v[node][i]!=pnode)
  18.         {
  19.             dfs(v[node][i],node);
  20.             for (int j=0;j<25;j++)
  21.             {
  22.                 for (int x=0;x<2;x++)
  23.                 {
  24.                     dp[node][j][x]+=dp[v[node][i]][j][x^arr[node][j]];
  25.                     s[j][x]+=dp[v[node][i]][j][x];
  26.                 }
  27.             }
  28.         }
  29.     }
  30.     for (int j=0;j<25;j++)
  31.     {
  32.         long long x0=0,x1=0;
  33.         for (int i=0;i<v[node].size();i++)
  34.         {
  35.             if (v[node][i]!=pnode)
  36.             {
  37.                 x0+=(s[j][1]-dp[v[node][i]][j][1])*dp[v[node][i]][j][1]+(s[j][0]-dp[v[node][i]][j][0])*dp[v[node][i]][j][0];
  38.                 x1+=(s[j][1]-dp[v[node][i]][j][1])*dp[v[node][i]][j][0]+(s[j][0]-dp[v[node][i]][j][0])*dp[v[node][i]][j][1];
  39.             }
  40.         }
  41.         if (arr[node][j])
  42.         ans[j]+=x0/2;
  43.         else
  44.         ans[j]+=x1/2;
  45.     }
  46.     for (int j=0;j<25;j++)
  47.     ans[j]+=dp[node][j][1];
  48. }
  49. int main()
  50. {
  51.     int n;
  52.     cin >> n;
  53.     for (int i=1;i<=n;i++)
  54.     {
  55.         int a;
  56.         cin >> a;
  57.         for (int x=0;x<25;x++)
  58.         arr[i][x]=(bool)(a&(1<<x));
  59.     }
  60.     for (int i=1;i<n;i++)
  61.     {
  62.         int a,b;
  63.         cin >> a >> b;
  64.         v[a].push_back(b);
  65.         v[b].push_back(a);
  66.     }
  67.     dfs(1,0);
  68.     long long res=0;
  69.     for (int i=0;i<25;i++)
  70.     res+=(ans[i]*(1LL<<i));
  71.     cout<< res << endl;
  72. }
RAW Paste Data