题面

题解

看到网上写了很多DSU和线段树合并的题解，笔者第一次做也是用的线段树合并，但在原题赛的时候却怕线段树合并调不出来，于是就用了更好想更好调的莫队。

这里笔者就说说莫队怎么做吧。

我们可以通过 dfs 序把点都拍到序列上，然后每个点的主导编号和就相当于询问一段区间的主导编号和，并且这样的询问刚好 n 个。

那么维护两个数组和一个变量

• C

  [

  i

  ]

  C[i]

  C[i]：第

  i

  i

  i 种颜色的出现次数

• S

  m

  [

  i

  ]

  Sm[i]

  Sm[i]：出现

  i

  i

  i 次的颜色编号和

• a

  n

  s

  ans

  ans：出现的最多次数是几次（即实际的答案是

  S

  m

  [

  a

  n

  s

  ]

  Sm[ans]

  Sm[ans]，这样方便维护些）

当我们的序列中新加入一个点时（我们已经开始跑莫队了），设这个点的颜色为

c

o

l

col

col ,那么

C

[

c

o

l

]

C[col]

C[col] 很好维护吧，

S

m

[

.

.

.

]

Sm[…]

Sm[…] 也很好维护吧，那么我们需要证明一个结论：

a

n

s

ans

ans 每次变动的幅度最多为 1。

其实很好证，由于每次

C

[

c

o

l

]

C[col]

C[col] 最多改 1，因此

S

m

[

.

.

.

]

Sm[…]

Sm[…] 只在长度为 2 的范围内有变动，其中一个清零的话，另一个肯定会有值，而

a

n

s

ans

ans 的值只取决于最大的有值的

S

m

[

.

.

.

]

Sm[…]

Sm[…] ，因此由于最大的

S

m

Sm

Sm 最多变动 1，所以

a

n

s

ans

ans 也最多变动 1。在脑袋里模拟一下也会理解的。

具体怎么操作可以看代码的

i

n

s

(

)

ins()

ins() 和

d

e

l

(

)

del()

del() 函数。

CODE

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100005
#define LL long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) : (x))
LL read() {
    LL f = 1,x = 0;char s = getchar();
    while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
    while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
    return x * f;
}
const int MOD = 1000000007;
int n,m,i,j,s,o,k,sq;
vector<int> g[MAXN];
int dfn[MAXN],rr[MAXN],cnt,id[MAXN];
int cl[MAXN];
void dfs(int x,int fa) {
    dfn[x] = ++ cnt; id[cnt] = x;
    for(int i = 0;i < (int)g[x].size();i ++) {
        if(g[x][i] != fa) {
            dfs(g[x][i],x);
        }
    }
    rr[x] = cnt;
    return ;
}
struct it{
    int l,r,id;
}q[MAXN];
bool cmp(it a,it b) {
    if(a.l/sq != b.l/sq) return a.l < b.l;
    return a.r < b.r;
}
int L,R,c[MAXN],ans;
LL sm[MAXN],as[MAXN];
void ins(int x) { // x 是点编号
    int col = cl[x];
    sm[c[col]] -= col;
    c[col] ++;
    sm[c[col]] += col;
    if(sm[ans+1] > 0) ans ++;
    else if(!sm[ans]) ans --;
    return ;
}
void del(int x) {
    int col = cl[x];
    sm[c[col]] -= col;
    c[col] --;
    sm[c[col]] += col;
    if(sm[ans+1] > 0) ans ++;
    else if(!sm[ans]) ans --;
    return ;
}
int main() {
    n = read();
    sq = (int)sqrt((DB)n);
    for(int i = 1;i <= n;i ++) cl[i] = read();
    for(int i = 1;i < n;i ++) {
        s = read();o = read();
        g[s].push_back(o);
        g[o].push_back(s);
    }
    dfs(1,0);
    for(int i = 1;i <= n;i ++) {
        q[i].id = i;
        q[i].l = dfn[i];q[i].r = rr[i];
    }
    sort(q + 1,q + 1 + n,cmp);
    L = 1,R = 0;
    for(int i = 1;i <= n;i ++) {
        int l = q[i].l,r = q[i].r;
        while(L > l) ins(id[-- L]);
        while(R < r) ins(id[++ R]);
        while(L < l) del(id[L ++]);
        while(R > r) del(id[R --]);
        as[q[i].id] = sm[ans];
    }
    for(int i = 1;i <= n;i ++) {
        printf("%lld ",as[i]);
    }ENDL;
    return 0;
}