Alioth_ 的博客

Alioth_ 的博客

虚树总结

posted on 2019-02-15 20:09:12 | under 知识点 |

虚树

有时在做树形$DP$的时候 会出现多组询问 每一组询问指定$m$个点做修改或者别的东西 且$n$与$\sum m$同阶 这样的话普通的树形$DP$需要$\Theta(nm)$的复杂度 肯定是过不了 这时就会用到虚树

注意$n$与$\sum m$同阶 每次只是修改$m$个点 这时候就需要用到$\Theta(\sum m)$的算法——虚树

原来的树形$DP$是在原树上$DP$ 跑一边需要$\Theta(n)$ 这样太慢了 注意到每次修改$m$个点 我们就在虚树上保留$m$个点 称为关键点 和他们的$lca$(为了连成一棵树)其他的点合并 这样每次就形成了一棵总复杂度为$\sum m$的虚树 有效地降低了复杂度

如图 红点是关键点 蓝点是$lca$

构建

我们先在原树上求出$dfs$序 然后把所有的关键点按照$dfs$序排序

这是我们用一个栈来维护 栈中维护一条链 每次插入时 用新点和栈顶的$lca$的$dfn$和栈中第二个点的$dfn$比较 来判断这条链有没有拐弯

若拐弯了 则说明上一个子树已经遍历完 可以构建 我们就不断弹出节点并连边 直到处理完子树 这个判断要用栈中第二个点和$lca$比较 看他是不是在$lca$下面 如果处理完了 还要判断一下子树中是否还有点 如果有 就连$lca$和它 最后把新的点加入栈即可

若没有拐弯 直接加入栈中返回就行了(等处理完这棵子树再连边)

关键点不一定是虚树的叶子结点

就这样

void insert(int x)//栈中维护的是一条链!!!!!
{
    int lca=LCA(s[top],x);
    while(top>1&&dfn[s[top-1]]>=dfn[lca])add_edge(s[top-1],s[top]),top--;//s[top]的子树已经遍历完 可以弹出这条链使他拐弯并连s[top]子树中的边
    if(lca!=s[top])add_edge(lca,s[top]),s[top]=lca;//弹完后 若栈顶不是lca 则lca一定在他上面 且他是这个子树中最后一个点 连边 加入lca
    s[++top]=x;
}

一些技巧

$1$.连完边后$s[1]$即为$root$ 这个可以确定虚树的根 如果强制以什么东西为根 直接在加入$a$数组前把他加到栈里就行了

$2$.有些题一条链上的点可以合并 如果新加入的点的$lca$是$s[top]$就不用管直接$return$即可

$3$.注意每次构建虚树后要清空连的虚边 新建的边可以用一个$vector$保存 在最后一次在虚树上的$dfs$中直接$v.clear()$即可

$4$.注意虚树上的点和虚树之外的点要分别$DP$

例题

$1.P3320$寻宝游戏

这题主要是理解虚树思想 其实不用建出虚树 由于每条边遍历两遍的特殊性质 直接用一个$set$维护一下就行了

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int maxn=100000+100;

struct edge{
    int to,next,w;
}e[maxn<<1];

int head[maxn],tot,n,m,ans,DIS[maxn],siz[maxn],bz[maxn],fa[maxn],dfn[maxn],id,son[maxn],dep[maxn],topf[maxn];

void add(int x,int y,int z)
{
    e[++tot].to=y;
    e[tot].w=z;
    e[tot].next=head[x];
    head[x]=tot;
}

struct node{
    int id;
};

bool operator <(const node a,const node b)
{
    return dfn[a.id]<dfn[b.id]; 
}

set<node> s;

void dfs1(int x,int f)
{
    siz[x]=1;
    fa[x]=f;
    for(int i=head[x];i;i=e[i].next)
    {
        int y=e[i].to;
        if(y==f)continue;
        dep[y]=dep[x]+1;
        DIS[y]=DIS[x]+e[i].w;
        dfs1(y,x);
        siz[x]+=siz[y];
        if(siz[y]>siz[son[x]])son[x]=y;
    }
}

