CF600E Lomsat gelral

洛咕

题意:一棵树有\(n(n<=1e5)\)个结点，每个结点都是一种颜色，每个颜色有一个编号，求树中每个子树中出现最多的颜色的编号的和.

分析:好像学习树上启发式合并都是这道入坑题吧.先放一下洛咕日报,虽然个人认为讲得并不是很清楚(可能是我太蒟蒻,最近试图去学习的一些东西看博客感觉都是在浪费时间,从来没有看懂过).

首先因为是第一篇树上启发式合并的博客,口胡一下几个核心好了.

1.把询问离线,目前为止做的树上启发式合并都是离线询问的,应该只有这样才能保证其\(nlog_n\)的时间复杂度吧.

2.两个\(dfs\),第一个\(dfs\)预处理出每个节点的重儿子,有时根据题目可能还要维护深度等信息.第二个\(dfs\)就是操作核心了:先递归处理轻儿子,然后处理重儿子,再计算整颗子树的贡献(\(update\)函数)(因为重儿子的贡献在上一步已经保留了下来,所以这里不要再重复计算进去了),最后如果这个点不是其父亲的重儿子还要消除它的贡献(还是\(update\)函数).

3.\(update\)函数也是个从上到下递归处理的过程.

回到这道题,模板还是上面这个模板,然后设\(tot[i]\)表示当前子树中i这种颜色出现的次数,\(num[i]\)表示在当前子树中有多少种颜色出现了i次,\(sum[i]\)表示当前子树中出现了i次的颜色的编号之和.然后在\(update\)时维护这几个数组即可,同时还要一个全局变量\(maxn\)来记录当前子树中出现颜色最多的次数.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e5+5;
int n,maxn,tot[N],num[N];ll sum[N],ans[N];
int a[N],size[N],son[N],visit[N];
int cnt,head[N],nxt[N<<1],to[N<<1];
inline void add(int a,int b){
    nxt[++cnt]=head[a];head[a]=cnt;to[cnt]=b;
}
inline void pre_dfs(int u,int fa){//找重儿子就不解释了
    size[u]=1;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];if(v==fa)continue;
        pre_dfs(v,u);size[u]+=size[v];
        if(size[v]>size[son[u]])son[u]=v;
    }
}
inline void update(int u,int fa,int val){
    int &t=tot[a[u]];--num[t];sum[t]-=a[u];
    t+=val;++num[t];sum[t]+=a[u];
    if(val>0)maxn=max(maxn,t);
    else if(!num[maxn])--maxn;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];if(v==fa)continue;
        if(visit[v])continue;//跳过重儿子
        update(v,u,val);
    }
}
inline void dfs(int u,int fa,int keep){//keep=0/1,表示当前节点是轻/重儿子
//keep的初始化很迷,一般都是1,但有一道题我改成0才能过
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];if(v==fa)continue;
        if(v==son[u])continue;dfs(v,u,0);//先只递归处理轻儿子
    }
    if(son[u])dfs(son[u],u,1),visit[son[u]]=1;//再单独处理重儿子
//visit标记重儿子,使得下面update时不会被计算贡献
    update(u,fa,1);//计算整颗子树的贡献,所以val=1
    ans[u]=sum[maxn];//记录这个节点的答案
    visit[son[u]]=0;//清除重儿子的标记
    if(!keep)update(u,fa,-1);//消除轻儿子产生的贡献,所以val=-1
}
int main(){
    n=read();for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<n;++i){
        int a=read(),b=read();
        add(a,b);add(b,a);
    }
    pre_dfs(1,0);dfs(1,0,1);
    for(int i=1;i<=n;++i)printf("%lld ",ans[i]);
    printf("\n");
    return 0;
}

CF600E Lomsat gelral

原文：https://www.cnblogs.com/PPXppx/p/11666759.html