yicongli

LG3233

Mar 4th, 2019
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.41 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=300005;
  17.  
  18. vector<int>G[N];
  19. vector<int>G2[N];
  20.  
  21. int ac[N][20];
  22. int dep[N];
  23. int siz[N];
  24. int dfn[N];
  25. int dfs_clock;
  26.  
  27. void dfs1(int x,int f){
  28.     siz[x]=1;
  29.     dep[x]=dep[f]+1;
  30.     ac[x][0]=f;
  31.     dfn[x]=++dfs_clock;
  32.     for(int i=1;(ac[x][i]=ac[ac[x][i-1]][i-1]);++i);
  33.     for(int i=0;i<G[x].size();++i){
  34.         int v=G[x][i];
  35.         if(v==f)continue;
  36.         dfs1(v,x);
  37.         siz[x]+=siz[v];
  38.     }
  39. }
  40.  
  41. inline int lca(int u,int v){
  42.     if(dep[u]<dep[v])swap(u,v);
  43.     for(int i=18;~i;--i){
  44.         if(dep[ac[u][i]]>=dep[v])u=ac[u][i];
  45.     }
  46.     if(u==v)return u;
  47.     for(int i=18;~i;--i){
  48.         if(ac[u][i]!=ac[v][i])u=ac[u][i],v=ac[v][i];
  49.     }
  50.     return ac[u][0];
  51. }
  52.  
  53. inline bool cmp(const int &a,const int &b){
  54.     return dfn[a]<dfn[b];
  55. }
  56.  
  57. int top;
  58. int sta[N];
  59.  
  60. inline void addedge(int u,int v){
  61.     G2[u].push_back(v);
  62. //  G2[v].push_back(u);
  63. }
  64.  
  65. inline void ins(int x){
  66.     if(top==0){
  67.         sta[++top]=x;
  68.         return ;
  69.     }
  70.     int t=lca(x,sta[top]);
  71.     while(top>1&&dep[sta[top-1]]>=dep[t]){
  72.         addedge(sta[top-1],sta[top]);
  73.         top--;
  74.     }
  75.     if(sta[top]!=t){
  76.         addedge(t,sta[top]);
  77.         sta[top]=t;
  78.     }
  79.     sta[++top]=x;
  80. }
  81.  
  82. inline int dist(int u,int v){
  83.     return dep[u]+dep[v]-2*dep[lca(u,v)];
  84. }
  85.  
  86. int ID[N];
  87. int BL[N];
  88. int tot;
  89. int tmp[N];
  90. int Left[N];
  91. int Ans[N];
  92.  
  93. void dfs2(int x){
  94.     Left[x]=siz[x];
  95.     tmp[++tot]=x;
  96.     for(int i=0;i<G2[x].size();++i){
  97.         int v=G2[x][i];
  98.         dfs2(v);
  99.         if(!BL[v])continue;
  100.         if(!BL[x])BL[x]=BL[v];
  101.         else {
  102.             int d1=dist(x,BL[x]),d2=dist(x,BL[v]);
  103.             if(d1==d2)BL[x]=min(BL[x],BL[v]);
  104.             else if(d1>d2)BL[x]=BL[v];
  105.         }
  106.     }
  107. }
  108.  
  109. void dfs3(int x){
  110.     for(int i=0;i<G2[x].size();++i){
  111.         int v=G2[x][i];
  112.         if(!BL[v])BL[v]=BL[x];
  113.         else {
  114.             int d1=dist(v,BL[v]),d2=dist(v,BL[x]);
  115.             if(d1==d2)BL[v]=min(BL[v],BL[x]);
  116.             else if(d1>d2)BL[v]=BL[x];
  117.         }
  118.         dfs3(v);
  119.     }
  120. }
  121.  
  122. void calc(int u,int v){
  123.     int s=v,t=v;
  124.     for(int i=18;~i;--i){
  125.         if(dep[ac[s][i]]>dep[u])s=ac[s][i];
  126.     }
  127.     Left[u]-=siz[s];
  128.     if(BL[u]==BL[v]){
  129.         Ans[ID[BL[u]]]+=siz[s]-siz[v];
  130.     }
  131.     else {
  132.         for(int i=18;~i;--i){
  133.             if(dep[ac[t][i]]<=dep[u])continue;
  134.             int x=ac[t][i];
  135.             int d1=dist(x,BL[u]);
  136.             int d2=dist(x,BL[v]);
  137.             if(d1>d2||(d1==d2&&BL[v]<BL[u]))t=x;
  138.         }
  139.         Ans[ID[BL[u]]]+=siz[s]-siz[t];
  140.         Ans[ID[BL[v]]]+=siz[t]-siz[v];
  141.     }
  142. }
  143.  
  144. int a[N];
  145.  
  146. int main(){
  147. //  freopen(".in","r",stdin);
  148. //  freopen(".out","w",stdout);
  149.     int n;r(n);
  150.     for(int i=1;i<n;++i){
  151.         int u,v;r(u),r(v);
  152.         G[u].push_back(v);
  153.         G[v].push_back(u);
  154.     }
  155.     dfs1(1,0);
  156.     int q;r(q);
  157.     while(q--){
  158.         int c;r(c);
  159.         for(int i=1;i<=c;++i){
  160.             r(a[i]);
  161.             ID[a[i]]=i;
  162.             BL[a[i]]=a[i];
  163.         }
  164.         sort(a+1,a+c+1,cmp);
  165.         top=0;
  166.         if(BL[1]!=1)sta[++top]=1;
  167.         for(int i=1;i<=c;++i){
  168.             ins(a[i]);
  169.         }
  170.         while(top>1){
  171.             addedge(sta[top-1],sta[top]);
  172.             top--;
  173.         }
  174.         dfs2(1);
  175.         dfs3(1);
  176.         for(int i=1;i<=tot;++i){
  177.             int x=tmp[i];
  178.             for(int j=0;j<G2[x].size();++j){
  179.                 calc(x,G2[x][j]);
  180.             }
  181.         }
  182.         for(int i=1;i<=tot;++i){
  183.             Ans[ID[BL[tmp[i]]]]+=Left[tmp[i]];
  184.         }
  185.         for(int i=1;i<=c;++i){
  186.             printf("%d ",Ans[i]);
  187.         }
  188.         puts("");
  189.         for(int i=1;i<=tot;++i){
  190.             Left[tmp[i]]=0;
  191.             G2[tmp[i]].clear();
  192.             Ans[ID[BL[tmp[i]]]]=0;
  193.             ID[tmp[i]]=0;
  194.             BL[tmp[i]]=0;
  195.         }
  196.         tot=0;
  197.     }
  198.     return 0;
  199. }
Advertisement
Add Comment
Please, Sign In to add comment