DSU On Tree——Codeforces 600E(E. Lomsat gelral)

有这么一类问题，要求统计一棵树上与子树相关的某些信息，比如：在一棵所有节点被染色的树上，统计每棵子树上出现次数最多的颜色编号之和。

很自然的可以想到用DFS序+主席树去求解，但是编码复杂度很高；

然后我们可以想到DFS序+莫队解决，然而$O(n\sqrt{n})$的时间复杂度在数据较大的时候容易TLE；

有没有更优美一点的解法呢？DSU On Tree（据说叫树上启发式合并）可以以较小的编码复杂度在$O(n\log n)$的时间复杂度完成对于所有子树信息的统计。

先上模板

1 void dsu(LL k,LL f,LL x){
2     fore(i,k,v)
3         if(v!=f&&v!=son[k])dsu(v,k,0);//统计轻儿子所在的子树，不保留信息 
4     if(son[k])
5         dsu(son[k],k,1),hs=son[k];//统计重儿子所在子树，保留信息 
6     calc(k,f,1);//统计所需信息 
7     hs=0;ans[k]=sum;
8     if(!x)calc(k,f,-1),mx=sum=0;//如果是轻儿子，则清除信息 
9 }

看上去除了每次保留了重儿子的信息和暴力也没啥区别。。。

但是实际上，只有dfs到轻边时，才会将轻边的子树中合并到上一级的重链，树剖后的每条链上至多有$log n$条轻边，所以每一个节点最多向上合并$log n$次，每次统计的复杂度是$O(n)$，整体复杂度为$O(nlog n)$

在竞赛中，DSU On Tree 是一个不错的trick，可以有效减少代码复杂度。然而其缺陷也是明显的，这种算法的适用范围非常狭窄，仅适用于对于子树信息的统计，并且不滋磁修改操作。

来看一道模板题：传送门

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 ≤ 105) — the number of vertices in the tree.

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

Each of the next n - 1 lines contains two integers xj, yj (1 ≤ xj, yj ≤ 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

input

output

10 9 3 4

input

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

output

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

题目大意：给出一棵树，每一个节点有一个颜色，统计以每一个节点为根的子树中出现次数最多的颜色(可能不止一种)的编号和。

套上面的模板就好啦。

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define foru(i,x,y) for(LL i=x;i<=y;i++)
#define fore(i,x,v) for(LL i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
using namespace std;
typedef long long LL;
const LL N=2e5+10;
struct edge{LL to,nxt;}e[N*2];
LL head[N],siz[N],son[N],ans[N],cnt[N],c[N],n,sum,hs,mx,ne;
void add(LL a,LL b){e[++ne]=(edge){b,head[a]};head[a]=ne;}

void dfs(LL k,LL f){
    siz[k]=1;son[k]=0;
    fore(i,k,v){
        if(v==f)continue;
        dfs(v,k);
        siz[k]+=siz[v];
        if(siz[v]>siz[son[k]])son[k]=v;
    }//剖分轻重儿子 
}

void calc(LL k,LL f,LL x){
    cnt[c[k]]+=x;
    if(cnt[c[k]]>mx)sum=c[k],mx=cnt[c[k]];
    else if(cnt[c[k]]==mx)sum+=c[k];
    fore(i,k,v)    
        if(v!=f&&v!=hs)calc(v,k,x);
}

void dsu(LL k,LL f,LL x){
    fore(i,k,v)
        if(v!=f&&v!=son[k])dsu(v,k,0);//统计轻儿子所在的子树，不保留信息 
    if(son[k])
        dsu(son[k],k,1),hs=son[k];//统计重儿子所在子树，保留信息 
    calc(k,f,1);//统计所需信息 
    hs=0;ans[k]=sum;
    if(!x)calc(k,f,-1),mx=sum=0;//如果是轻儿子，则清除信息 
}

int main(){
    LL u,v;
    scanf("%I64d",&n);
    foru(i,1,n)scanf("%I64d",&c[i]);
    foru(i,1,n-1){
        scanf("%I64d%I64d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs(1,0);
    dsu(1,0,0);
    foru(i,1,n)printf("%I64d ",ans[i]);printf("\n");
}

秒客网

DSU On Tree——Codeforces 600E(E. Lomsat gelral)

相关文章