Dsu On Tree

首先丢一下原文链接，写的很好：这里

是一种奇怪的科技。。在 cf 学了一下感觉看不出和 dsu 有多大的关系，貌似只是按秩合并的复杂度有点关。不过还是很妙的啦。。

我们考虑要做这样一件事：维护一个子树内的某种信息。比如我们要问某个点子树内的某种颜色的数量。我们显然可以拖到 dfs 序上跑主席树 于是本文终结，但是这里介绍另一种做法。。

我们考虑，一个最朴素的暴力到大一个点，清空 cnt 数组并且便历这个子树，到一个点就给这个点的颜色 + 1。这样做是稳定 $O(n^2)$ 的，我们考虑怎么优化这个过程。

不难发现我们只需要在每个点得到这个点的 cnt 数组就好了。dsu on tree 的思路就是：继承重儿子的 cnt 数组，然后分别把其他轻儿子的树跑完。这样做的复杂度就优化到了 $O(n\log n)$。因为考虑这个过程，其实基本上就是 dsu 按秩合并的过程（每次把小的丢到大的下面）。。

关于实现，首先显然可以直接 直接 dfs 所有轻儿子一遍让它们的颜色 + 1，但是我们可以放到 dfs 序列上。。这样既好写常数也比较小。

一个模版题： CF600E

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "bitset"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define P 998244353
typedef long long ll;
int n , m , z , q , blo;
int A[MAXN];
vector<int> G[MAXN];
//char ch[MAXN];

int L[MAXN] , R[MAXN] , bac[MAXN] , siz[MAXN] , clo;
void dfs1( int u , int fa ) {
    siz[u] = 1; L[u] = ++ clo; bac[clo] = u;
    for( int v : G[u] ) if( v != fa ) dfs1( v , u ) , siz[u] += siz[v];
    R[u] = clo;
}
long long res[MAXN] , ans;
int cnt[MAXN] , mxc;
void dfs( int u , int fa , int ke ) {
    int mx = 0;
    for( int v : G[u] ) if( v != fa && ( !mx || siz[v] > siz[mx] ) ) mx = v;
    for( int v : G[u] ) if( v != fa && v != mx ) dfs( v , u , 0 );
    if( mx ) dfs( mx , u , 1 );
    ++ cnt[A[u]];
    if( cnt[A[u]] > mxc ) mxc = cnt[A[u]] , ans = A[u];
    else if( cnt[A[u]] == mxc ) ans += A[u];
    for( int v : G[u] ) if( v != fa && v != mx )
        for( int i = L[v] ; i <= R[v] ; ++ i ) {
            int c = A[bac[i]];
            ++ cnt[c];
            if( cnt[c] > mxc ) mxc = cnt[c] , ans = c;
            else if( cnt[c] == mxc ) ans += c;
        }
    res[u] = ans;
    if( !ke ) {
        for( int i = L[u] ; i <= R[u] ; ++ i )
            -- cnt[A[bac[i]]];
        ans = mxc = 0;
    }
}

void solve() {
//    freopen("input","r",stdin);
//    freopen("ot","w",stdout);
    cin >> n;
    rep( i , 1 , n ) scanf("%d",&A[i]);
    int u , v;
    rep( i , 2 , n )
        scanf("%d%d",&u,&v) , G[u].pb( v ) , G[v].pb( u );
    dfs1( 1 , 1 ) , dfs( 1 , 1 , 1 );
    rep( i , 1 , n ) printf("%lld%c",res[i]," \n"[i==n]);
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}