fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct BIT {
  5.     int n;
  6.     vector<long long> f;
  7.     BIT() {}
  8.     BIT(int n): n(n), f(n+2,0) {}
  9.     void add1(int i, long long v){ for(; i<=n; i+=i&-i) f[i]+=v; }
  10.     void range_add(int l,int r,long long v){
  11.         if(l>r) return;
  12.         add1(l,v);
  13.         add1(r+1,-v);
  14.     }
  15.     long long sum(int i){ long long s=0; for(; i>0; i-=i&-i) s+=f[i]; return s; }
  16. };
  17.  
  18. int n;
  19. vector<vector<int>> g1, g2;
  20.  
  21. struct Info {
  22.     vector<int> tin, tout, sz, par;
  23.     vector<vector<int>> children;
  24.     int timer=0;
  25. };
  26.  
  27. void dfs_build(int u, int p, vector<vector<int>>& g, Info& I){
  28.     I.par[u]=p;
  29.     I.tin[u]=++I.timer;
  30.     I.sz[u]=1;
  31.     for(int v: g[u]) if(v!=p){
  32.         I.children[u].push_back(v);
  33.         dfs_build(v,u,g,I);
  34.         I.sz[u]+=I.sz[v];
  35.     }
  36.     I.tout[u]=I.timer;
  37. }
  38.  
  39. struct Op { int y1,y2; int d; };
  40. vector<vector<Op>> eventsX;
  41.  
  42. inline void addRect(int Lx,int Rx,int Ly,int Ry,int delta){
  43.     if(Lx>Rx || Ly>Ry) return;
  44.     eventsX[Lx].push_back({Ly,Ry,delta});
  45.     eventsX[Rx+1].push_back({Ly,Ry,-delta});
  46. }
  47.  
  48. int main(){
  49.     ios::sync_with_stdio(false);
  50.     cin.tie(nullptr);
  51.     if(!(cin>>n)) return 0;
  52.     g1.assign(n+1,{}); g2.assign(n+1,{});
  53.     for(int i=0;i<n-1;i++){ int u,v; cin>>u>>v; g1[u].push_back(v); g1[v].push_back(u); }
  54.     for(int i=0;i<n-1;i++){ int u,v; cin>>u>>v; g2[u].push_back(v); g2[v].push_back(u); }
  55.  
  56.     Info A,B;
  57.     A.tin.assign(n+1,0); A.tout.assign(n+1,0); A.sz.assign(n+1,0); A.par.assign(n+1,0); A.children.assign(n+1,{});
  58.     B.tin.assign(n+1,0); B.tout.assign(n+1,0); B.sz.assign(n+1,0); B.par.assign(n+1,0); B.children.assign(n+1,{});
  59.  
  60.     dfs_build(1,0,g1,A);
  61.     dfs_build(1,0,g2,B);
  62.  
  63.     eventsX.assign(n+3,{});
  64.  
  65.     for(int x=1;x<=n;x++){
  66.         if(A.sz[x]>B.sz[x]){
  67.             addRect(1,A.tin[x]-1,1,B.tin[x]-1,1);
  68.             addRect(1,A.tin[x]-1,B.tout[x]+1,n,1);
  69.             addRect(A.tout[x]+1,n,1,B.tin[x]-1,1);
  70.             addRect(A.tout[x]+1,n,B.tout[x]+1,n,1);
  71.         }
  72.     }
  73.  
  74.     for(int x=1;x<=n;x++){
  75.         int thr = n - B.sz[x];
  76.         for(int c: A.children[x]){
  77.             if(A.sz[c] < thr){
  78.                 addRect(A.tin[c],A.tout[c],1,B.tin[x]-1,1);
  79.                 addRect(A.tin[c],A.tout[c],B.tout[x]+1,n,1);
  80.             }
  81.         }
  82.     }
  83.  
  84.     for(int x=1;x<=n;x++){
  85.         int thr2 = n - A.sz[x];
  86.         for(int c: B.children[x]){
  87.             if(B.sz[c] > thr2){
  88.                 addRect(1,A.tin[x]-1,B.tin[c],B.tout[c],1);
  89.                 addRect(A.tout[x]+1,n,B.tin[c],B.tout[c],1);
  90.             }
  91.         }
  92.     }
  93.  
  94.     for(int x=1;x<=n;x++){
  95.         auto &c1 = A.children[x];
  96.         auto &c2 = B.children[x];
  97.         if(c1.empty() || c2.empty()) continue;
  98.         vector<int> o1=c1, o2=c2;
  99.         sort(o1.begin(),o1.end(),[&](int u,int v){ return A.sz[u]<A.sz[v]; });
  100.         sort(o2.begin(),o2.end(),[&](int u,int v){ return B.sz[u]<B.sz[v]; });
  101.         if(o1.size()<=o2.size()){
  102.             for(int u: o1){
  103.                 int s=A.sz[u];
  104.                 int j = upper_bound(o2.begin(),o2.end(),s,[&](int val,int node){ return val < B.sz[node]; }) - o2.begin();
  105.                 for(int k=j;k<(int)o2.size();k++){
  106.                     int v=o2[k];
  107.                     addRect(A.tin[u],A.tout[u],B.tin[v],B.tout[v],1);
  108.                 }
  109.             }
  110.         }else{
  111.             for(int v: o2){
  112.                 int t=B.sz[v];
  113.                 int i = lower_bound(o1.begin(),o1.end(),t,[&](int node,int val){ return A.sz[node] < val; }) - o1.begin();
  114.                 for(int k=i;k<(int)o1.size();k++){
  115.                     int u=o1[k];
  116.                     addRect(A.tin[u],A.tout[u],B.tin[v],B.tout[v],1);
  117.                 }
  118.             }
  119.         }
  120.     }
  121.  
  122.     BIT bit(n+2);
  123.     vector<long long> ans(n+1,0);
  124.     vector<int> invTin1(n+1,0);
  125.     for(int v=1;v<=n;v++) invTin1[A.tin[v]]=v;
  126.  
  127.     for(int X=1; X<=n; X++){
  128.         for(auto &e: eventsX[X]) bit.range_add(e.y1,e.y2,e.d);
  129.         int v = invTin1[X];
  130.         ans[v]=bit.sum(B.tin[v]);
  131.     }
  132.  
  133.     for(int v=1;v<=n;v++){
  134.         if(v>1) cout<<' ';
  135.         cout<<ans[v];
  136.     }
  137.     cout<<"\n";
  138.     return 0;
  139. }
  140.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
5
1 4
2 4
3 2
3 5
3 1
2 3
5 2
4 2
stdout 
1 1 1 0 2
https://ideone.com/yUcU73
language:
C++14 (gcc 8.3)
created:
19 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!