虚树

前情提要：本文中括号较多，有的括号表示补充说明，有的括号将定语分层方便阅读理解。

首先列一个树上问题解决表（并不是很全）。

多想想dfs栈和dfs作差。

询问	解决思路
整棵树的问题	自底向上树上贪心/树形DP
链上问题	树链剖分
子树问题	线段树合并/dsu on tree/dfs序转成区间问题
给定点集询问	建虚树
涉及加边删边	LCT

静态虚树

虚数的大小为 $O(m)$ （m为关键点数量），具体来说， $m \leq \text{虚树大小} \leq \min(2m-1,n)$ 。

虚树上的点都是原树上的点，但虚树上的边可能是原树的多条边缩成的。

具体来说，虚树首先包含了所有关键点，其次，虚树还包含了所有（有两个及以上（子树中含关键点）的儿子）的非关键点。

可以理解成关键点往上跑的时候在这些点交汇。

虚树中并不包含（仅有一个（子树中含关键点）的儿子）的非关键点，因为虚树上这个点的存在是不必要的，我们可以把它与父亲的连边和它与关键儿子（即子树中含关键点的儿子）的连边接在一起变成一条边，从而舍弃这个节点，来保证我们虚树的大小为 $O(m)$ 。

举个例子，譬如说下面这棵树的2和5是关键点：

那么这棵树的虚树是：

下面我们给出基于倍增求 $LCA$ 的 $O(mlogn)$ 的虚树的建立方法：

（虚树点集序列记为 $v$ ，边集序列记为 $e$ ）

将所有关键点按dfs序排序并加入 $v$ 。
$\forall i\in [1,m-1],$ 将 $LCA(v_i,v_{i+1})$ 加入 $v$ 。
对 $v$ 排序去重。
$\forall i\in [2,size(v)],$ 将 $LCA(v_{i-1},v_{i})\rightarrow v_i$ 加入 $e$ 。

注意：由于该算法复杂度小于 $O(n)$ ，故清空虚树数组时务必使用 $O(m)$ 的处理方式。

下面给出例题CF631D的AC Code：

// Problem: CF613D Kingdom and its Cities
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF613D
// Memory Limit: 250 MB
// Time Limit: 2000 ms

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char *p1,*p2,buf[1<<21];
int read()
{
    int s=0,w=0;char ch=getchar();
    while(ch<'0'||ch>'9') w|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return w?-s:s;
}
const int N=1e5+5,M=2e5+5;
int n,k,cnt,u[M],v[M],start[N],Next[M],f[N][21],dep[N],dfn[N],tot,vis[N],V[M];
vector<int> G[N];
void add(int x,int y)
{
    u[++cnt]=x;v[cnt]=y;Next[cnt]=start[x];start[x]=cnt;
}
void dfs(int x)
{
    dep[x]=dep[f[x][0]]+1;
    dfn[x]=++tot;
    for(int i=start[x];i;i=Next[i])
    {
        if(v[i]==f[x][0]) continue;
        f[v[i]][0]=x;
        dfs(v[i]);
    }
}
int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int j=20;j>=0;j--) if(dep[f[x][j]]>=dep[y]) x=f[x][j];
    if(x==y) return x;
    for(int j=20;j>=0;j--) if(f[x][j]!=f[y][j]) x=f[x][j],y=f[y][j];
    return f[x][0];
}
void add1(int x,int y)
{
    G[x].pb(y);
}
int ans;
void dfs1(int x,int fa)
{
    int sum=0;
    for(int y:G[x])
    {
        dfs1(y,x);sum+=vis[y];
    }
    if(vis[x]) ans+=sum;
    else
    {
        if(sum>=2||(vis[fa]&&sum>=1)) ans++;
        else vis[x]=sum;
    }
}
void clear()
{
    for(int i=1;i<=k;i++) vis[V[i]]=0,G[V[i]].clear();
    ans=0;
}
int main()
{
    n=read();
    for(int i=1,x,y;i<=n-1;i++) x=read(),y=read(),add(x,y),add(y,x);
    dfs(1);
    for(int j=1;j<=20;j++) for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
    for(int m=read(),flag;m--;)
    {
        k=read();flag=0;
        for(int i=1;i<=k;i++) vis[V[i]=read()]=1;
        for(int i=1;i<=k;i++) if(vis[f[V[i]][0]]) {puts("-1");flag=1;break;}
        if(flag) {clear();continue;}
        sort(V+1,V+k+1,[](int x,int y){return dfn[x]<dfn[y];});
        for(int i=1,tk=k;i<=tk-1;i++) V[++k]=lca(V[i],V[i+1]);
        sort(V+1,V+k+1,[](int x,int y){return dfn[x]<dfn[y];});
        k=unique(V+1,V+k+1)-V-1;
        for(int i=2;i<=k;i++) add1(lca(V[i-1],V[i]),V[i]);
        dfs1(V[1],0);cout<<ans<<endl;
        clear();
    }
    return 0;
}

