fork download
copy 
  1.  #include <bits/stdc++.h>
  2.     using namespace std;
  3.     #define pb push_back
  4.     typedef long long ll;
  5.     int k[1005];
  6.     int dp[1005][1025];
  7.     vector<int>adj[1005];
  8.  
  9.     int dfs(int ele,int par,int xorr,int flag,int len)
  10.     {
  11.  
  12.         int sum1=0,sum2=0,sum=0;
  13.         if(flag==1)
  14.         {
  15.             if(len==1)
  16.             {
  17.                 for(int i=0;i<adj[ele].size();i++)
  18.                 {
  19.                     if(adj[ele][i]!=par)
  20.                     {
  21.                         sum+=dfs(adj[ele][i],ele,xorr,0,xorr);
  22.                     }
  23.                 }
  24.             }
  25.             else
  26.             {
  27.                 for(int i=0;i<adj[ele].size();i++)
  28.                 {
  29.                     if(adj[ele][i] != par)
  30.                     {
  31.                         sum += dfs(adj[ele][i],ele,xorr,1,len-1);
  32.                     }
  33.                 }
  34.             }
  35.             return sum;
  36.         }
  37.         else
  38.         {
  39.  
  40.             if(dp[ele][xorr] != -1)
  41.             {
  42.                 return dp[ele][xorr];
  43.             }
  44.             int p = adj[ele].size();
  45.             for(int i=0;i<p;i++)
  46.             {
  47.                 if(adj[ele][i] != par)
  48.                 {
  49.                     sum1 += dfs(adj[ele][i],ele,xorr,0,xorr);
  50.                     int uu = (xorr^k[ele-1]);
  51.                     if(uu == 0)
  52.                     {
  53.                         sum2 += dfs(adj[ele][i],ele,uu,0,uu);
  54.                     }
  55.                     else
  56.                     {
  57.                         sum2 += dfs(adj[ele][i],ele,uu,1,uu);
  58.                     }
  59.                 }
  60.             }
  61.             sum2 += k[ele-1];
  62.             dp[ele][xorr] = max(sum1,sum2);
  63.             return dp[ele][xorr];
  64.         }
  65.     }
  66.     int main()
  67.     {
  68.         int n;
  69.         cin>>n;
  70.         assert(n>=1 && n<=1000);
  71.         for(int i=0;i<=1001;i++)
  72.         {
  73.             for(int j=0;j<=1200;j++)
  74.             {
  75.                 dp[i][j] = -1;
  76.             }
  77.         }
  78.         for(int i=0;i<n;i++)
  79.         {
  80.             cin>>k[i];
  81.             assert(k[i]>=0 && k[i]<=1023);
  82.         }
  83.         for(int i=1;i<=n-1;i++)
  84.         {
  85.             int x,y;
  86.             cin>>x>>y;
  87.             assert(x>=1 && x<=n);
  88.             assert(y>=1 && y<=n);
  89.             adj[x].pb(y);
  90.             adj[y].pb(x);
  91.         }
  92.         cout<<dfs(1,-1,0,0,0)<<endl;
  93.     }
Success #stdin #stdout 0s 19288KB
comments (?)
stdin
copy 
4
1 1 1 1
1 2
1 3
1 4
stdout
copy 
3
https://ideone.com/AZnhpN
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!