在阅读本文之前,你需要了解DFS序,树链剖分算法与LCA.
Part1:虚树的概念
虚树,是对于一棵给定节点数(n)的树(T),构造一棵新的树(T')使得节点总数最小且包含指定的某几个节点和它们的LCA.
利用虚树,可以对于指定多组点集(S)的询问进行每组(O(|S|log n+f(|S|)))的回答,其中(f(x))指的是对于树上(x)个点的情况下单组询问这个问题的时间复杂度.可以看到,这个复杂度基本上(除了那个(log n)以外)与(n)无关了.这样,对于多组询问的回答就可以省去每次询问都遍历一整棵树的(O(n))复杂度了.
Part2:虚树的构造
我们以CF613D Kingdom and its Cities作为例题.
题意:
给定一棵树,多组询问,每组询问给定(k)个点,你可以删掉不同于那(k)个点的(m)个点,使得这(k)个点两两不连通,要求最小化(m),如果不可能输出(-1).询问之间独立.数据范围(nleq10^5,sum kleq10^5).
一看到这种(sum kleq10^5)的题很可能就是虚树了.
构造方法
先预处理整棵树的LCA与DFS序,接下来是对于每组询问的构造.
虚树的构造是一个增量算法,要首先将指定的这(k)个点按照DFS序排序,然后按照顺序一一加入.可以强行先加入根节点以方便后面的处理.
虚树构建时会开一个栈(S),这个栈本质上和DFS递归时系统自动开的栈原理是一样的.也就是说,这个栈保存了从根出发的一条路径(按照深度从小到大存储).当加入第(k)个指定的节点(a_k)后,满足(S[1]=root,S.top()=a_k,stk[x])为(S[x-1])的后代.虚树上((u,v))的边的连接时间就是(v)被弹出栈的时间.
考虑如何加入一个新的节点(x).设(zleftarrow ext{LCA}(x,S.top())),分两类讨论:
1.(z=S.top()),也就是(x)是(S.top())的子树内节点.这时直接将(x)加入栈中即可.
2.(z e S.top()),这种情况中,(x)一定不是(S.top())子树内的节点.
这时原树上的情况.这时,"..."代指的那些路径上的节点以及(S[S.size()-1],S.top())都应弹出栈外(相当于开始回溯,访问(z)的另一棵子树).注意,此时(S[S.size()-1],S.top())和(z,x)在树上不一定直接相连,图中只是少画了几个节点而已.
我们不断弹出(S.top()),直到(S[S.size()-1].dep<z.dep),这时"..."表示的点全部出栈.在弹(S.top())时都要在虚树上连一条((S[S.size()-1],S.top()))的边.
注意弹完时可能(S.top() e z),我们需要把(z)补充进虚树来维护这个,直接加进栈即可.插入完所有点之后要完全回溯,也就是把栈内节点都弹出,也要连((S[S.size()-1],S.top()))的边.
伪代码如下:
( ext{INSERT_TO_VIRTUAL_TREE}(x):)
(mathbf{if} S.empty():)
(quad S.push(x))
(quad mathbf{return})
(ancestorleftarrow ext{LCA}(S.top(),x))
(mathbf{while} S.size()>1 mathbf{and} ancestor.dep<S[S.size()-1].dep)
(quad ext{ADD_EDGE}(S[S.size()-1],S.top()))
(quad S.pop())
(mathbf{if} ancestor.dep<S.top().dep)
(quad ext{ADD_EDGE}(ancestor,S.top()))
(quad S.pop())
(mathbf{if} S.empty() mathbf{or} S.top()
e ancestor)
(quad S.push(ancestor))
(S.push(x))
C++实现如下:
inline void insert(int x) // x为节点的编号
{
if(top==0) // 用数组stk模拟栈,top为栈顶指针
{
stk[top=1]=x;
return;
}
int ancestor=LCA(stk[top],x);
while((top>1)&&(dep[ancestor]<dep[stk[top-1]]))
{
add_edge(stk[top-1],stk[top]);
--top;
}
if(dep[ancestor]<dep[stk[top]])
add_edge(ancestor,stk[top--]);
if((!top)||(stk[top]!=ancestor))
stk[++top]=ancestor;
stk[++top]=x;
}
正确性
对于任意指定两点(a,b)的LCA,都存在DFS序连续的两点(u,v(u.dfnle v.dfn)),分别属于LCA包含(a,b)的两棵子树,此时(v)加入时的操作必定会使LCA入栈,所以所要求加入的点必然都加入了.对于非LCA点,按照上面的操作是不会出现这个点的,所以树的大小是最小的.
复杂度
由于每个指定点进栈出栈各一次,这部分复杂度为(O(sum k)).排序和求LCA的复杂度为(O(sum klog k)).
构建完成后的应用
以例题为例介绍虚树的使用.首先特判掉无解情况(即一个点和他的父亲都被指定).构造好虚树后,我们给真正被指定的点的节点个数(siz)设置成(1)(因为有一些加入的点实际上只是LCA,要区分开来),然后DFS这棵虚树.
以下所说的节点(u)可达是指有一个指定节点可以到达(u)(在执行了下面的删点之后)
对于一个被指定的点(u),如果存在孩子(v)可达,那么意味着(u,v)不删点就出现了连通,所以(u,v)上随便去掉一个点就可以了(这里要(ansleftarrow ans+1)),如果孩子不可达,那就不用处理了.
对于一个未被指定的点(u),统计有多少个孩子(v)可达.如果只有一个,把(u)设置成可达的就好了(相当于看上面的情况决定是否处理).如果超过一个,那把(u)删掉就好了(这里也要(ansleftarrow ans+1)).
单个询问的伪代码如下:
(//ans ext{ is a global variable to store the result})
( ext{VIRTUAL_TREE_DFS}(x):)
(mathbf{if} x.size
e 0)
(quadmathbf{for} each e mathbf{in} x.adjacency:)
(quadquad ext{VIRTUAL_TREE_DFS}(e.to))
(quadquadmathbf{if} e.to.size
e 0:)
(quadquadquad e.to.sizeleftarrow 0)
(quadquadquad ansleftarrow ans+1)
(mathbf{else}:)
(quadmathbf{for} each e mathbf{in} x.adjacency:)
(quadquad ext{VIRTUAL_TREE_DFS}(e.to))
(quadquad x.sizeleftarrow x.size+e.to.size)
(quadquad e.to.sizeleftarrow 0)
(quadmathbf{if} x.size>1:)
(quadquad ansleftarrow ans+1)
(quadquad x.sizeleftarrow 0)
(x.adjacency.clear())
事实上难点完全在于建虚树.
算法总复杂度(O(n+sum klog k)),如果用非(O(1))的LCA要多一个(sum klog n),如果用倍增ST表LCA要多一个(nlog n).
注意在最后一遍DFS虚树时,要把边清空,具体只需要修改头指针(对于vector直接erase)就可以了.如果对每个询问暴力memset会导致复杂度退化为(O(nq)).
完整C++代码如下:
const int Maxn=1e5+7,Maxm=2e5+7;
struct Edge
{
int nxt,to;
}e[Maxm];
int a[Maxn],head[Maxn],dfn[Maxn],top[Maxn],son[Maxn],siz[Maxn],f[Maxn],dep[Maxn];
int stk[Maxn];
int n,m,q,tp,cnt,ans;
/*
树链剖分部分
*/
inline void add_edge(int x,int y)
{
e[++cnt].nxt=head[x];
e[cnt].to=y;
head[x]=cnt;
}
inline void DFS1(int x)
{
siz[x]=1;
for(int i=head[x];i;i=e[i].nxt)
{
int u=e[i].to;
if(u==f[x])
continue;
dep[u]=dep[x]+1;
f[u]=x;
DFS1(u);
siz[x]+=siz[u];
if(son[x]==0||siz[son[x]]<siz[u])
son[x]=u;
}
}
inline void DFS2(int x)
{
dfn[x]=++cnt;
if(son[x])
{
top[son[x]]=top[x];
DFS2(son[x]);
for(int i=head[x];i;i=e[i].nxt)
if((e[i].to!=f[x])&&(e[i].to!=son[x]))
DFS2(top[e[i].to]=e[i].to);
}
}
inline int LCA(int x,int y)
{
while(top[x]!=top[y])
if(dep[top[x]]>dep[top[y]])
x=f[top[x]];
else
y=f[top[y]];
return dep[x]<dep[y]?x:y;
}
/*
树链剖分部分完
*/
inline void quick_sort(int l,int r)
{
int i=l,j=r,mid=dfn[a[l+r>>1]];
while(i<=j)
{
while(dfn[a[i]]<mid)
++i;
while(dfn[a[j]]>mid)
--j;
if(i<=j)
swap(a[i++],a[j--]);
}
if(i<r)
quick_sort(i,r);
if(l<j)
quick_sort(l,j);
}
inline void insert(int x)
{
if(tp==0)
{
stk[tp=1]=x;
return;
}
int ance=LCA(stk[tp],x);
while((tp>1)&&(dep[ance]<dep[stk[tp-1]]))
{
add_edge(stk[tp-1],stk[tp]);
--tp;
}
if(dep[ance]<dep[stk[tp]])
add_edge(ance,stk[tp--]);
if((!tp)||(stk[tp]!=ance))
stk[++tp]=ance;
stk[++tp]=x;
}
inline void DFS3(int x)
{
if(siz[x])
for(int i=head[x];i;i=e[i].nxt)
{
int u=e[i].to;
DFS3(u);
if(siz[u])
{
siz[u]=0;
++ans;
}
}
else
{
for(int i=head[x];i;i=e[i].nxt)
{
int u=e[i].to;
DFS3(u);
siz[x]+=siz[u];
siz[u]=0;
}
if(siz[x]>1)
{
++ans;
siz[x]=0;
}
}
head[x]=0;
}
int main()
{
scanf("%d",&n);
for(int i=1,x,y;i<=n-1;++i)
{
scanf("%d%d",&x,&y);
add_edge(x,y);
add_edge(y,x);
}
cnt=0;
DFS1(dep[1]=1);
DFS2(top[1]=1);
memset(head+1,0,n<<2);
memset(siz+1,0,n<<2);
scanf("%d",&q);
cnt=0;
for(;q--;)
{
int x=1;
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
scanf("%d",a+i);
siz[a[i]]=1;
}
for(int i=1;i<=m;++i)
if(siz[f[a[i]]])
{
puts("-1");
x=0;
break;
}
if(!x)
{
while(m)
siz[a[m--]]=0;
continue;
}
ans=0;
quick_sort(1,m);
if(a[1]!=1)
stk[tp=1]=1;
for(int i=1;i<=m;++i)
insert(a[i]);
if(tp)
while(--tp)
add_edge(stk[tp],stk[tp+1]); // 回溯过程
DFS3(1);
siz[1]=cnt=0;
printf("%d
",ans);
}
}