fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ____AnhKietSS____ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define NamDinh signed
  5. #define ii pair<int,int>
  6. #define ll long long
  7. #define foru(i,d,c) for(int i=(d);i<=(c);i++)
  8. #define ford(i,d,c) for(int i=(d);i>=(c);i--)
  9. #define fi first
  10. #define se second
  11. #define pb push_back
  12.  
  13. using namespace std;
  14.  
  15. const int N = 200005;
  16.  
  17. vector<int> a[N];
  18. int p[N];
  19. ll s[N];
  20. ll w[N];
  21. ll sum;
  22. ll ans[N];
  23.  
  24. void dfs(int u,int par)
  25. {
  26.     p[u] = par;
  27.     s[u] = w[u];
  28.  
  29.     for(int v : a[u])
  30.     {
  31.         if(v == par) continue;
  32.  
  33.         dfs(v,u);
  34.  
  35.         s[u] += s[v];
  36.     }
  37. }
  38.  
  39. void solve(int u)
  40. {
  41.     ans[u] = sum;
  42.  
  43.     for(int v : a[u])
  44.     {
  45.         if(p[v] == u)
  46.             ans[u] = max(ans[u],s[v]);
  47.         else
  48.             ans[u] = max(ans[u],sum-s[u]);
  49.     }
  50. }
  51.  
  52. NamDinh main()
  53. {
  54.     ____AnhKietSS____
  55.  
  56.     int n;
  57.     cin >> n;
  58.  
  59.     foru(i,1,n)
  60.     {
  61.         int x;
  62.         cin >> x;
  63.  
  64.         if(x == 1)
  65.             w[i] = 1;
  66.         else
  67.             w[i] = -1;
  68.  
  69.         sum += w[i];
  70.     }
  71.  
  72.     foru(i,1,n-1)
  73.     {
  74.         int u,v;
  75.         cin >> u >> v;
  76.  
  77.         a[u].pb(v);
  78.         a[v].pb(u);
  79.     }
  80.  
  81.     dfs(1,0);
  82.  
  83.     foru(i,1,n)
  84.         solve(i);
  85.  
  86.     foru(i,1,n)
  87.         cout << ans[i] << ' ';
  88.  
  89.     return 0;
  90. }
Success #stdin #stdout 0.01s 12996KB
comments (?)
stdin
copy 
4 
0 0 1 0 
1 2
 1 3
1 4
stdout
copy 
1 -1 -2 -1
https://ideone.com/yctVaH
language:
C++ (gcc 8.3)
created:
3 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!