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;
}