void dfs2(int x,int tp)
{
    topf[x]=tp;
    dfn[x]=++id;
    if(!son[x])return ;
    dfs2(son[x],tp);
    for(int i=head[x];i;i=e[i].next)
    {
        int y=e[i].to;
        if(y==fa[x]||y==son[x])continue;
        dfs2(y,y);
    }
}

inline int lca(int x,int y)
{
    while(topf[x]!=topf[y])
    {
        if(dep[topf[x]]>dep[topf[y]])x=fa[topf[x]];
        else
        y=fa[topf[y]];
    }
    if(dep[x]<dep[y])swap(x,y);
    return y;
}

inline int dis(int x,int y)
{
    return DIS[x]+DIS[y]-2*DIS[lca(x,y)];
}

inline set<node>::iterator last(set<node>::iterator Pos)
{
    if(Pos==s.begin())Pos=s.end();
    Pos--;
    return Pos;
}

inline set<node>::iterator next(set<node>::iterator Pos)
{
    Pos++;
    if(Pos==s.end())Pos=s.begin();
    return Pos;
}

std::set<node>::iterator l,r;

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=m;i++)
    {
        int u;
        scanf("%lld",&u);
        if(s.find((node){u})!=s.end())
        {
            if(s.size()!=1)
            {
                l=r=s.find(node{u});
                l=last(l),r=next(r);
                ans-=dis(u,(*l).id)+dis(u,(*r).id);
                ans+=dis((*l).id,(*r).id);
            }
            s.erase((node){u});
        }
        else
        {
            s.insert((node){u});
            if(s.size()!=1)
            {
                l=r=s.find((node){u});
                l=last(l),r=next(r);
                ans+=dis(u,(*l).id)+dis(u,(*r).id);
                ans-=dis((*l).id,(*r).id);
            }
        }
        printf("%lld\n",ans);
    }
}

$2.P2495$消耗战

这题也有点特殊 每次只用$DP$虚树上的点 同时建虚树时一条链上的点也可以合并 且强制以$1$为根 不够典型 但$DP$好写

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn=250001;

int n,m;

struct edge{
    int next,to,w,from;
}e[maxn<<1];

int head[maxn],num;

inline void add(int x,int y,int z)
{
    e[++num].to=y;
    e[num].from=x;
    e[num].w=z;
    e[num].next=head[x];
    head[x]=num;
}

vector<int>v[maxn];

inline void add_edge(int x,int y)
{
    v[x].push_back(y);
}

int a[maxn],dfn[maxn],top,topf[maxn],siz[maxn],son[maxn],s[maxn],fa[maxn],deep[maxn],id;
ll mn[maxn];

void dfs1(int x,int f)
{
    siz[x]=1;
    fa[x]=f;
    for(int i=head[x];i;i=e[i].next)
    {
        int y=e[i].to;
        if(y==f)continue;
        deep[y]=deep[x]+1;
        mn[y]=min(mn[x],(ll)e[i].w);
        dfs1(y,x);
        siz[x]+=siz[y];
        if(siz[y]>siz[son[x]])son[x]=y;
    }
}

void dfs2(int x,int tp)
{
    topf[x]=tp;
    dfn[x]=++id;
    if(!son[x])return ;
    dfs2(son[x],tp);
    for(int i=head[x];i;i=e[i].next)
    {
        int y=e[i].to;
        if(y==fa[x]||y==son[x])continue;
        dfs2(y,y);
    }
}

inline bool cmp(int x,int y)
{
    return dfn[x]<dfn[y];
}

