CodeForces

分析

树上启发式合并板子题。

维护一个 $cnt_i$ 表示第 $i$ 种颜色的出现次数,$num_i$ 表示有多少种颜色出现 $i$ 次,$sum_i$ 表示所有颜色出现 $i$ 次的节点的编号和。这样子计算贡献显然是 $O(1)$ 的。

那么在树上 DFS,重复以下过程:

  • 递归处理所有轻儿子,并消去贡献。
  • 递归处理重儿子,并保留贡献。
  • 将轻儿子的信息合并到重儿子保留的贡献中。
  • 若当前节点不是父节点的重儿子,消去贡献。

复杂度 $O(n\log n)$,但是我不会证。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,c[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int hson[N],sz[N];
inline void dfs(int u,int fa) {
    sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}

int vis[N]; ll ans[N];
int cnt[N],num[N],mx=0; ll sum[N];
inline void update(int u,int fa,int w) {
    --num[cnt[c[u]]],sum[cnt[c[u]]]-=c[u];
    cnt[c[u]]+=w;
    ++num[cnt[c[u]]],sum[cnt[c[u]]]+=c[u];
    if (w>0) mx=max(mx,cnt[c[u]]);
    else if (!num[mx]) --mx;
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa&&!vis[e[i].v]) update(e[i].v,u,w);
}
inline void solve(int u,int fa,int flag) {
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa&&e[i].v!=hson[u]) solve(e[i].v,u,0);
    if (hson[u]) solve(hson[u],u,1),vis[hson[u]]=1;
    update(u,fa,1); ans[u]=sum[mx]; vis[hson[u]]=0;
    if (!flag) update(u,fa,-1);
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) c[i]=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,0); solve(1,0,1);
    for (re int i=1;i<=n;++i) printf("%I64d ",ans[i]); puts("");
    return 0;
}
最后修改:2019 年 10 月 20 日 08 : 55 AM