Loading...

树上启发式合并 学习笔记

check评论:0 条 remove_red_eye浏览量:343 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-12-15

树上启发式合并是一类离线处理树上问题的算法

例题

我们像树剖一样,分重儿子和轻儿子

我们先走轻儿子并计算答案,但是不计算是否重复的标记

再走一次重儿子,计算标记

最后走轻儿子,合并答案,每次$O(1)$回答

#include <bits/stdc++.h>
using namespace std;
int fa[100010],son[100010],cnt[100010],ans[100010],head[100010],siz[100010],c[100010],n;
struct edge
{
    int next,to;
}e[200020];
void add(int u,int v)
{
    head[0]++;
    e[head[0]].to=v;
    e[head[0]].next=head[u];
    head[u]=head[0];
}
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;
        }
        fa[v]=u;
        dfs1(v);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
        {
            son[u]=v;
        }
    }
}
int dfs2(int u,int h,int keep)
{
    if(keep)
    {
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(v==fa[u]||v==son[u])
            {
                continue;
            }
            dfs2(v,0,1);
        }
    }
    int tmp=0;
    if(!keep&&son[u])
    {
        tmp+=dfs2(son[u],1,0);
    }
    else if(son[u])
    {
        tmp+=dfs2(son[u],1,1);
    }
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u]||v==son[u])
        {
            continue;
        }
        tmp+=dfs2(v,0,0);
    }
    if(!cnt[c[u]])
    {
        tmp++;
    }
    cnt[c[u]]=1;
    if(keep)
    {
        ans[u]=tmp;
    }
    if(keep&&!h)
    {
        memset(cnt,0,sizeof(cnt));
    }
    return tmp;
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
    }
    dfs1(1);
    dfs2(1,0,1);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        printf("%d\n",ans[x]);
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名