int LCA(int x,int y)
{
    while(topf[x]!=topf[y])
    {
        if(deep[topf[x]]>deep[topf[y]])x=fa[topf[x]];
        else
        y=fa[topf[y]];
    }
    if(deep[x]<deep[y])swap(x,y);
    return y;
}
//此题特殊 不做模板题
void insert(int x)//栈中维护的是一条链!!!!!
{
    if(top==1){s[++top]=x;return ;}
    int lca=LCA(s[top],x);
    if(lca==s[top])return ;//一条链上的需求点可以用第一个点替代后面的不用加入
    while(top>1&&dfn[s[top-1]]>=dfn[lca])add_edge(s[top-1],s[top]),top--;//s[top]的子树已经遍历完 可以弹出这条链使他拐弯并连s[top]子树中的边
    if(lca!=s[top])add_edge(lca,s[top]),s[top]=lca;//弹完后 若栈顶不是lca 则lca一定在他上面 且他是这个子树中最后一个点 连边 加入lca
    s[++top]=x;
}

ll dp(int x)
{
    if(!v[x].size())return mn[x];
    ll sum=0;
    for(int i=0;i<v[x].size();i++)
    {
        int y=v[x][i];
        sum+=dp(y);
    }
    v[x].clear();
    return min(sum,mn[x]);
}

int main()
{
    scanf("%d",&n);
    mn[1]=1ll<<60;
    for(int i=1;i<n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);add(y,x,z);
    }
    deep[1]=1;
    dfs1(1,0);
    dfs2(1,0);
    scanf("%d",&m);
    while(m--)
    {
        int k;
        scanf("%d",&k);
        for(int i=1;i<=k;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+1+k,cmp);
        s[top=1]=1;
        for(int i=1;i<=k;i++)insert(a[i]);
        while(top>0)
        add_edge(s[top-1],s[top]),top--;
        cout<<dp(1)<<endl;
    }
}

$3.P3233$世界树

这才是真正的模板题 虽然DP实在是太恶心 但所有的特点都体现了 比如虚树内外的点分别$DP$ 插入也比较正常 但是DP太傻逼了 调了一天

#include<bits/stdc++.h>

using namespace std;

const int maxn=309010;
const int INF=1000010000;

typedef pair<int,int>p;

struct edge{
    int next,to;
}e[maxn<<1];

int head[maxn],rt,num,fa[maxn][30];

inline void add(int x,int y)
{
    e[++num].to=y;
    e[num].next=head[x];
    head[x]=num;
}

vector<int>v[maxn];

inline void add_edge(int x,int y){v[x].push_back(y);}

int a[maxn],n,q,bo[maxn],A[maxn],up[maxn],bel[maxn],ans[maxn],dis[maxn],dfn[maxn],top,topf[maxn],siz[maxn],son[maxn],s[maxn],deep[maxn],id;

void dfs1(int x,int f)
{
    dfn[x]=++id;
    siz[x]=1;
    fa[x][0]=f;
    for(int i=head[x];i;i=e[i].next)
    {
        int y=e[i].to;
        if(y==f)continue;
        deep[y]=deep[x]+1;
        dfs1(y,x);
        siz[x]+=siz[y];
    }
}

//计算儿子对父亲的贡献 
void dfs3(int x)//dis[x]表示在以x为根的子树内,离x最近的管辖节点到x的距离 
{
    if(bo[x])
    bel[x]=x,dis[x]=0;//叶子结点管辖自己 一定是管辖点 
    else bel[x]=0,dis[x]=INF;//初值 
    for(int i=0;i<v[x].size();i++)
    {
        int y=v[x][i];
        dfs3(y);
        if(dis[y]+deep[y]-deep[x]<dis[x]||(dis[y]+deep[y]-deep[x]==dis[x]&&bel[x]>bel[y]&&bel[y]))
        {
            dis[x]=dis[y]+deep[y]-deep[x];
            bel[x]=bel[y];
        }
    }
}

