题解归档 - cf600E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf600E
• 本地来源：problems/cf600E/idea.md
• 题目链接：https://codeforces.com/contest/600/problem/E
• 原始标题：600E Lomsat gelral

思路

600E Lomsat gelral

题意

给定以 1 为根的 (n) 个结点树，每点颜色 (c_i\in[1,n])。对结点 (v)，定义颜色 (c) 在 (v) 的子树中主导：不存在其他颜色出现次数严格多于 (c)。可能有多种颜色同时主导。求每个 (v) 子树内所有主导颜色之和。

思路：DSU on Tree（树上启发式合并 / Sack）

朴素对每个 (v) 扫子树统计颜色频次 (O(n^2))。经典优化：

1. 第一次 DFS（dfs1）：算子树大小 sz[v]，记录重儿子 hvy[v]（子树最大的儿子）。

2. 第二次 DFS（dfs2）按「轻儿子清空、重儿子保留」：

   • 先递归所有轻儿子并 keep=0（返回时清空该子树贡献）；
   • 再递归重儿子 keep=1（保留频次表）；
   • add(v) 加入当前点；
   • 对每个轻儿子 dfs_add 把其子树重新加入全局频次表；
   • ans[v] = sm（当前最大频次对应颜色之和）；
   • 若 keep=0 则 clr(v) 清空整棵子树贡献。

维护全局 cnt[c]、最大频次 mx、主导颜色和 sum：

• 加入 add(v)：cnt[c]++；更新 mx,sum。
• 清空轻子树：mx=0,sum=0 后 clear(v) 递归将子树内 cnt[a[x]] 置 0（只在 keep=0 返回时调用，均摊 (O(n\log n))）。

模板

lib/图论(DSU-on-tree).cpp（Catalog 缺口，AC 后沉淀）。

核心骨架：

void dfs1(ll v,ll f){ /* sz, hvy */ }
void add(ll v){ /* cnt, mx, sm */ }
void addsub(ll v,ll f){ add(v); for(son) addsub(son,v); }
void clear(ll v,ll f){ cnt[a[v]]=0; for(son) clear(son,v); }
void dfs2(ll v,ll f,ll pd){
    for(light son) dfs2(son,v,0);
    if(hv[v]!=-1) dfs2(hv[v],v,1);
    for(light son) addsub(son,v);
    add(v);
    f[v]=sum;
    if(pd==0){ mx=0,sum=0; clear(v,f); }
}

复杂度

• 时间：(O(n\log n))（每个点在轻边路径上最多被加入/删除 (O(\log n)) 次）
• 空间：(O(n))

验证

• 样例 1、2：✅（本地 build/cf600E_solution.exe）
• 对拍：brute.cpp + gen.cpp，随机树 (n\le 80)，50 组通过，本地 50 组通过

结果

• AC（1 次提交，daemon 自动交题）
• Catalog 模板已沉淀：lib/图论(DSU-on-tree).cpp

代码

来源：problems/cf600E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 02:41:30
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005;
vector<ll>ss[maxn];
ll a[maxn],sz[maxn],hv[maxn],f[maxn],cnt[maxn+5];
ll mx,sum;
void add(ll x){
    ll zc=a[x];
    cnt[zc]++;
    if(cnt[zc]>mx){
        mx=cnt[zc];
        sum=zc;
    }else if(cnt[zc]==mx){
        sum+=zc;
    }
}
void addsub(ll x,ll fa){
    add(x);
    ll i,zc;
    for(i=0;i<(ll)ss[x].size();i++){
        zc=ss[x][i];
        if(zc==fa) continue;
        addsub(zc,x);
    }
}
void clear(ll x,ll fa){
    cnt[a[x]]=0;
    ll i,zc;
    for(i=0;i<(ll)ss[x].size();i++){
        zc=ss[x][i];
        if(zc==fa) continue;
        clear(zc,x);
    }
}
void dfs1(ll x,ll fa){
    sz[x]=1;
    hv[x]=-1;
    ll i,zc,zc1=0;
    for(i=0;i<(ll)ss[x].size();i++){
        zc=ss[x][i];
        if(zc==fa) continue;
        dfs1(zc,x);
        sz[x]+=sz[zc];
        if(sz[zc]>zc1){
            zc1=sz[zc];
            hv[x]=zc;
        }
    }
}
void dfs2(ll x,ll fa,ll pd){
    ll i,zc;
    for(i=0;i<(ll)ss[x].size();i++){
        zc=ss[x][i];
        if(zc==fa or zc==hv[x]) continue;
        dfs2(zc,x,0);
    }
    if(hv[x]!=-1) dfs2(hv[x],x,1);
    for(i=0;i<(ll)ss[x].size();i++){
        zc=ss[x][i];
        if(zc==fa or zc==hv[x]) continue;
        addsub(zc,x);
    }
    add(x);
    f[x]=sum;
    if(pd==0){
        mx=0,sum=0;
        clear(x,fa);
    }
}
int main(){
    ll n,i,x,y;
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    for(i=1;i<=n-1;i++){
        cin>>x>>y;
        ss[x].push_back(y);
        ss[y].push_back(x);
    }
    dfs1(1,0);
    dfs2(1,0,1);
    for(i=1;i<=n;i++){
        cout<<f[i];
        if(i<n) cout<<" ";
    }
    cout<<"\n";
    return 0;
}