Codeforces613D Kingdom and its Cities【虚树】

注意判断-1后虚树的清零。

Code：

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m,k,a[maxn],dep[maxn],fa[maxn],siz[maxn],son[maxn],top[maxn],dfn[maxn],tim;
int fir[maxn],nxt[maxn<<1],to[maxn<<1],tot;
inline void line(int x,int y){nxt[++tot]=fir[x],fir[x]=tot,to[tot]=y;}
bool cmp(int i,int j){return dfn[i]<dfn[j];}
void dfs1(int u,int ff){
	dep[u]=dep[fa[u]=ff]+1,siz[u]=1;
	for(int i=fir[u],v;i;i=nxt[i]) if((v=to[i])!=ff){
		dfs1(v,u),siz[u]+=siz[v];
		if(siz[v]>siz[son[u]]) son[u]=v;	
	}
}
void dfs2(int u,int tp){
	top[u]=tp,dfn[u]=++tim;
	if(son[u]) dfs2(son[u],tp);
	for(int i=fir[u];i;i=nxt[i]) if(!dfn[to[i]]) dfs2(to[i],to[i]);	
}
inline int LCA(int u,int v){
	for(;top[u]!=top[v];u=fa[top[u]]) if(dep[top[u]]<dep[top[v]]) swap(u,v);
	return dep[u]<dep[v]?u:v;	
}
namespace VTree{
	int stk[maxn],top,f[maxn],g[maxn],rec[maxn],sz;
	bool kp[maxn];
	void dfs(int u){
		if(kp[u]){
			f[u]=0,g[u]=1;
			for(int i=fir[u],v;i;i=nxt[i]) dfs(v=to[i]),f[u]+=f[v]+g[v]; 	
		}
		else{
			f[u]=0,g[u]=0;
			for(int i=fir[u],v;i;i=nxt[i]) dfs(v=to[i]),f[u]+=f[v],g[u]+=g[v];
			if(g[u]>1) f[u]++,g[u]=0;
		}
	}
	void solve(){
		for(int i=1,lca;i<=k;i++){
			kp[rec[++sz]=a[i]]=1; if(!top) {stk[++top]=a[i];continue;}
			for(lca=LCA(a[i],stk[top]);top>1&&dfn[lca]<=dfn[stk[top-1]];top--) line(stk[top-1],stk[top]);
			if(stk[top]!=lca) line(lca,stk[top]),stk[top]=lca,rec[++sz]=lca;
			else if(kp[lca]&&lca==fa[a[i]]) {puts("-1");goto end;}
			stk[++top]=a[i];
		}
		for(;top>1;top--) line(stk[top-1],stk[top]);
		dfs(stk[1]),printf("%d\n",f[stk[1]]);
	end:
		for(tot=top=0;sz;sz--) kp[rec[sz]]=fir[rec[sz]]=0;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),line(x,y),line(y,x);
	dfs1(1,0),dfs2(1,1);
	scanf("%d",&m);
	memset(fir,0,sizeof fir),tot=0;
	while(m--){
		scanf("%d",&k);
		for(int i=1;i<=k;i++) scanf("%d",&a[i]);
		sort(a+1,a+1+k,cmp);
		VTree::solve();
	}
}