//计算父亲对儿子的贡献 因为有可能被兄弟管辖 所以dfs3先到lca dfs4再下到这个节点 
void dfs4(int u,int D,int x)
{
    if(D<dis[u]||(D==dis[u]&&bel[u]>x))dis[u]=D,bel[u]=x;
    else D=dis[u],x=bel[u];//一直记录父亲的 否则记录父亲的bel 
    for(int i=0;i<v[u].size();i++)
    {
        dfs4(v[u][i],D+deep[v[u][i]]-deep[u],x);
    }
}
//处理虚树子树中的节点归谁 
void dfs5(int x)
{
    ans[bel[x]]+=siz[x];
    for(int i=0;i<v[x].size();i++)
    {
        int y=v[x][i];//x的虚树儿子 
        for(int j=18;j>=0;j--)
            if(fa[y][j]&&deep[fa[y][j]]>deep[x])y=fa[y][j];//ans[bel[x]]要减去所有x子树中有虚树节点的子树siz 只保留没有虚树节点的子树 
        ans[bel[x]]-=siz[up[v[x][i]]=y];
        dfs5(v[x][i]);
    }
}
//现在只剩下虚树边上的被我们忽略的节点没有确定归属。 

void dfs6(int x)
{
    for(int i=0;i<v[x].size();i++)
    {
        int y=v[x][i];
        if(bel[x]==bel[y]){ans[bel[x]]+=siz[up[v[x][i]]]-siz[y];dfs6(v[x][i]);continue;}
        int H=deep[bel[y]]+deep[x]-dis[x];
        H=H&1?H+1>>1:(bel[y]<bel[x]?H>>1:(H>>1)+1);
        for(int j=18;j>=0;j--)
        if(fa[y][j]&&deep[fa[y][j]]>=H)y=fa[y][j];
        ans[bel[v[x][i]]]+=siz[y]-siz[v[x][i]];
        ans[bel[x]]+=siz[up[v[x][i]]]-siz[y];
        dfs6(v[x][i]);
    }
}

void dfs7(int x)
{
    up[x]=bel[x]=dis[x]=0;
    for(int i=0;i<v[x].size();i++)dfs7(v[x][i]);
    v[x].clear();
}

inline bool cmp(int x,int y)
{
    return dfn[x]<dfn[y];
}

inline int LCA(int x,int y)
{
    if(deep[x]>deep[y])swap(x,y);//x比y浅 
    for(int i=18;i>=0;i--)
        if(deep[fa[y][i]]>=deep[x])y=fa[y][i];
    if(x==y)return x;
    for(int i=18;i>=0;i--)
        if(fa[y][i]!=fa[x][i])y=fa[y][i],x=fa[x][i];
    return fa[x][0];
}

void insert(int x)//栈中维护的是一条链!!!!!
{
    int lca=LCA(s[top],x);
    while(top>1&&dfn[s[top-1]]>=dfn[lca])add_edge(s[top-1],s[top]),top--;//s[top]的子树已经遍历完 可以弹出这条链使他拐弯并连s[top]子树中的边
    if(lca!=s[top])add_edge(lca,s[top]),s[top]=lca;//弹完后 若栈顶不是lca 则lca一定在他上面 且他是这个子树中最后一个点 连边 加入lca
    s[++top]=x;
}

int main()
{
//  freopen("10.in","r",stdin);
//  freopen("new 1.ans","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    deep[1]=1;
    dfs1(1,0);
    for(int i=1;i<=18;i++)
        for(int j=1;j<=n;j++)
            fa[j][i]=fa[fa[j][i-1]][i-1];
    scanf("%d",&q);
    while(q--)
    {
        int m;
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
            scanf("%d",&a[i]),A[i]=a[i],bo[a[i]]=1;
        sort(a+1,a+1+m,cmp);
        s[top=1]=a[1];
        for(int i=2;i<=m;i++)
        insert(a[i]);
        while(top>1)
        add_edge(s[top-1],s[top]),top--;
        rt=s[1];
        dfs3(rt);
        dfs4(rt,dis[rt],bel[rt]);
        dfs5(rt);
        dfs6(rt);
        ans[bel[rt]]+=siz[1]-siz[rt];
        for(int i=1;i<=m;i++)
            cout<<ans[A[i]]<<" ";
        cout<<endl;
        dfs7(rt);
        for(int i=1;i<=m;i++)
            bo[a[i]]=ans[a[i]]=0;
    }
}

没了