动态虚树（trick：虚树大小为任意dfs序上相邻关键点（第一个和最后一个也算）距离和/2）

在刚刚的静态虚树中，我们把虚树建了出来，但如果动态往点集中加点的话，虚树的复杂度和输入复杂度就不对等了，所以借鉴刚刚的思想，我们可以用 $set$ 维护一个虚树点集而不维护边集，从而实现动态加点同时维护一些值，同时码量短了许多。

据说可以分好多种情况，不过OI中神奇的事情就是很多时候可以用一份代码囊括多种情况~

~~（p.s. stO 小粉兔 Orz 我尝试对题解区兔队的题解进行修改，结果发现这份代码已经是简洁精妙的极致）~~

下面给出例题P3320 [SDOI2015]寻宝游戏的AC Code：

// Problem: P3320 [SDOI2015]寻宝游戏
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3320
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include<bits/stdc++.h>
#define dis(x,y) (dis[dfx[x]]+dis[dfx[y]]-2*dis[lca(dfx[x],dfx[y])])
using namespace std;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char *p1,*p2,buf[1<<21];
int read()
{
    int s=0,w=0;char ch=getchar();
    while(ch<'0'||ch>'9') w|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return w?-s:s;
}
const int N=1e5+5,M=2e5+5;    
int n,m,q,cnt,u[M],v[M],w[M],start[N],Next[M],dep[N],dfn[N],dfx[N],tot,f[N][21],vis[N];
long long ans,dis[N],d;
set<int> s;
void add(int x,int y,int z)
{
    u[++cnt]=x;v[cnt]=y;w[cnt]=z;Next[cnt]=start[x];start[x]=cnt;
}
void dfs(int x)
{
    dep[x]=dep[f[x][0]]+1;
    dfn[x]=++tot;dfx[tot]=x;
    for(int i=start[x];i;i=Next[i])
    {
        if(v[i]==f[x][0]) continue;
        f[v[i]][0]=x;
        dis[v[i]]=dis[x]+w[i];
        dfs(v[i]);
    }
}
int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int j=20;j>=0;j--) if(dep[f[x][j]]>=dep[y]) x=f[x][j];
    if(x==y) return x;
    for(int j=20;j>=0;j--) if(f[x][j]!=f[y][j]) x=f[x][j],y=f[y][j];
    return f[x][0];
}
int main()
{
    n=read();m=read();
    for(int i=1,x,y,z;i<=n-1;i++) x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
    dfs(1);
    for(int j=1;j<=20;j++) for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
    set<int>::iterator it;
    for(int x,y,z;m--;)
    {
        x=dfn[read()];
        if(!vis[x]) s.insert(x);
        y=((it=s.lower_bound(x))==s.begin()?*--s.end():*--it);
        z=((it=s.upper_bound(x))==s.end()?*s.begin():*it);
        if(vis[x]) s.erase(x);
        d=dis(x,y)+dis(x,z)-dis(y,z);
        if(vis[x]) vis[x]=0,ans-=d;
        else vis[x]=1,ans+=d;
        cout<<ans<<endl;
    }
    return 0;
}

取其精华：

#define dis(x,y) (dis[dfx[x]]+dis[dfx[y]]-2*dis[lca(dfx[x],dfx[y])])
for(int x,y,z;m--;)
{
    x=dfn[read()];
    if(!vis[x]) s.insert(x);
    y=((it=s.lower_bound(x))==s.begin()?*--s.end():*--it);
    z=((it=s.upper_bound(x))==s.end()?*s.begin():*it);
    if(vis[x]) s.erase(x);
    d=dis(x,y)+dis(x,z)-dis(y,z);
    if(vis[x]) vis[x]=0,ans-=d;
    else vis[x]=1,ans+=d;
    cout<<ans/2<<endl;
}

此代码就是给定边权动态求虚树大小的模板（注意最后的ans/2）。

动态虚树不可完全替代虚树，许多需要将树建出来再处理的问题仍需要用静态虚树。

有的时候我们也需要简单小巧的 $O(n)$ 建虚数，如下：

F(i,1,m) vis[p[i]]=1;
for(int i=1,x;i<=m;i++) {
    for(x=p[i];!tg[x];x=fa[x]) tg[x]=p[i];
    if(!vis[x]) nw.Add(x,tg[x]),p[++m]=x,vis[x]=1;
    nw.Add(x,p[i]);
}

注意多出来的点也是需要向上跳的，所以 i<=m 的条件是一个动态条件。