【CF600E】Lomsat gelral

题目大意：给定一棵 N 个节点的有根树，1 号节点为根节点，点有点权，求对于每个节点为根的子树中，出现次数最多的点权的和是多少。

题解：子树询问问题可以采用离线+线段树合并
线段树维护区间颜色出现次数最大值和区间颜色出现次数最大的点权和，合并通过比较左右子区间出现的最大次数讨论即可。

代码如下

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=1e5+10;
typedef long long LL;

int n,cor[maxn];
LL ans[maxn];
vector<int> G[maxn];
struct node{
    #define ls(x) t[x].lc
    #define rs(x) t[x].rc
    int lc,rc,cnt; LL sum;
}t[maxn*20];
int tot,rt[maxn];
inline void pushup(int o){
    if(t[ls(o)].cnt==t[rs(o)].cnt)t[o].cnt=t[ls(o)].cnt,t[o].sum=t[ls(o)].sum+t[rs(o)].sum;
    else if(t[ls(o)].cnt>t[rs(o)].cnt)t[o].cnt=t[ls(o)].cnt,t[o].sum=t[ls(o)].sum;
    else t[o].cnt=t[rs(o)].cnt,t[o].sum=t[rs(o)].sum;
}
void insert(int &o,int l,int r,int pos){
    if(!o)o=++tot;
    if(l==r){t[o].sum=l,++t[o].cnt;return;}
    int mid=l+r>>1;
    if(pos<=mid)insert(ls(o),l,mid,pos);
    else insert(rs(o),mid+1,r,pos);
    pushup(o);
}
int merge(int x,int y,int l,int r){
    if(!x||!y)return x+y;
    if(l==r){t[x].sum=l,t[x].cnt+=t[y].cnt;return x;}
    int mid=l+r>>1;
    ls(x)=merge(ls(x),ls(y),l,mid);
    rs(x)=merge(rs(x),rs(y),mid+1,r);
    return pushup(x),x;
}

void dfs(int u,int fa){
    for(auto v:G[u]){
        if(v==fa)continue;
        dfs(v,u);
        rt[u]=merge(rt[u],rt[v],1,n);
    }
    insert(rt[u],1,n,cor[u]);
    ans[u]=t[rt[u]].sum;
}

void read_and_parse(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&cor[i]);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].pb(y),G[y].pb(x);
    }
}
void solve(){
    dfs(1,0);
    for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
}
int main(){
    read_and_parse();
    solve();
    return 0;
} 

【CF600E】Lomsat gelral

原文：https://www.cnblogs.com/wzj-xhjbk/p/11005085.html