fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define len(s) (int)s.size()
  4. #define pb push_back
  5. #define fi first
  6. #define se second
  7. #define MASK(x) ((1LL)<<(x))
  8. #define BIT(x,i) (((x) >>(i))&(1LL))
  9. #define ii pair<int,int>
  10. #define OpenFile(Name) if (fopen(Name".inp", "r")) freopen(Name".inp","r",stdin),freopen(Name".out","w",stdout);
  11. using namespace std;
  12.  
  13. int dx[4]={0,1,0,-1};
  14. int dy[4]={1,0,-1,0};
  15.  
  16. ll K=0x3f,MOD=1e9+7;
  17. const int N=1e6+5,M=1e3+3,base=31;
  18.  
  19. ///____________________________________________________________________________________________________________________________
  20.  
  21. int n,tin[N],tout[N],sz[N],c[N],Timer=0,Node[N],cnt[N],m;
  22. vector<int> a[N];
  23. ll res[N],dem=0,sum[N];
  24.  
  25.  
  26. void dfs(int u,int p=-1){
  27.     tin[u]=++Timer;
  28.     Node[Timer]=u;
  29.     sz[u]=1;
  30.  
  31.     for (int v:a[u])
  32.     if (v!=p) {
  33.         dfs(v,u);
  34.         sz[u]+=sz[v];
  35.     }
  36.  
  37.     tout[u]=Timer;
  38. }
  39.  
  40. void add(int u){
  41.     //int x=c[u];
  42.     sum[cnt[c[u]]]-=c[u];
  43.     cnt[c[u]]++;
  44.     sum[cnt[c[u]]]+=c[u];
  45.     m=max(m,cnt[c[u]]);
  46. }
  47.  
  48. void del(int u){
  49.     sum[cnt[c[u]]]-=c[u];
  50.     cnt[c[u]]--;
  51.     sum[cnt[c[u]]]+=c[u];
  52.     if (sum[m]==0) m--;
  53. }
  54.  
  55. void sack(int u,int p=-1,int keep=0){
  56.     int bigC=-1;
  57.  
  58.     for (int v:a[u])
  59.     if (v!=p)
  60.         if (bigC==-1 && sz[bigC]<sz[v]) bigC=v;
  61.  
  62.     for (int v:a[u])
  63.     if (v!=p && v!=bigC) sack(v,u);
  64.     if (bigC!=-1) sack(bigC,u,1);
  65.  
  66.     add(u);
  67.     for (int v:a[u])
  68.     if (v!=p && v!=bigC) {
  69.         for (int i=tin[v];i<=tout[v];i++) add(Node[i]);
  70.     }
  71.  
  72.     res[u]=sum[m];
  73.     if (!keep)
  74.     for (int i=tin[u];i<=tout[u];i++) del(Node[i]);
  75. }
  76.  
  77.  
  78.  
  79. signed main() {
  80.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  81.     OpenFile("TASK");
  82.  
  83.     cin>>n;
  84.     for (int i=1;i<=n;i++) cin>>c[i];
  85.  
  86.     for (int i=1;i<n;i++) {
  87.         int u,v; cin>>u>>v;
  88.         a[u].pb(v);
  89.         a[v].pb(u);
  90.     }
  91.  
  92.     for (int i=1;i<=n;i++) sum[0]+=c[i];
  93.     dfs(1);
  94.     sack(1);
  95.     for (int i=1;i<=n;i++) cout<<res[i]<<' ';
  96.  
  97.  
  98.  
  99.     return 0;
  100. }
  101.  
Success #stdin #stdout 0.01s 34340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DDbKig
language:
C++14 (clang 8.0)
created:
11 hours 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!