Loading...

虚树 学习笔记

check评论:1 条 remove_red_eye浏览量:52 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-09-22

菜deco终于学了虚树

丢一道不是纯板子的板子

就以这道题为例,首先我们考虑树形$dp$

先$dfs$一遍,统计出每个点到根节点路径上边的最小权值

然后$dp$转移$f[u]=min(dis[u],\sum dp(son))$

如果是标记结点就返回$dis$,这样的复杂度是$O(nm)$的,显然过不了

不过我们注意到,被选出来的总点数$\sum k$,满足$\sum k \leq 500000$

考虑到每次$dp$都会有很多无用结点,我们想个方法来提取出有用的结点以降低复杂度,虚树诞生了

虚树只包含了关键结点,即我们选中的结点和他们的$lca$,来建立一颗新树后$dp$即可

可以证明新的结点个数不多于$\sum k*2$,这里不证明了

我们每次将所有的点按$in$,即$dfs$序排序,然后用一个栈来建边,一开始栈顶元素为根

当$top=1$时,显然直接加入栈

否则,取当前插入结点记作$x$,求出$LCA=lca(x,st[top])$,若$LCA=st[top]$,则直接插入$x$即可

否则,我们一直由$st[top-1]$向$st[top]$连边,直到$top=1$或$in[st[top-1]]<in[LCA]$

连边结束后,若$st[top]!=LCA$,则由$LCA$向$st[top]$连边并将$st[top]$赋值为$LCA$,因为此时代表我们进入了以$LCA$为根的子树

然后将$x$推进栈即可

建树完成后,树形$dp$即可

对于消耗战这题来说,因为割掉祖先边显然更优,所以当$LCA=st[top]$的时候就无需将当前结点进栈了

总复杂度$O(\sum k log n+2*\sum k)$

还是挺好写的

$code:$

/*deco loves Chino*/
#include <bits/stdc++.h>
using namespace std;
int head[500010],cnt,dp[500010],mak[500010],n,top;
struct edge
{
    int next,to,dis;    
}e[1000010];
vector<int> vc[500010];
int siz[500010],son[500010],dep[500010],fa[500010],topp[500010],in[500010],st[500010];
void add(int u,int v,int dis)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].dis=dis;
    head[u]=cnt;
}
void addd(int u,int v)
{
    vc[u].push_back(v);
}
void dfs1(int u)
{
    siz[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u])
        {
            continue;
        }
        dep[v]=dep[u]+1;
        dp[v]=min(dp[u],e[i].dis);
        fa[v]=u;
        dfs1(v);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
        {
            son[u]=v;
        }
    }
}
void dfs2(int u,int tp)
{
    in[u]=++cnt;
    topp[u]=tp;
    if(son[u])
    {
        dfs2(son[u],tp);
    }
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==son[u]||v==fa[u])
        {
            continue;   
        } 
        dfs2(v,v);
    }
}
int lca(int x,int y)
{
    while(topp[x]!=topp[y])
    {
        if(dep[topp[x]]<dep[topp[y]])
        {
            swap(x,y);
        }
        x=fa[topp[x]];
    }
    if(dep[x]<dep[y])
    {
        swap(x,y);
    }
    return y;
}
bool cmp(int x,int y)
{
    return in[x]<in[y];
}
void insert(int x)
{
    if(top<=1)
    {
        st[++top]=x;
        return ;
    }
    int pwp=lca(x,st[top]);
    if(pwp==st[top])
    {
        //st[++top]=x;
        return ;
    }
    while(top>1&&in[st[top-1]]>=in[pwp])
    {
        addd(st[top-1],st[top]);
        top--;
    }
    if(st[top]!=pwp)
    {
        addd(pwp,st[top]);
        st[top]=pwp;
    }
    st[++top]=x;
}
int dodp(int u)
{
    if(vc[u].size()==0)
    {
        return dp[u];    
    } 
    int ans=0;
    for(int i=0;i<vc[u].size();i++)
    {
        ans+=dodp(vc[u][i]);
    }
    vc[u].clear();
    return min(ans,dp[u]);
}
int main()
{
    cin>>n;
    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);
    }   
    dp[1]=0x3f3f3f3f;
    cnt=0;
    dfs1(1);
    dfs2(1,1);
    int m;
    cin>>m;
    while(m--)
    {
        int qwq;
        scanf("%d",&qwq);
        for(int i=1;i<=qwq;i++)
        {
            scanf("%d",&mak[i]);
        }
        sort(mak+1,mak+qwq+1,cmp);
        st[top=1]=1;
        for(int i=1;i<=qwq;i++)
        {
            insert(mak[i]); 
        }
        while(top>1)
        {
            addd(st[top-1],st[top]);
            top--;
        }
        cout<<dodp(1)<<endl;
    }
}

chevron_left 哇 没了
CF915E 题解 chevron_right

仅有一条评论

正在回复给  
去登陆?

   点击刷新验证码

    deco
    2019 - 10 - 10 18 : 53

    wtcl qaq

标签云

文章留名