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.     void initFacs() {
  65.         facs[0] = 1; 
  66.         facInvs[0] = 1;
  67.         for (int i = 1 ; i < MX ; i ++ ) {
  68.             facs[i] = (facs[i-1] * i) % MOD;
  69.             facInvs[i] = inv(facs[i]);
  70.         }
  71.     }
  72.  
  73.     int n;
  74.     const int maxn = 200001;
  75.     ll arr[maxn];
  76.     ll res[maxn];
  77.     vector<ll> adj[maxn]; 
  78.     ll s[maxn];
  79.     ll d[maxn]; 
  80.     void dfs(int a , int p) { 
  81.         s[a] = 1; 
  82.         d[a] = 0; 
  83.         for (ll c : adj[a]) {
  84.             if (c == p)continue;
  85.             dfs(c,a);
  86.             s[a] += s[c]; 
  87.             d[a] += s[c] +  d[c];
  88.         }
  89.     }
  90.  
  91.     void dfs2(int a, int p,ll prev ) {
  92.         res[a] = arr[a] * (d[a] + prev + (n - s[a]));
  93.         for (ll c : adj[a]) {
  94.             if (c == p)continue;
  95.             dfs2(c,a,prev + (n - s[a]) + (d[a] - s[c] - d[c]));
  96.         }
  97.     }    
  98.  
  99.     int main()  {
  100.         ios_base::sync_with_stdio(0); cin.tie(0);  
  101.         cin >> n;
  102.         for (int i = 1 ; i <= n; i ++) {
  103.             cin >> arr[i]; 
  104.         }
  105.  
  106.         for (int i =  0 ; i < n- 1; i ++) {
  107.             ll a ,b ;cin >> a >> b; 
  108.             adj[a].push_back(b);
  109.             adj[b].push_back(a);
  110.         }
  111.  
  112.  
  113.         dfs(1,-1);
  114.         dfs2(1,-1,0 ); 
  115.         ll currm = -1; 
  116.         for (int i = 1; i <= n ; i++) {
  117.             currm = max(currm , res[i]);
  118.         }
  119.         cout << currm<< endl; 
  120.         return 0;
  121.     }
  122.  
Success #stdin #stdout 0.01s 11864KB
comments (?)
stdin
copy 
8
9 4 1 7 10 1 6 5
1 2
2 3
1 4
1 5
5 6
5 7
5 8
stdout
copy 
119
https://ideone.com/aBRK5r
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!