启发式合并 CodeForces - 600E

启发式合并最重要的思想就是指的是每次将小集合拷贝合并至大集合。
考虑每个元素的合并开销。对于合并次数最多的那个元素来说，它每合并一次，所在集合的规模扩大两倍，最多只会合并 logN 次，因而对于所有元素,至多插入set中NlogN次，时间复杂度就有上限 O(N∗logN∗logN)

现在主要是dsu on tree,它用来解决这样一类问题：统计树上一个节点的子树中具有某种特征的节点数。 基本上就是树上子树的统计问题。

但是dsu on tree也有一定的局限性：1.只能支持子树查询；2.不支持修改修改。

看例题来说：

D - Lomsat gelralCodeForces - 600E

You are given a rooted tree with root in vertex 1. Each vertex is coloured in some colour.

Let's call colour c dominating in the subtree of vertex v if there are no other colours that appear in the subtree of vertex v more times than colour c . So it's possible that two or more colours will be dominating in the subtree of some vertex.

The subtree of vertex v is the vertex v and all other vertices that contains vertex v in each path to the root.

For each vertex v find the sum of all dominating colours in the subtree of vertex v .

Input

The first line contains integer n (1 ≤ n ≤ 10 ⁵ ) — the number of vertices in the tree.

The second line contains n integers c _i (1 ≤ c _i ≤ n ), c _i — the colour of the i -th vertex.

Each of the next n - 1 lines contains two integers x _j , y _j (1 ≤ x _j , y _j ≤ n ) — the edge of the tree. The first vertex is the root of the tree.

Output

Print n integers — the sums of dominating colours for each vertex.

Examples

4
1 2 3 4
1 2
2 3
2 4

10 9 3 4

15
1 2 3 1 2 3 3 1 1 3 2 2 1 2 3
1 2
1 3
1 4
1 14
1 15
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13

6 5 4 3 2 3 3 1 1 3 2 2 1 2 3

题意：给定一个 n 个节点的树，对于每个子树，输出子树中出现次数最多的节点编号之和。（次数最多的编号有多个节点都要统计进去）。 
想法：最初的想法是对于每个点都跑一遍，暴力跑每个点的子树，然后记录下来答案，然后清空数组跑下一次，但是这样的话就时间复杂度就非常的高。
所以要优化一下，我们都知道每个点有子树的话，会有一个重子树（就是点相对最多的那颗子树）。所以我们先预处理一下找到所有节点重子树。
然后对于每科子树，我们先跑每颗子树的轻子树，跑完之后再跑重子树。在计算结果的时候，假设某一个点的儿子都已经被dfs过，统计这个点的答案。统计答案的过程中要calc当前这个点的子树，但是只calc它的轻链，重链不做。 
这样的话，就需要在dfs的过程中，如果当前点是它父亲的轻儿子，做完这个点之后就将影响消除；而如果这个点是它父亲的重儿子，则将这个点的影响保留。 
我们看下代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

using namespace std;

typedef long long LL;

const int maxn=1e5+;

int n,m;

int mx,big;

LL sum=;

LL ans[maxn];

int col[maxn],si[maxn],hson[maxn],cnt[maxn];

vector<int>G[maxn];

void findhson(int x,int fa)//找到所有的重儿子

{

    si[x]=;

    int len=G[x].size();

    for(int i=;i<len;i++)

    {

        int t=G[x][i];

        if(t!=fa)

        {

            findhson(t,x);

            si[x]+=si[t];

            if(si[t]>si[hson[x]])

                hson[x]=t;

        }

    }

}

void cal(int x,int fa,int val)//计算的过程，就是不断递归求颜色的数量

{

    cnt[col[x]]+=val;

    if(cnt[col[x]]>mx)

    {

        sum=col[x];

        mx=cnt[col[x]];

    }

    else if(cnt[col[x]]==mx)

        sum+=col[x];

    int len=G[x].size();

    for(int i=;i<len;i++)

    {

        int t=G[x][i];

        if(t!=fa && t!=big)

            cal(t,x,val);

    }

}

void dfs(int x,int fa,int flag)//flag作为标记，看是轻子树还是重子树

{

    int len=G[x].size();

    for(int i=;i<len;i++)//先跑轻子树

    {

        int t=G[x][i];

        if(t!=fa && t!=hson[x])

            dfs(t,x,);

    }

    if(hson[x])//再跑重子树

    {

        dfs(hson[x],x,);

        big=hson[x];

    }

    cal(x,fa,);

    big=;

    ans[x]=sum;

    if(!flag)//如果是轻子树的话，消除影响

    {

        cal(x,fa,-);

        mx=;sum=;

    }

}

int main()

{

    sum=;big=;mx=;

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        scanf("%d",&col[i]);

    int x,y;

    for(int i=;i<n;i++)//双向边

    {

        scanf("%d %d",&x,&y);

        G[x].push_back(y);

        G[y].push_back(x);

    }

    findhson(,);

    dfs(,,);

    for(int i=;i<=n;i++)

    {

        if(i==)

            printf("%lld",ans[i]);

        else

            printf(" %lld",ans[i]);

    }

    printf("\n");

    return ;

}