Lomsat gelral

1.前言

好像写完这题这个学期的算法学习就结束了,准备考试了...只打打cf,at了.然后就没了...当然还有些群友的问题也得尽力解答...

2.树上启发式合并

这个算法是个比较简单但又很好的算法,可以解决树上的一些问题.他的优化在于重儿子只要遍历一次.轻儿子遍历两次,从而可以在nlog(n)的时间复杂度下解决树上问题.

3.算法流程

具体的算法流程是:

遍历它的轻儿子,并删除.
统计它的重儿子,并保留.
再进行一次dfs,统计其轻儿子,完成对u子树的统计.

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int col[N],cnt[N];
vector<int>v[N];
int sz[N],dfn[N],Son;
long long ans[N],mx,sum;
void dfs(int u,int fa)
{
    sz[u]=1;
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==fa) continue;
        dfs(son,u);
        sz[u]+=sz[son];
        if(sz[dfn[u]]<sz[son])    dfn[u]=son;
    }
}

void cal(int u,int fa,bool op)
{
    if(op)  cnt[col[u]]++;
    else    cnt[col[u]]--;
    if(cnt[col[u]]>mx)  mx=cnt[col[u]],sum=col[u];
    else if(cnt[col[u]]==mx)    sum+=col[u];
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==fa||son==Son)   continue;
        cal(son,u,op);
    }
}

void dfs(int u,int fa,bool op)
{
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==dfn[u]||son==fa)    continue;
        dfs(son,u,true);
    }
    if(dfn[u])  dfs(dfn[u],u,false),Son=dfn[u];
    cal(u,fa,true);
    ans[u]=sum;
    Son=0;
    if(op)
    {
        cal(u,fa,false);
        mx=0,sum=0;
    }
}

int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)   scanf("%d",&col[i]);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    dfs(1,0,true);
    for(int i=1;i<=n;i++)   printf("%lld ",ans[i]);
    puts("");
    return 0;
}