Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- #define ll long long
- template<typename T>
- inline void read(T&x){
- x=0;T k=1;char gc;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
- }
- const int N=300005;
- vector<int>G[N];
- vector<int>G2[N];
- int ac[N][20];
- int dep[N];
- int siz[N];
- int dfn[N];
- int dfs_clock;
- void dfs1(int x,int f){
- siz[x]=1;
- dep[x]=dep[f]+1;
- ac[x][0]=f;
- dfn[x]=++dfs_clock;
- for(int i=1;(ac[x][i]=ac[ac[x][i-1]][i-1]);++i);
- for(int i=0;i<G[x].size();++i){
- int v=G[x][i];
- if(v==f)continue;
- dfs1(v,x);
- siz[x]+=siz[v];
- }
- }
- inline int lca(int u,int v){
- if(dep[u]<dep[v])swap(u,v);
- for(int i=18;~i;--i){
- if(dep[ac[u][i]]>=dep[v])u=ac[u][i];
- }
- if(u==v)return u;
- for(int i=18;~i;--i){
- if(ac[u][i]!=ac[v][i])u=ac[u][i],v=ac[v][i];
- }
- return ac[u][0];
- }
- inline bool cmp(const int &a,const int &b){
- return dfn[a]<dfn[b];
- }
- int top;
- int sta[N];
- inline void addedge(int u,int v){
- G2[u].push_back(v);
- // G2[v].push_back(u);
- }
- inline void ins(int x){
- if(top==0){
- sta[++top]=x;
- return ;
- }
- int t=lca(x,sta[top]);
- while(top>1&&dep[sta[top-1]]>=dep[t]){
- addedge(sta[top-1],sta[top]);
- top--;
- }
- if(sta[top]!=t){
- addedge(t,sta[top]);
- sta[top]=t;
- }
- sta[++top]=x;
- }
- inline int dist(int u,int v){
- return dep[u]+dep[v]-2*dep[lca(u,v)];
- }
- int ID[N];
- int BL[N];
- int tot;
- int tmp[N];
- int Left[N];
- int Ans[N];
- void dfs2(int x){
- Left[x]=siz[x];
- tmp[++tot]=x;
- for(int i=0;i<G2[x].size();++i){
- int v=G2[x][i];
- dfs2(v);
- if(!BL[v])continue;
- if(!BL[x])BL[x]=BL[v];
- else {
- int d1=dist(x,BL[x]),d2=dist(x,BL[v]);
- if(d1==d2)BL[x]=min(BL[x],BL[v]);
- else if(d1>d2)BL[x]=BL[v];
- }
- }
- }
- void dfs3(int x){
- for(int i=0;i<G2[x].size();++i){
- int v=G2[x][i];
- if(!BL[v])BL[v]=BL[x];
- else {
- int d1=dist(v,BL[v]),d2=dist(v,BL[x]);
- if(d1==d2)BL[v]=min(BL[v],BL[x]);
- else if(d1>d2)BL[v]=BL[x];
- }
- dfs3(v);
- }
- }
- void calc(int u,int v){
- int s=v,t=v;
- for(int i=18;~i;--i){
- if(dep[ac[s][i]]>dep[u])s=ac[s][i];
- }
- Left[u]-=siz[s];
- if(BL[u]==BL[v]){
- Ans[ID[BL[u]]]+=siz[s]-siz[v];
- }
- else {
- for(int i=18;~i;--i){
- if(dep[ac[t][i]]<=dep[u])continue;
- int x=ac[t][i];
- int d1=dist(x,BL[u]);
- int d2=dist(x,BL[v]);
- if(d1>d2||(d1==d2&&BL[v]<BL[u]))t=x;
- }
- Ans[ID[BL[u]]]+=siz[s]-siz[t];
- Ans[ID[BL[v]]]+=siz[t]-siz[v];
- }
- }
- int a[N];
- int main(){
- // freopen(".in","r",stdin);
- // freopen(".out","w",stdout);
- int n;r(n);
- for(int i=1;i<n;++i){
- int u,v;r(u),r(v);
- G[u].push_back(v);
- G[v].push_back(u);
- }
- dfs1(1,0);
- int q;r(q);
- while(q--){
- int c;r(c);
- for(int i=1;i<=c;++i){
- r(a[i]);
- ID[a[i]]=i;
- BL[a[i]]=a[i];
- }
- sort(a+1,a+c+1,cmp);
- top=0;
- if(BL[1]!=1)sta[++top]=1;
- for(int i=1;i<=c;++i){
- ins(a[i]);
- }
- while(top>1){
- addedge(sta[top-1],sta[top]);
- top--;
- }
- dfs2(1);
- dfs3(1);
- for(int i=1;i<=tot;++i){
- int x=tmp[i];
- for(int j=0;j<G2[x].size();++j){
- calc(x,G2[x][j]);
- }
- }
- for(int i=1;i<=tot;++i){
- Ans[ID[BL[tmp[i]]]]+=Left[tmp[i]];
- }
- for(int i=1;i<=c;++i){
- printf("%d ",Ans[i]);
- }
- puts("");
- for(int i=1;i<=tot;++i){
- Left[tmp[i]]=0;
- G2[tmp[i]].clear();
- Ans[ID[BL[tmp[i]]]]=0;
- ID[tmp[i]]=0;
- BL[tmp[i]]=0;
- }
- tot=0;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment