[Codeforces]600E. Lomsat gelral

題目連結：http://codeforces.com/problemset/problem/600/E

題目為為子樹的眾數問題。
不難發現樹壓扁可以轉成序列區間眾數，因此再用莫隊去做。

#include <bits/stdc++.h> 
#define PB push_back
#define F first
#define S second
#define lld long long
#define N 100005
#define debug cout << "a" <<endl;
using namespace std;
typedef pair<int,int> Pair;
struct Query{
    int l,r,lid,id;
    bool operator < (const Query &x)const{
        return lid == x.lid ? r < x.r : lid < x.lid;
    }
}q[N];
int n;
int color[N];
vector<int> v[N],g;
int in[N],out[N],sz[N],mx,t;
lld h[N],ans[N],sum;
void DFS(int now,int fa){
    in[now] = t++;
    g.PB(color[now]);
    for(int i : v[now]){
        if(i != fa)DFS(i,now);  
    }
    out[now] = t-1;
}
void add(int x){
    ++sz[x];
    h[sz[x]] += x;
    mx = max(mx,sz[x]);
}
void sub(int x){
    h[sz[x]] -= x;
    sz[x]--;
    if(!h[mx])mx--;
}
void MO(){
    int L = 0,R = 0;
    add(g[L]);
    for(int i = 1; i <= n ; i++){
        while(R < q[i].r)add(g[++R]);
        while(L > q[i].l)add(g[--L]);
        while(R > q[i].r)sub(g[R--]);
        while(L < q[i].l)sub(g[L++]);
        ans[q[i].id] = h[mx];
    }
    for(int i = 1; i <= n ; i++)cout << ans[i] << " \n"[i == n];
}
int main(){
    cin >> n;
    for(int i = 1; i <= n ; i++)cin >> color[i];
    for(int i = 1; i < n ; i++){
        int a,b;cin >> a >> b;
        v[a].PB(b);v[b].PB(a);
    }
    DFS(1,0);
    int s = sqrt(n)+1;
    for(int i = 1; i <= n ; i++){
        q[i].l = in[i];
        q[i].r = out[i];
        q[i].lid = q[i].l/s;
        q[i].id = i;
    }sort(q+1,q+n+1);
    MO();
    return 0;
}