613-D 题目大意

给定一颗\(n\)个节点的树。

\(q\)组询问，每组询问给定\(k\)个点，问至少要删除树中多少个点才能使这\(k\)个点两两不连通，无解则输出\(-1\)。

这里\(\sum{k_i}\)的规模大致和\(n\)相当。

Solution

虚树模板题。

暴力的做法是每组询问都对整棵树进行遍树形DP，复杂度为\(O(qn)\)。虚树的做法是对于每组询问的\(k\)个点，在原树的基础上重构一颗小规模的新树，在新树上进行树形DP，虚树能够保证重构树中的节点数量不超过\(2k\)，时间复杂度为\(O(\sum{k_i}·log\sum{k_i})\)。

对于一组点集，虚树的构建过程如下：
1、预处理出原树的\(dfs\)序，对点集按\(dfn\)序升序排序。
2、用栈\(st\)来维护\(dfs\)访问过的点，栈中的点从栈底到栈顶构成一条链，深度从小到大。首先加入根节点0。
3、现在考虑加入点\(x\)，设\(y=st[top]\)，\(z=lca(x,y)\)，分情况讨论：
\(\;\;\;\;\)①当\(z=y\)时，说明\(x\)是\(y\)子树内的节点，此时直接把\(x\)加入栈中即可。
\(\;\;\;\;\)②当\(z\ne y\)时，说明\(x\)不是\(y\)子树内的节点，此时应当把栈中深度大于\(z\)的节点全部出栈，在出栈的过程中进行连边建立虚树，直到\(dep[st[top-1]]<dep[z]\)为止。最后栈顶元素的深度仍然不小于\(z\)的深度，这时分两种情况\(\;\;\;\;\)讨论:
\(\;\;\;\;\;\;\;\;\)\(Ⅰ.\)如果\(y=z\)，说明\(lca\)已在栈中，直接把\(x\)入栈即可。
\(\;\;\;\;\;\;\;\;\)\(Ⅱ.\)如果\(y\ne z\)，说明\(lca\)不在栈中，那么把\(z\)向\(y\)连一边条，再把\(y\)出栈，然后再把\(z\)和\(x\)先后入栈。
4、枚举完点集之后，栈中仍然保存着一条链，把栈中节点全部出栈，并进行连边。

树形DP：
剩余的就是如何进行树形DP，首先判定无解的情况，存在一组父子点都在询问给的点集之中，此时无解。
对整棵树进行DP，维护一个\(sz\)值，询问点为\(1\)，其余点为\(0\)，分情况讨论：
1、如果当前点\(x\)是询问点，对它的所有儿子\(y\)进行\(dfs\)，如果儿子\(y\)的\(sz\)值为正，说明要从\(x\)到\(y\)的路径上删除一个点，否则不需要操作。
2、如果当前点\(x\)不是询问点，对它的所有儿子\(y\)进行\(dfs\)，并把所有儿子的\(sz\)值累加到\(x\)的\(sz\)值中，如果最终\(sz[x]\)超过1，说明删除这个非询问点，能够隔离开它子树中所有的询问点，否则不需要操作。

要注意的是需要在递归结束时清空相应的\(sz\)值，以及把新加的边都删去。如果整个操作完再去统一初始化，则时间复杂度会退化到\(O(qn)\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	int P=19;
	vector<vector<int>> e(n),ne(n);
	vector<vector<int>> fa(n,vector<int>(P));
	vector<int> dfn(n),dep(n);
	int idx=0;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		--x,--y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	function<void(int,int,int)> dfs=[&](int x,int father,int depth){
		dfn[x]=++idx,fa[x][0]=father,dep[x]=depth;
		for(int i=1;i<P;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
		for(auto y:e[x]){
			if(y==father) continue;
			dfs(y,x,depth+1);
		}
	};
	function<int(int,int)> lca=[&](int x,int y){
		if(dep[x]<dep[y]) swap(x,y);
		for(int i=P-1;~i;i--){
			if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
		}
		if(x==y) return x;
		for(int i=P-1;~i;i--){
			if(fa[x][i]!=fa[y][i]){
				x=fa[x][i],y=fa[y][i];
			}
		}
		return fa[x][0];
	};
	dfs(0,0,0);
	int q;
	cin>>q;
	vector<int> sz(n);
	int ans=0;
	function<void(vector<int>&)> build=[&](vector<int> &p){
		sort(p.begin(),p.end(),[&](const auto &x,const auto &y){
			return dfn[x]<dfn[y];
		});
		vector<int> st{0};//根节点入栈
		if(p[0]!=0) st.push_back(p[0]);//第一个查询点入栈
		for(int i=1;i<p.size();i++){
			int x=p[i],y=st.back();
			st.pop_back();
			int z=lca(x,y);
			while(st.size()&&dep[st.back()]>=dep[z]){//对当前链连边
				ne[st.back()].push_back(y);
				y=st.back();
				st.pop_back();
			}
			if(z!=y){//对lca和栈顶点连边,栈顶点出栈,lca入栈
				ne[z].push_back(y);
			}
			st.push_back(z);
			st.push_back(p[i]);
		}
		while(st.size()>1){///对最后一条链连边
			int y=st.back();
			st.pop_back();
			ne[st.back()].push_back(y);
		}
	};
	function<void(int)> DP=[&](int x){
		if(sz[x]){
			for(auto y:ne[x]){
				DP(y);
				if(sz[y]) ans++,sz[y]=0;
			}
		}else{
			for(auto y:ne[x]){
				DP(y);
				sz[x]+=sz[y],sz[y]=0;
			}
			if(sz[x]>1) ans++,sz[x]=0;
		}
		ne[x].clear();
	};
	while(q--){
		int k;
		cin>>k;
		vector<int> p(k);
		for(int i=0;i<k;i++){
			cin>>p[i];
			p[i]--;
			sz[p[i]]=1;
		}
		int flag=0;
		for(int i=0;i<k;i++){
			if(p[i]!=0&&sz[fa[p[i]][0]]) flag=1;
		}
		if(flag){
			for(int i=0;i<k;i++) sz[p[i]]=0;
			cout<<-1<<'\n';
			continue;
		}
		build(p);
		ans=0;
		DP(0);
		sz[0]=0;
		cout<<ans<<'\n';
	}
	return 0;
}