http://www.lydsy.com/JudgeOnline/problem.php?id=3572
明显需要构造虚树
点属于谁管理分三种情况：
1、属于虚树的点
2、在虚树上的边上的点
3、既不属于虚树的点，又不属于虚树上的边的点
第一种情况：
先做一遍树形dp，得到子树中距离它最近的点
再dfs一遍，看看父节点那一块 是否有比它现在的点更近的点
第二种情况：
一条边u-->v 如果u和v属于同一点x管理，那么这条边所代表的所有点也都属于x管理
否则的话，二分一个点tmp，tmp以上的点归管理u的点管理，tmp及tmp以下的点归管理v的点管理
第三种情况：
归这个种树的根 的父节点 管理
第三种情况可以合并到第一种情况中，即用siz[x]表示虚树中一个点x在原树代表多少个点
开始siz[x]=原树中x的子树大小
虚树中每加一条边x-->y，若y属于x的子节点中k的子树，就在siz[x]中减去 原树中k的子树大小
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm> #define N 300001 typedef long long LL; #define min(x,y) ((x)<(y) ? (x) : (y)) int n,lim;
int num,id[N];
int fa[N][],SIZ[N],prefix[N],dep[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-'';c=getchar(); }
} namespace Original
{
int front[N],nxt[N<<],to[N<<];
int tot; void add(int u,int v)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;
} void dfs(int x)
{
id[x]=++num;
SIZ[x]=;
int t;
for(int i=front[x];i;i=nxt[i])
{
t=to[i];
if(t!=fa[x][])
{
fa[t][]=x;
dep[t]=dep[x]+;
dfs(t);
SIZ[x]+=SIZ[t];
}
}
} void multiplication()
{
lim=log(n)/log();
for(int i=;i<=lim;++i)
for(int j=;j<=n;++j)
fa[j][i]=fa[fa[j][i-]][i-];
} void Prefix_dfs(int x)
{
int t;
for(int i=front[x];i;i=nxt[i])
{
t=to[i];
if(t!=fa[x][])
{
prefix[t]=prefix[x]+SIZ[x]-SIZ[t];
Prefix_dfs(t);
}
}
} void main()
{
int u,v;
read(n);
for(int i=;i<n;++i)
{
read(u); read(v);
add(u,v);
}
dfs();
multiplication();
Prefix_dfs();
return;
}
} namespace Imaginary
{
int cnt,use[N]; int st[N],top; int tot;
int front[N],to[N],nxt[N],from[N],val[N]; int bin[N],bin_cnt; int siz[N]; int mi[N],bl[N];
int dy[N],ans[N]; bool cmp(int p,int q)
{
return id[p]<id[q];
} int find_ancestor(int x,int y)
{
for(int i=lim;i>=;--i)
if(y>=(<<i))
{
x=fa[x][i];
y-=(<<i);
}
return x;
} void add(int u,int v,int w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u; val[tot]=w;
int s=find_ancestor(v,dep[v]-dep[u]-);
siz[u]-=SIZ[s];
} int get_lca(int x,int y)
{
if(id[x]<id[y]) std::swap(x,y);
for(int i=lim;i>=;--i)
if(id[fa[x][i]]>id[y]) x=fa[x][i];
return fa[x][];
} int get_dis(int u,int v)
{
int lca=get_lca(u,v);
return dep[u]+dep[v]-dep[lca]*;
} void build()
{
std::sort(use+,use+cnt+,cmp);
tot=;
st[top=]=;
bin[bin_cnt=]=;
siz[]=SIZ[];
int i=;
if(use[]==) i=;
int x,lca;
for(;i<=cnt;++i)
{
x=use[i];
lca=get_lca(x,st[top]);
while(id[lca]<id[st[top]])
{
if(id[lca]>=id[st[top-]])
{
add(lca,st[top],dep[st[top]]-dep[lca]);
if(lca!=st[--top])
{
st[++top]=lca;
siz[lca]+=SIZ[lca];
bin[++bin_cnt]=lca;
}
break;
}
add(st[top-],st[top],dep[st[top]]-dep[st[top-]]);
top--;
}
st[++top]=x;
siz[x]+=SIZ[x];
bin[++bin_cnt]=x;
}
while(top>)
{
add(st[top-],st[top],dep[st[top]]-dep[st[top-]]);
top--;
}
} int dfs1(int x)
{
int p,d;
mi[x]=;
if(dy[x])
{
for(int i=front[x];i;i=nxt[i]) dfs1(to[i]);
bl[x]=x;
return x;
}
for(int i=front[x];i;i=nxt[i])
{
p=dfs1(to[i]);
d=dep[p]-dep[x];
if(!mi[x] || d<mi[x])
{
mi[x]=d;
bl[x]=p;
}
else if(d==mi[x] && p<bl[x]) bl[x]=p;
}
return bl[x];
} int dfs2(int x)
{
int t;
for(int i=front[x];i;i=nxt[i])
{
t=to[i];
if(!dy[t])
if(bl[x]!=bl[t])
{
if(mi[x]+val[i]<mi[t])
{
mi[t]=mi[x]+val[i];
bl[t]=bl[x];
}
else if(mi[x]+val[i]==mi[t] && bl[x]<bl[t]) bl[t]=bl[x];
}
dfs2(t);
}
ans[dy[bl[x]]]+=siz[x];
} void belong()
{
dfs1();
dfs2();
} void get_ans()
{
int f,s;
int l,r,mid,tmp,tmp_son;
int u,v;
bool equal;
int up,down;
for(int i=;i<=tot;++i)
{
u=from[i];
v=to[i];
r=dep[v]-dep[u]-;
if(!r) continue;
s=find_ancestor(v,r);
if(bl[u]==bl[v]) ans[dy[bl[u]]]+=prefix[v]-prefix[s];
else
{
tmp=v;
l=;
equal=false;
while(l<=r)
{
mid=l+r>>;
f=find_ancestor(v,mid);
down=get_dis(f,bl[v]);
up=get_dis(f,bl[u]);
if(down<up) tmp=f,l=mid+;
else if(down==up)
{
tmp=f;
equal=true;
tmp_son=find_ancestor(v,mid-);
break;
}
else r=mid-;
}
if(!equal)
{
ans[dy[bl[v]]]+=prefix[v]-prefix[tmp];
ans[dy[bl[u]]]+=prefix[tmp]-prefix[s];
}
else
{
ans[dy[bl[v]]]+=prefix[v]-prefix[tmp_son];
ans[dy[bl[u]]]+=prefix[tmp]-prefix[s];
ans[dy[min(bl[v],bl[u])]]+=prefix[tmp_son]-prefix[tmp];
}
}
}
for(int i=;i<=cnt;++i) printf("%d ",ans[i]);
printf("\n");
} void clear()
{
for(int i=;i<=bin_cnt;++i)
{
front[bin[i]]=;
ans[i]=;
dy[bin[i]]=;
siz[bin[i]]=;
}
tot=;
} void main()
{
int m;
read(m);
while(m--)
{
read(cnt);
for(int i=;i<=cnt;++i)
{
read(use[i]);
dy[use[i]]=i;
}
build();
belong();
get_ans();
clear();
}
return;
}
} int main()
{
Original::main();
Imaginary::main();
return ;
}