fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define name "vestonluvto"
  4. const char* namein = name ".inp";
  5. const char* nameout = name ".out";
  6.  
  7. #define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  8. #define PI 3.141592653589793238462
  9. #define sz(x) ((int)(x).size())
  10. #define all(x) (x).begin(), (x).end()
  11. #define pb emplace_back
  12.  
  13. using namespace std;
  14.  
  15. #ifndef LOCAL
  16. #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  17. #else
  18. #define debug(x)
  19. #endif
  20.  
  21. void _print(int t) {cerr << t;}
  22. void _print(long long t) {cerr << t;}
  23. void _print(string t) {cerr << t;}
  24. void _print(char t) {cerr << t;}
  25. void _print(long double t) {cerr << t;}
  26. void _print(double t) {cerr << t;}
  27. void _print(unsigned long long t) {cerr << t;}
  28.  
  29. template <class T, class V> void _print(pair <T, V> p);
  30. template <class T> void _print(vector <T> v);
  31. template <class T> void _print(set <T> v);
  32. template <class T, class V> void _print(map <T, V> v);
  33. template <class T> void _print(multiset <T> v);
  34. template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.first); cerr << ","; _print(p.second); cerr << "}";}
  35. template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  36. template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  37. template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  38. template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
  39.  
  40. void homefix(){
  41.     #ifndef LOCAL
  42.     #endif
  43. }
  44.  
  45. void home(){
  46.      homefix();
  47.      if (fopen(namein, "r")) {
  48.         freopen(namein, "r", stdin);
  49.         freopen(nameout, "w", stdout);
  50.      }
  51. }
  52.  
  53. const int MAXN = 2e5 + 5;
  54. int n;
  55. long long a[MAXN];
  56. vector<int> dt[MAXN];
  57.  
  58. map<int, int> mp[MAXN];
  59. int max_freq[MAXN];
  60. long long sum_max[MAXN];
  61. long long ans[MAXN];
  62.  
  63. void nhap(){
  64.     cin >> n;
  65.     for(int i = 1; i <= n; i++) cin >> a[i];
  66.     for(int i = 1; i < n; i++){
  67.         int u, v;
  68.         cin >> u >> v;
  69.         dt[u].pb(v);
  70.         dt[v].pb(u);
  71.     }
  72. }
  73.  
  74. void dfs(int u, int p){
  75.     mp[u][a[u]] = 1;
  76.     max_freq[u] = 1;
  77.     sum_max[u] = a[u];
  78.  
  79.     for(int &v : dt[u]){
  80.         if(v == p) continue;
  81.         dfs(v, u);
  82.  
  83.         if(sz(mp[u]) < sz(mp[v])){
  84.             swap(mp[u], mp[v]);
  85.             swap(max_freq[u], max_freq[v]);
  86.             swap(sum_max[u], sum_max[v]);
  87.         }
  88.  
  89.         for(auto &k : mp[v]){
  90.             int col = k.first;
  91.             int f = k.second;
  92.             mp[u][col] += f;
  93.             int cur_f = mp[u][col];
  94.  
  95.             if(cur_f > max_freq[u]){
  96.                 max_freq[u] = cur_f;
  97.                 sum_max[u] = col;
  98.             } else if(cur_f == max_freq[u]){
  99.                 sum_max[u] += col;
  100.             }
  101.         }
  102.         mp[v].clear();
  103.     }
  104.     ans[u] = sum_max[u];
  105. }
  106.  
  107. void solve(){
  108.     dfs(1, 0);
  109.     for(int i = 1; i <= n; i++){
  110.         cout << ans[i] << ' ';
  111.     }
  112. }
  113.  
  114. int main(){
  115.     fastio(); 
  116.     home();
  117.     int t = 1;
  118.     while(t--){
  119.         nhap();
  120.         solve();
  121.     }
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 0.01s 19868KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cFaB0i
language:
C++14 (gcc 8.3)
created:
1 day 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!