fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define n nnathw
  5. #define ll long long
  6. #define pb push_back
  7. #define MAX 200200
  8.  
  9. int n;
  10. vector<int> adj[MAX];
  11. int pos[MAX], head[MAX], treesize[MAX], depth[MAX], parent[MAX];
  12. int cnt = 0;
  13.  
  14. void nhap()
  15. {
  16.     cin >> n;
  17.     for(int i = 0; i<n-1; i++){
  18.         int a,b; cin >> a >> b;
  19.         adj[a].pb(b);
  20.         adj[b].pb(a);
  21.     }
  22.     depth[1] = 0;
  23.     parent[1] = 0;
  24. }
  25.  
  26. void dfs(int v, int par)
  27. {
  28.     treesize[v] = 1;
  29.     int index = -1;
  30.     int ans_index = -1;
  31.     for(int u : adj[v]){
  32.         ++index;
  33.         if(u == par) continue;
  34.         parent[u] = v;
  35.         depth[u] = depth[v] + 1;
  36.         dfs(u,v);
  37.         treesize[v] += treesize[u];
  38.         if(ans_index == -1 || treesize[u] > treesize[adj[v][ans_index]]) ans_index = index;
  39.     }
  40.     if(ans_index != -1 && ans_index != 0) swap(adj[v][0], adj[v][ans_index]);
  41. }
  42.  
  43. void decompose(int v, int par, int h)
  44. {
  45.     head[v] = h;
  46.     pos[v] = ++cnt;
  47.     for(int u : adj[v]){
  48.         if(u == par) continue;
  49.         if(u == adj[v][0]){
  50.             decompose(u,v,h);
  51.         }else{
  52.             decompose(u,v,u);
  53.         }
  54.     }
  55. }
  56.  
  57. void process()
  58. {
  59.     vector<int> a(n+2,0);
  60.     for(int i = 1; i<n; i++){
  61.         int u = i;
  62.         int v= i+1;
  63.         while(head[u] != head[v]){
  64.             if(depth[head[u]] < depth[head[v]]) swap(u,v);
  65.             a[pos[head[u]]]++;
  66.             a[pos[u] + 1]--;
  67.             u = parent[head[u]];
  68.         }
  69.         if(depth[u] > depth[v]) swap(u,v);
  70.         a[pos[u]]++;
  71.         a[pos[v] + 1]--;
  72.     }
  73.     for(int i = 1; i<=n; i++) a[i] = a[i-1] + a[i];
  74.     for(int i = 1; i<=n; i++) cout << a[pos[i]] << ' ';
  75. }
  76.  
  77. int main()
  78. {
  79.     ios_base::sync_with_stdio(0); cin.tie(0);
  80.     nhap();
  81.     dfs(1,-1);
  82.     decompose(1,-1,1);
  83.     process();
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0.01s 10420KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nYenWX
language:
C++14 (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!