CF lomsat gelral (heuristic merge)

Logue link ：Lomsat gelral - Luogu

The question ：

• There is a tree  nn  The number of nodes is  1  Node number is the root of Rooting tree .
• Each node has a color , Colors are represented by numbers , i  The color number of node No. is  c[i]​.
• If a color is in  x  The subtree with root appears the most times , Call it in  x  In a subtree with roots Dominance . obviously , Multiple colors may dominate in the same subtree .
• Your task is for every  i∈[1,n], Find out to  i  In the subtree of the root , The number and number of the dominant colors .

We need to use Heuristic merging , My understanding of heuristic merging is as follows ：

This problem requires “ Information of all subtrees ”. We have a tree dp My thoughts know , The information of the subtree of a node is the subtree information of all its sons + Own information . But here we have a problem , Just can not O(1) Combine information , Suppose every two pieces of information are merged O(n) Of , It has m A son , Then it is necessary to complete the information consolidation of this node O(nm) 了 , That's not going to work .

Then let's consider this ： Let the node inherit the subtree information of one of its sons , Then violence statistics other information （ Including their own information and the subtree information of other sons ）, Find this faster . So which son do we choose to inherit ？ Heavy son , Because the statistics of heavy son violence are the slowest . Therefore, heuristic merging requires light chain dissection .

So this is the way to think about it , The general steps of heuristic merging are as follows ：

1. Run dfs1 To record the subtree size , Height , Heavy son and other information .

2. Run again dfs2 Calculate the answer , For each node , Inherit the information of his son , Then violence statistics other information .

code：

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define int long long
const int N = 1e5+5;
int n, a[N], sz[N], son[N];
int cnt[N], ans[N], Mx, Son, Ans;
vector<int> g[N];

void dfs1(int u,int fa){
    sz[u] = 1;
    for(int v:g[u]){
        if(v==fa) continue;
        dfs1(v,u);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v; // Heavy chain subdivision , Record heavy son 
    }
}
void add(int u,int fa,int val){
    cnt[a[u]] += val; // Count current contributions 
    if(cnt[a[u]] > Mx) Mx=cnt[a[u]], Ans=a[u];
    else if(cnt[a[u]]==Mx) Ans+=a[u];
    for(int v:g[u]){
        if(v==fa || v==Son) continue;
        add(v,u,val);
    }
}
void dfs2(int u,int fa,int op){ //op=0 It means you don't need to keep information ,op=1 I want to keep it 
    for(int v:g[u]){
        if(v==fa) continue;
        if(v!=son[u]) dfs2(v,u,0); // First, violence statistics light son's information , Then throw away the information 
    }
    if(son[u]) dfs2(son[u],u,1), Son=son[u]; // Then violence statistics heavy son's information , Keep information . And record the current heavy son , For the back add

    add(u,fa,1); // After inheriting the information of the second son , The rest of the violence statistics 
    Son = 0; // Reset the current heavy son 
    ans[u] = Ans; // Record the current answer 
    if(!op) add(u,fa,-1), Ans=0, Mx=0; // Delete information 
}
inline void solve(){
    cin>>n; FOR(i,1,n) cin>>a[i];
    FOR(i,1,n-1){
        int x,y; cin>>x>>y;
        g[x].push_back(y); g[y].push_back(x);
    }
    dfs1(1,0); dfs2(1,0,0);
    FOR(i,1,n) cout<<ans[i]<<' ';
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T=1; while(T--) solve();
}