fork download
copy 
  1.  
  2.     #include <bits/stdc++.h>
  3.  
  4.     using namespace std;
  5.  
  6.     using ll = long long;
  7.     const int MOD = 1000000007; 
  8.     const int MOD2 =  998244353; 
  9.     const ll INF = 1e18;
  10.     const int MX = 1000001; //check the limits, dummy
  11.  
  12.  
  13.     ll modExp(ll base, ll power) {
  14.         if (power == 0) {
  15.             return 1;
  16.         } else {
  17.             ll cur = modExp(base, power / 2); cur = cur * cur; cur = cur % MOD;
  18.             if (power % 2 == 1) cur = cur * base;
  19.             cur = cur % MOD;
  20.             return cur;
  21.         }
  22.     }
  23.  
  24.     ll inv(ll base) {
  25.         return modExp(base, MOD-2);
  26.     }
  27.  
  28.  
  29.     ll mul(ll A, ll B) {
  30.         return (A*B)%MOD;
  31.     }
  32.  
  33.     ll add(ll A, ll B) {
  34.         return (A+B)%MOD;
  35.     }
  36.  
  37.     ll dvd(ll A, ll B) {
  38.         return mul(A, inv(B));
  39.     }
  40.  
  41.     ll sub(ll A, ll B) {
  42.         return (A-B+MOD)%MOD;
  43.     }
  44.     ll cielDiv(ll A , ll B) {
  45.         return (A + B - 1)/B;
  46.     } 
  47.  
  48.     ll* facs = new ll[MX];
  49.     ll* facInvs = new ll[MX];
  50.  
  51.     ll choose(ll a, ll b) {
  52.         if (b > a) return 0;
  53.         if (a < 0) return 0;
  54.         if (b < 0) return 0;
  55.         ll cur = facs[a];
  56.         cur = mul(cur, facInvs[b]);
  57.         cur = mul(cur, facInvs[a-b]);
  58.         return cur;
  59.     }
  60.  
  61.  
  62.  
  63.  
  64.  
  65.     void initFacs() {
  66.         facs[0] = 1; 
  67.         facInvs[0] = 1;
  68.         for (int i = 1 ; i < MX ; i ++ ) {
  69.             facs[i] = (facs[i-1] * i) % MOD;
  70.             facInvs[i] = inv(facs[i]);
  71.         }
  72.     }
  73.     const int maxn =  200005;    
  74.     int n; 
  75.  
  76.  
  77.     vector<int> adj[maxn]; 
  78.     int c[maxn];     
  79.  
  80.  
  81.     int dp[maxn];
  82.  
  83.  
  84.     void dfs(int a,int p ) {
  85.  
  86.         int v = c[a]; 
  87.  
  88.         for (int c : adj[a]) {
  89.             if (c == p) continue;
  90.  
  91.             dfs(c, a); 
  92.             dp[v] += max(dp[c], 0);             
  93.         }
  94.         dp[v] += v;
  95.     }
  96.     // wdo sthi  work we
  97.     void dfs2(int a,int p ) {
  98.         for (int c : adj[a]) {
  99.             if (c == p) continue;
  100.             int  toparentcost = dp[a] - max(dp[c] , 0); 
  101.             dp[c] = dp[c] +  toparentcost;          
  102.             dfs2(c, a);  
  103.         }
  104.     }
  105.  
  106.     int main()  {
  107.         ios_base::sync_with_stdio(0); cin.tie(0);  
  108.         int n ; cin >> n;
  109.         for (int i = 1 ; i <= n; i ++) {
  110.             int x;
  111.              cin >> x; 
  112.              if (x == 1) {
  113.                 c[i] = 1;
  114.              } else {
  115.                 c[i] = -1; 
  116.              }
  117.         } 
  118.         for (int i = 1 ; i <= n; i ++) {
  119.             cin >> c[i];
  120.         } 
  121.  
  122.         for (int i = 0 ; i < n- 1; i ++) {
  123.             int a , b ; cin >> a >> b; 
  124.             adj[a].push_back(b);
  125.             adj[b].push_back(a);
  126.         } 
  127.  
  128.         dfs(1,0);
  129.         dfs2(1,0);
  130.         for (int i = 1 ; i <= n; i ++) {
  131.             cout << dp[i] << ' '; 
  132.         }
  133.  
  134.  
  135.         return 0;
  136.     }
  137.  
Success #stdin #stdout 0.01s 9376KB
comments (?)
stdin
copy 
9
0 1 1 1 0 0 0 0 1
1 2
1 3
3 4
3 5
2 6
4 7
6 8
5 9
stdout
copy 
1 0 0 0 0 0 0 0 0
https://ideone.com/sPPBJu
language:
C++ (gcc 8.3)
created:
2 days 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!