C++ 48行代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;inline int read() {int res=0;bool bo=0;char c;while(((c=
getchar())<'0'||c>'9')&&c!='-');if(c=='-')bo=1;else res=c-48;while((c=getchar())
>='0'&&c<='9')res=(res<<3)+(res<<1)+(c-48);return bo?~res+1:res;}const int N=3e5+5,
M=6e5+5,LogN=21,INF=0x3f3f3f3f;int n,ecnt,nxt[M],adj[N],go[M],dep[N],fa[N][LogN],
times,dfn[N],vn,vir[N],top,stk[N],par[N],ecnt2,nxt2[M],adj2[N],go2[M],val2[M],Q,
tmp[N],tn,ans[N], sze[N];bool isvir[N];struct cyx{int x,y;cyx(){}cyx(int _x,int _y):
x(_x),y(_y) {}friend inline bool operator<(cyx a,cyx b) {if(a.x!=b.x)return a.x
<b.x;return a.y < b.y;}} f[N],g[N];void add_edge(int u,int v) {nxt[++ecnt]=
adj[u];adj[u]=ecnt;go[ecnt]=v;nxt[++ecnt]=adj[v];adj[v]=ecnt;go[ecnt]=u;}
void add_edge2(int u,int v,int w) {nxt2[++ecnt2]=adj2[u];adj2[u]=ecnt2;
go2[ecnt2]=v;val2[ecnt2]=w;nxt2[++ecnt2]=adj2[v];adj2[v]=ecnt2;go2[ecnt2]=u;
val2[ecnt2]=w;}inline bool comp(const int &u,const int &v) {return dfn[u]<dfn[v];}
void dfs(int u, int fu){int i;dep[u]=dep[fa[u][0]=fu]+1;dfn[u]=++times;
sze[u]=1;for(i=0;i<=18;i++)fa[u][i+1]=fa[fa[u][i]][i];for(int e=adj[u],v;e;e=
nxt[e]){if((v=go[e])==fu) continue;dfs(v,u);sze[u]+=sze[v];}}int lca(int u,int v)
{int i;if(dep[u]<dep[v])swap(u,v);for(i=19;i>=0;i--){if(dep[fa[u][i]]>=dep[v])
u=fa[u][i];if(u==v)return u;}for(i=19;i>=0;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],
v=fa[v][i];return fa[u][0];}void build_virtree(){int i;tn=vn;sort(vir+1,vir+vn+1,
comp);top=0;for(i=1;i<=tn;i++){int u=vir[i];if(!top){par[stk[++top]=u]=0;continue;}
int w=lca(stk[top],u);while(dep[stk[top]]>dep[w]){if(dep[stk[top-1]]<dep[w])
par[stk[top]]=w;top--;}if(w!=stk[top])vir[++vn]=w,par[w]=stk[top],stk[++top]=w;
par[stk[++top]=u]=w;}sort(vir+1,vir+vn+1,comp);ecnt2=0;for(i=1;i<=vn;i++)adj2
[vir[i]]=0;for(i=2;i<=vn;i++)add_edge2(par[vir[i]],vir[i],dep[vir[i]]-dep[par[
vir[i]]]);}void dfs1(int u){int tot=0;f[u]=cyx(INF,0);g[u]=cyx(INF,0);cyx x;for
(int e=adj2[u],v;e;e=nxt2[e]){if((v=go2[e])==par[u])continue;tot++;dfs1(v);
x=cyx(f[v].x+val2[e],f[v].y);if(x<f[u])g[u]=f[u],f[u]=x;else if(x<g[u])g[u]=x;
}if(tot&&isvir[u])g[u]=f[u],f[u]=cyx(0,u);if(!tot)f[u]=cyx(0,u),g[u]=cyx(INF,0);
}void dfs2(int u){cyx x;for(int e=adj2[u],v;e;e=nxt2[e]){if((v=go2[e])==par[u])
continue;x=cyx(f[u].x+val2[e],f[u].y);if(f[u].y==f[v].y)x=cyx(g[u].x+val2[e],g[u].y);
if(x<f[v])f[v]=x;dfs2(v);}}int divi(int u,int v){int i,t=u;for(i=19;i>=0;i--){
if(dep[fa[u][i]] < dep[v]) continue;int w=fa[u][i];cyx x,y;x=cyx(f[t].x+dep[t]-
dep[w],f[t].y);y=cyx(f[v].x+dep[w]-dep[v],f[v].y);if(x<y)u=w;}return u;}int jump(
int u,int x) {int i;for(i=19;i>=0;i--)if((x>>i)&1) u=fa[u][i];return u;}void dfs3(
int u){int delta=sze[u]-1;for(int e=adj2[u],v;e;e=nxt2[e]){if((v=go2[e])==par[u])
continue;dfs3(v);v=jump(v,dep[v]-dep[u]-1);delta-=sze[v];}ans[f[u].y]+=delta;}
void solve() {int i;for(i=1;i<=tn;i++)ans[tmp[i]]=0;dfs1(vir[1]);dfs2(vir[1]);
ans[f[vir[1]].y]+=n-sze[vir[1]];for(i=1;i<=vn;i++)ans[f[vir[i]].y]++;for(i=2;i<=vn;
i++){int u=vir[i],v=par[u],w;if(dep[u]-dep[v]==1) continue;w=divi(u, v);if(u!=w)
ans[f[u].y]+=sze[w]-sze[u];if(dep[w]-dep[v]>1)ans[f[v].y]+=sze[jump(w,dep[w]-dep[v]
-1)]-sze[w];}dfs3(vir[1]);for(i=1;i<=tn;i++)printf("%d ",ans[tmp[i]]);printf("\n");}
int main(){int i,x,y;n=read();for(i=1;i<n;i++)x=read(),y=read(),add_edge(x,y);dfs(1,
0);Q=read();while(Q--){vn=read();for(i=1;i<=vn;i++)isvir[vir[i]=tmp[i]=read()]=1;
build_virtree();solve();for(i=1;i<=tn;i++)isvir[tmp[i]]=0;}return 0;}