传送门
虚树入门题？
好难啊。
在学习别人的写法之后终于过了。
这道题dp方程很好想。
主要是不好写。
简要说说思路吧。
显然最优值只能够从子树和父亲转移过来。
于是我们先dfs一遍用儿子更新父亲，然后再dfs一遍用父亲更新儿子。
这样搞完之后可以统计出每个点所属的管辖点。
然后统计。
但这样单次跑是O(n)O(n)O(n)的不优秀。
考虑优化算法的时间复杂度。
注意到所有管辖点加起来只有O(n)O(n)O(n)个。
因此我们每次只把跟管辖点有关的点连起来建出一棵虚树。
然后每次就在上面跑带边权的dp。
最后顺便用倍增统计对答案的贡献。
这样每次在虚树上面dp的时间复杂度是O(O(O(虚树大小)))的。
于是就可以过啦。
最后提一提（贴一发）建虚树的步骤。
- 输入每个询问的点，并且按照dfs序为关键字排序
- 将第1个点压到栈当中，开始构建虚树
- 枚举到下一个点u，计算u与栈顶点v的公共祖先lca
- 假设栈中栈顶下方的点为w（若栈中只有1个点就直跳过这一步），若w点的深度大于lca就把v向w连一条边，并且弹掉v，重复此步，否则就到下一步
- 若lca不是当前的v，那么就把lca和v连边，把v弹出，让lca成为栈顶元素（注：这个操作的意思是如果栈顶没有这个lca那么就压入），否则不做任何操作
- 最后把u压入栈中
- 回到3操作枚举下个点，直到枚举完了所有点
- 把栈顶v与栈顶下方的点为w连边，并且把v弹掉，这么做直到栈里只有一个点
- 栈里剩下的点就是虚树的根了
接下来你就可以开始进行dp等操作了
最后我再提一个比较优秀的细节。
我们最开始可以直接把1号点放入虚树，这样方便的多，而不用像上面说的把最后栈顶的点作为树根。
代码：
#include<bits/stdc++.h>
#define N 300005
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
inline void write(int x){
if(x>9)write(x/10);
putchar(x%10^48);
}
int n,rt,q,m,first[N],b[N],a[N],st[N][21],cal[N],ans[N],siz[N],dfn[N],g[N],bel[N],dep[N],stk[N],cnt=0,dfn_cnt=0,top=0,tot=0;
struct egde{int v,next;}e[N<<1];
inline void add(int u,int v){if(!u||u==v)return;e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
inline void dfs(int p){
siz[p]=1,dfn[p]=++dfn_cnt;
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
if(v==st[p][0])continue;
st[v][0]=p,dep[v]=dep[p]+1,dfs(v),siz[p]+=siz[v];
}
}
inline int lca(int x,int y){
if(dep[x]<dep[y])x^=y,y^=x,x^=y;
for(int i=20;~i;--i)if(dep[x]-(1<<i)>=dep[y])x=st[x][i];
if(x==y)return x;
for(int i=20;~i;--i)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];
return st[x][0];
}
inline bool cmp(int x,int y){return dfn[x]<dfn[y];}
inline int calc(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];}
inline void dfs1(int p,int fa){
int dis1,dis2;
g[p]=siz[p],cal[++tot]=p;
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
if(v==fa)continue;
dfs1(v,p);
if(!bel[v])continue;
if(!bel[p]){bel[p]=bel[v];continue;}
dis1=calc(bel[v],p),dis2=calc(bel[p],p);
if(dis1<dis2||(dis1==dis2&&bel[v]<bel[p]))bel[p]=bel[v];
}
}
inline void dfs2(int p,int fa){
int dis1,dis2;
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
if(v==fa)continue;
if(!bel[v])bel[v]=bel[p];
else{
dis1=calc(v,bel[v]),dis2=calc(bel[p],v);
if(dis1>dis2||(dis1==dis2&&bel[v]>bel[p]))bel[v]=bel[p];
}
dfs2(v,p);
}
}
inline void solve(int u,int v){
int son=v,mid=v,Next,dis1,dis2;
for(int i=20;~i;--i)if(dep[son]-(1<<i)>dep[u])son=st[son][i];
g[u]-=siz[son];
if(bel[u]==bel[v]){ans[bel[u]]+=siz[son]-siz[v];return;}
for(int i=20;~i;--i){
Next=st[mid][i];
if(dep[Next]<=dep[u])continue;
dis1=calc(Next,bel[u]),dis2=calc(Next,bel[v]);
if(dis1>dis2||(dis1==dis2&&bel[u]>bel[v]))mid=Next;
}
ans[bel[u]]+=siz[son]-siz[mid],ans[bel[v]]+=siz[mid]-siz[v];
}
int main(){
n=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
add(u,v),add(v,u);
}
dfs(1),cnt=0,memset(first,0,sizeof(first));
for(int j=1;j<=20;++j)for(int i=1;i<=n;++i)st[i][j]=st[st[i][j-1]][j-1];
q=read();
while(q--){
m=read();
for(int i=1;i<=m;++i)a[i]=b[i]=read(),bel[a[i]]=a[i];
top=cnt=tot=0,sort(a+1,a+m+1,cmp);
if(bel[1]!=1)stk[++top]=1;
int t;
for(int i=1;i<=m;++i){
if(!top){stk[++top]=a[i];continue;}
t=lca(stk[top],a[i]);
while(1){
if(dep[stk[top-1]]<=dep[t]){
add(t,stk[top]),--top;
if(stk[top]!=t)stk[++top]=t;
break;
}
add(stk[top-1],stk[top]),--top;
}
if(stk[top]!=a[i])stk[++top]=a[i];
}
while(top>1)add(stk[top-1],stk[top]),--top;
--top,dfs1(1,0),dfs2(1,0);
for(int i=1;i<=tot;++i)for(int j=first[cal[i]];j;j=e[j].next)solve(cal[i],e[j].v);
for(int i=1;i<=tot;++i)ans[bel[cal[i]]]+=g[cal[i]];
for(int i=1;i<=m;++i)printf("%d ",ans[b[i]]);
puts("");
for(int i=1;i<=tot;++i)ans[cal[i]]=first[cal[i]]=g[cal[i]]=bel[cal[i]]=0;
}
return 0;
}