fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "o"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. //#define pb push_back
  12. #define pb emplace_back
  13. #define fi first
  14. #define se second
  15. #define sz(s) (int)s.size()
  16. #define all(s) (s).begin(), (s).end()
  17. #define ms(a,x) memset(a, x, sizeof (a))
  18. #define cn continue
  19. #define re exit(0)
  20.  
  21. typedef long long ll;
  22. typedef unsigned long long ull;
  23. typedef long double ld;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vll;
  26. typedef pair<int, int> pii;
  27. typedef pair<ll, ll> pll;
  28. typedef vector<pii> vpii;
  29. typedef vector<pll> vpll;
  30.  
  31. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  32. ll ran(ll l, ll r)
  33. {
  34.     return uniform_int_distribution<ll> (l, r)(rng);
  35. }
  36.  
  37. inline void rf()
  38. {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(nullptr); cout.tie(nullptr);
  41.     if(fopen(file".inp","r"))
  42.     {
  43.         freopen(file".inp","r",stdin);
  44.         freopen(file".out","w",stdout);
  45.     }
  46. }
  47.  
  48. const int mod=1e9+7;
  49. const int maxn=1e5+15;
  50. const ll inf=5e16;
  51.  
  52. template<typename T> inline void add(T &x, const T &y)
  53. {
  54.     x+=y;
  55.     if(x>=mod) x-=mod;
  56.     if(x<0) x+=mod;
  57. }
  58.  
  59. template<typename T> inline bool maxi(T &a, T b)
  60. {
  61.     if(a>=b) return 0;
  62.     a=b; return 1;
  63. }
  64.  
  65. template<typename T> inline bool mini(T &a, T b)
  66. {
  67.     if(a<=b) return 0;
  68.     a=b; return 1;
  69. }
  70.  
  71. int n, ans[maxn];
  72. vi g[2][maxn];
  73. pii e[2][maxn];
  74. int st[2][maxn], ed[2][maxn], timer[2], tour[2][maxn];
  75. int sz[2][maxn], h[2][maxn], heavy[2][maxn];
  76.  
  77. struct fenwick
  78. {
  79.     int t[maxn];
  80.  
  81.     inline void upd(int x, int val)
  82.     {
  83.         for(; x<=n; x+=x&-x) t[x]+=val;
  84.     }
  85.  
  86.     inline int get(int x)
  87.     {
  88.         int ans=0;
  89.         for(; x>0; x-=x&-x) ans+=t[x];
  90.         return ans;
  91.     }
  92. } t;
  93.  
  94. void dfs(int u, int par, int id)
  95. {
  96.     sz[id][u]=1;
  97.     int mx=0;
  98.     heavy[id][u]=0; // *** khởi lại heavy ***
  99.     st[id][u]=++timer[id]; tour[id][timer[id]]=u;
  100.     for(auto v:g[id][u]) if(v!=par)
  101.     {
  102.         h[id][v]=h[id][u]+1;
  103.         dfs(v, u, id);
  104.         if(maxi(mx, sz[id][v])) heavy[id][u]=v;
  105.         sz[id][u]+=sz[id][v];
  106.     }
  107.     ed[id][u]=timer[id];
  108. }
  109.  
  110. void sack(int id, int u, int par, bool keep)
  111. {
  112.     for(auto v:g[id][u]) if(v!=par && v!=heavy[id][u]) sack(id, v, u, 0);
  113.     if(heavy[id][u]) sack(id, heavy[id][u], u, 1);
  114.  
  115.     // add current root u
  116.     t.upd(st[1-id][u], 1);
  117.  
  118.     // add all small-child subtrees
  119.     for(auto v:g[id][u]) if(v!=par && v!=heavy[id][u])
  120.     {
  121.         ff(i, st[id][v], ed[id][v])
  122.         {
  123.             int x=tour[id][i];
  124.             t.upd(st[1-id][x], 1);
  125.         }
  126.     }
  127.  
  128.     // compute answers for all edges of the other tree (1-id)
  129.     ff(i, 1, n-1)
  130.     {
  131.         int u1=e[1-id][i].fi, v1=e[1-id][i].se;
  132.         if(h[1-id][u1]<h[1-id][v1]) swap(u1, v1); // u1 is deeper -> subtree root
  133.  
  134.         int in = t.get(ed[1-id][u1]) - t.get(st[1-id][u1]-1);
  135.         int a = sz[id][u];
  136.         int c = sz[1-id][u1];
  137.  
  138.         int v1c = in;
  139.         int v2c = a - in;
  140.         int v3c = c - in;
  141.         int v4c = n - a - c + in;
  142.         int cnt = max( max(v1c, v2c), max(v3c, v4c) );
  143.         ++ans[cnt];
  144.     }
  145.  
  146.     if(!keep)
  147.     {
  148.         ff(i, st[id][u], ed[id][u])
  149.         {
  150.             int v=tour[id][i];
  151.             t.upd(st[1-id][v], -1);
  152.         }
  153.     }
  154. }
  155.  
  156. signed main()
  157. {
  158.     rf();
  159.     cin>>n;
  160.     // clear globals (an toàn)
  161.     ms(timer, 0);
  162.     ms(ans, 0);
  163.     ff(id, 0, 1)
  164.     {
  165.         ff(i, 1, n) { g[id][i].clear(); st[id][i]=ed[id][i]=0; sz[id][i]=0; h[id][i]=0; heavy[id][i]=0; }
  166.         ff(i, 1, n-1)
  167.         {
  168.             int u, v; cin>>u>>v;
  169.             e[id][i]={u, v};
  170.             g[id][u].pb(v); g[id][v].pb(u);
  171.         }
  172.         dfs(1, 0, id);
  173.     }
  174.  
  175.     ms(t.t, 0); // clear fenwick
  176.     sack(0, 1, 0, 1);
  177.     ff(i, 0, n) cout<<ans[i]<<ss;
  178.     re;
  179. }
  180.  
Success #stdin #stdout 0.01s 15212KB
comments (?)
stdin
copy 
7
6 3
1 4
4 5
4 7
2 6
6 4
6 3
1 4
4 5
4 7
2 6
6 4
stdout
copy 
0 0 0 6 6 20 10 0
https://ideone.com/49QxUK
language:
C++14 (gcc 8.3)
created:
20 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!