fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #ifdef LOCAL
  6. #include "algo/debug.h"
  7. #else
  8. #define debug(...) 42
  9. #endif
  10.  
  11. template<class X, class Y>bool maximize(X &x, const Y &y){if(x < y) return x = y, true; return false;}
  12. template<class X, class Y>bool minimize(X &x, const Y &y){if(x > y) return x = y, true; return false;}
  13.  
  14. #define ll long long
  15. #define fi first
  16. #define se second
  17. #define pb push_back
  18. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  19. #define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; i--)
  20. #define REP(i, n) for(int i = 0, _n = (n); i < _n; i++)
  21. #define C make_pair
  22. #define MASK(i) (1LL << (i))
  23. #define TURN_ON(i, x) ((x) | MASK(i))
  24. #define TURN_OFF(i, x) ((x) & ~MASK(i))
  25. #define CNT(x) (__builtin_popcountll(x))
  26. #define get_bit(i, x) ((x) & MASK(i))
  27. #define REV(i, x) ((x) ^ MASK(i))
  28.  
  29. const ll mod = 1e9 + 7;
  30. const ll INF = 1e15;
  31. const int maxn = 1e5 + 5;
  32. typedef pair<int, int> pi;
  33. typedef pair<int, pair<int,int>> pii;
  34. typedef pair<ll, ll> pl;
  35. typedef pair<ll, pair<ll,ll>>pll;
  36.  
  37. const int MAXN = (int)2e5 + 5;
  38.  
  39. ll n, sz[MAXN], dist[MAXN], Allsum, cnt[MAXN], sum[MAXN], Allcnt;
  40. ll ans[MAXN];
  41. bool is_centroid[MAXN];
  42. vector<int>a[MAXN];
  43.  
  44. void DFS_1(int u, int par){
  45.     sz[u] = 1;
  46.     for(int v: a[u]) if(v != par && !is_centroid[v]){
  47.         DFS_1(v, u);
  48.         sz[u] += sz[v];
  49.     }
  50. }
  51. int find_centroid(int u, int par, int TreeSize){
  52.     for(int v: a[u]) if(v != par && !is_centroid[v] && sz[v] > (TreeSize / 2))
  53.         return find_centroid(v, u, TreeSize);
  54.     return u;
  55. }
  56. void DFS_2(int u, int par, int cha){
  57.     cnt[u] = 1;
  58.     Allcnt++;
  59.     for(int v: a[u]) if(v != par && !is_centroid[v]){
  60.         dist[v] = dist[u] + 1;
  61.         DFS_2(v, u, cha);
  62.         cnt[u] += cnt[v];
  63.     }
  64.     sum[cha] += cnt[u];
  65. }
  66. void DFS_3(int u, int par, int cha){
  67.     ans[u] = ans[u] + (Allcnt - cnt[cha]) * dist[u] + (Allsum - sum[cha]);
  68.     for(int v: a[u]) if(v != par && !is_centroid[v])
  69.         DFS_3(v, u, cha);
  70. }
  71. void reset(int u, int par){
  72.     cnt[u] = sum[u] = dist[u] = 0;
  73.     for(int v: a[u]) if(v != par && !is_centroid[v])
  74.         reset(v, u);
  75. }
  76. void build_centroid(int u){
  77.     DFS_1(u, -1);
  78.     int centroid = find_centroid(u, -1, sz[u]);
  79.     is_centroid[centroid] = 1;
  80.     Allsum = 0, Allcnt = 1;
  81.     for(int v: a[centroid]) if(!is_centroid[v]){
  82.         dist[v] = 1;
  83.         DFS_2(v, centroid, v);
  84.         Allsum += sum[v];
  85.     }
  86.     for(int v: a[centroid]) if(!is_centroid[v]){
  87.         DFS_3(v, centroid, v);
  88.         reset(v, centroid);
  89.     }
  90.     ans[centroid] += Allsum;
  91.     for(int v: a[centroid]) if(!is_centroid[v]){
  92.         build_centroid(v);
  93.     }
  94. }
  95. void nhap(){
  96.     cin >> n;
  97.     FOR(i, 1, n - 1){
  98.         int u, v; cin >> u >> v;
  99.         a[u].pb(v);
  100.         a[v].pb(u);
  101.     }
  102. }
  103. void solve(){
  104.     build_centroid(1);
  105.     FOR(i, 1, n) cout << ans[i] << " ";
  106. }
  107. int main(){
  108.     ios_base::sync_with_stdio(0);
  109.     cin.tie(0); cout.tie(0);
  110.     nhap();
  111.     solve();
  112.     return 0;
  113. }
  114.  
Success #stdin #stdout 0.01s 12708KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HOfrli
language:
C++14 (gcc 8.3)
created:
8 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!