CF613D Kingdom and its Cities
题目：
给定一棵有n 个节点的树，树上有一些关键点(key)。接下来有q组询问，每次给出ki 个key，要求删去一些点，使得这些key不相连。要求删去的最少的点数。
1<=n<=100000
1<=q<=100000
The sum of all ki 's does't exceed 100000
题解：
这篇文章讲的很详细
第一反应肯定是树形dp，但是如果每个q都要跑一次完整的树，很俨然O(n * q)肯定会超时，所以肯定要用到虚树
虚树题目的一般套路，先不考虑超时写出树上dp转移方程，然后根据题意构建虚树，多为确定关键点，然后求lca
首先是树上dp部分：
如果两个关键点直接相连就无解（注意题目要求的是删点而非删边）
如果当前点是关键点，那么询问他的子儿子是不是关键点，如果是，两者连线上的点就必须断开。
如果当前点不是关键点，看子树中有多少关键点，如果多于两个，就将当前点删去，这样子树就断开了。如果只有一个，那么留到后面和洽谈子树中的关键点分割更优
siz[x]：以x为根的子树里key的个数
ans[i]：以x为根的子树，使得所有的key都不连通的最小删点个数
void dfs(int x)//树形dp，具体写法视题意而定，本题的树形dp基于贪心
{
ans[x]=0;
if(vis[x])//若当前点是关键点
{
siz[x]=1;//关键点数量
for(int i=0;i<vir[x].size();i++)
{
int son=vir[x][i];
dfs(son);
ans[x]+=ans[son];
if(siz[son])//若son子树中有关键点，必须删除一个点，以保证其不与x连通
ans[x]++;
}
}
else//若当前点为非关键点
{
siz[x]=0;
for(int i=0;i<vir[x].size();i++)
{
int son=vir[x][i];
dfs(son);
ans[x]+=ans[son];
siz[x]+=siz[son];
}
if(siz[x]>1)//若子树中有节点，则删除x节点
{
siz[x]=0;
ans[x]++;
}
}
} 然后就是建虚树：
建虚树就是找key点，然后将key的lca同时保留，维护树的形状
我们按照dfn的大小对key值进行排序，然后按照顺序两两求lca建树
这样就不用每对元素都求Lca（至于具体证明这里不讲了）
bool cmp(int x,int y)
{
return ldfn[x]<ldfn[y];
}//按dfn排序
void build()
{
sort(d+1,d+1+m,cmp);
int keynum=m;
for(int i=1;i<keynum;i++)
d[++m]=LCA(d[i],d[i+1]);//求相邻两个的LCA
sort(d+1,d+1+m,cmp);
m=unique(d+1,d+1+m)-d-1;
//去重，unique对一个已经排序的数组可以实现去重，
//多出来的扔到了数组的后面，并返回数组大小的地址
int top=0;
stk[++top]=d[1];
for(int i=2;i<=m;i++){
while(top&&rdfn[stk[top]]<ldfn[d[i]])
top--;//如果不是祖先，则弹出元素
if(top) vir[stk[top]].push_back(d[i]);//加入到其祖先的子树里
stk[++top]=d[i];//维护新的链
}
}
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100100;
const int MAXB=20;
int cnt,m;
int ldfn[MAXN],rdfn[MAXN];//当前节点的dfs序
int fa[MAXN][MAXB];//f[i][j]表示i节点向上2^j步的祖先
int dep[MAXN];//节点深度
int stk[MAXN];//栈，用于构建虚树
int d[MAXN<<1];//用于存储虚树的节点编号。由于LCA可能有重复，因此需要开2倍
int vis[MAXN];//标记当前节点是否为关键点
vector<int> rea[MAXN],vir[MAXN];//实树的边，虚树的边
int ans[MAXN],siz[MAXN];//用于树形dp
void predfs(int x,int f,int depth)//模板，预处理，计算实树上每个节点的dfs序和倍增祖先
{
ldfn[x]=++cnt;
dep[x]=depth;
fa[x][0]=f;
for(int j=1;j<MAXB;j++)
{
fa[x][j]=fa[fa[x][j-1]][j-1];
}
for(int i=0;i<rea[x].size();i++)
{
int son=rea[x][i];
if(son!=f)
predfs(son,x,depth+1);
}
rdfn[x]=cnt;
}
int lca(int u,int v)//模板，倍增计算u和v的最近公共祖先
{
if(dep[u]<dep[v])
swap(u,v);
int delta=dep[u]-dep[v];
for(int j=0;j<MAXB&δj++)//先调整到同一深度
{
if(delta&(1<<j))
u=fa[u][j];
}
if(u==v)
return u;
for(int j=MAXB-1;j>=0;j--)//再二分向上查找LCA
{
if(fa[u][j]!=fa[v][j])
{
u=fa[u][j];
v=fa[v][j];
}
}
return fa[u][0];
}
bool cmp(int x,int y)
{
return ldfn[x]<ldfn[y];
}
void build()//模板，构建虚树
{
sort(d+1,d+m+1,cmp);//按dfs序排序
int keynum=m;
for(int i=1;i<keynum;i++)//将dfs序相邻的节点的LCA也加入到虚树的构建中
d[++m]=lca(d[i],d[i+1]);
sort(d+1,d+m+1,cmp);//再次排序
m=unique(d+1,d+m+1)-d-1;//去重
//unique函数的本质是将相邻且相同的元素去重，通常与sort搭配使用，利用排序将相同元素放在相邻位置
//虽然d[]内元素没有按数值递增，但按cmp排序后，也能保证相同元素处在相邻位置，可以用unique去重
int top=0;
stk[++top]=d[1];//构造一个从底到顶元素的深度递增单调栈
for(int i=2;i<=m;i++)//开始构建虚树
{
while(top&&rdfn[stk[top]]<ldfn[d[i]])//维护单调栈，弹出不是d[i]祖先的元素
top--;
if(top)
vir[stk[top]].push_back(d[i]);//连边
stk[++top]=d[i];//d[i]加入单调栈
}
}
void dfs(int x)//树形dp，具体写法视题意而定，本题的树形dp基于贪心
{
ans[x]=0;
if(vis[x])//若当前点是关键点
{
siz[x]=1;//关键点数量
for(int i=0;i<vir[x].size();i++)
{
int son=vir[x][i];
dfs(son);
ans[x]+=ans[son];
if(siz[son])//若son子树中有关键点，必须删除一个点，以保证其不与x连通
ans[x]++;
}
}
else//若当前点为非关键点
{
siz[x]=0;
for(int i=0;i<vir[x].size();i++)
{
int son=vir[x][i];
dfs(son);
ans[x]+=ans[son];
siz[x]+=siz[son];
}
if(siz[x]>1)//若子树中有节点，则删除x节点
{
siz[x]=0;
ans[x]++;
}
}
}
int main()
{
int n,q,u,v;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
rea[i].clear();
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
rea[u].push_back(v);
rea[v].push_back(u);
}
cnt=0;
predfs(1,0,0);
scanf("%d",&q);
while(q--)
{
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&d[i]);
vis[d[i]]=1;
}
int flag=1;
for(int i=1;i<=m;i++)
{
if(vis[fa[d[i]][0]])
{
flag=0;
break;
}
}
if(!flag)
{
printf("-1\n");
}
else
{
build();
dfs(d[1]);
printf("%d\n",ans[d[1]]);
}
for(int i=1;i<=m;i++)//由于关键点较少，避免使用memset清空
{
vis[d[i]]=0;
vir[d[i]].clear();
}
}
}
}