codeforces600E. Lomsat gelral(dsu on tree) 我们就需要学习一种新的数据结构：dsu on tree

codeforces600E. Lomsat gelral(dsu on tree)
我们就需要学习一种新的数据结构：dsu on tree

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
4
1 2 3 4
1 2
2 3
2 4

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

分析：
我这个zz不看题
被yveh学长嘲讽。。。
首先读懂题目，
我们需要统计的是以i为根节点的子树中
数目最多的颜色的权值和是多少
（就是按出现频率排序，排第一的一种或几种颜色分别是什么，把颜色编号加起来输出）

显然这样一遍dfs是不可能的了
n^2暴力太不优美

主体思路也是轻重链剖分
但是没有那么繁琐了，不用维护太多东西
首先找到每个节点的重儿子
之后再进行一遍dfs

dfs流程：
1.dfs轻儿子
2.dfs重儿子
3.把儿子的信息记录到父亲
4.Son=0
5.记录答案
6.一键消除轻儿子影响

这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long

using namespace std;

const int N=100010;
struct node{
    int x,y,nxt;
};
node way[N<<1];
int st[N],n,tot=0,son[N],size[N],Son,mxx,cnt[N],c[N];
ll sum,ans[N];

void add(int u,int w)
{
    tot++;
    way[tot].x=u;way[tot].y=w;way[tot].nxt=st[u];st[u]=tot;
    tot++;
    way[tot].x=w;way[tot].y=u;way[tot].nxt=st[w];st[w]=tot;
}

void js(int now,int fa,int v)
{
    cnt[c[now]]+=v;  //now在子树中出现了几次 
    if (cnt[c[now]]>mxx) sum=(ll)c[now],mxx=cnt[c[now]];
    else if (cnt[c[now]]==mxx) sum+=(ll)c[now];
    for (int i=st[now];i;i=way[i].nxt)
        if (way[i].y!=fa&&way[i].y!=Son) js(way[i].y,now,v);  //way[i].y!=Son 
}

void getson(int now,int fa)
{
    int i,mx=0;
    size[now]=1;
    for (i=st[now];i;i=way[i].nxt)
        if (way[i].y!=fa)
        {
            getson(way[i].y,now);
            size[now]+=size[way[i].y];
            if (size[way[i].y]>mx)
            {
                mx=size[way[i].y];
                son[now]=way[i].y;
            }
        }
}

void dfs(int now,int fa,int keep)  //keep用来标记是否要清除影响 
{
    int i;
    for (i=st[now];i;i=way[i].nxt)
        if (way[i].y!=fa&&way[i].y!=son[now])
            dfs(way[i].y,now,0);   //轻儿子
    if (son[now]) dfs(son[now],now,1),Son=son[now];   //不清除影响
    js(now,fa,1);  //加入影响
    Son=0;   //进行到这一步，重儿子的信息一定已经计入了，这就说明整个子树都进行了统计 
    ans[now]=sum;   //记录答案
    if (!keep) js(now,fa,-1),mxx=sum=0;  //
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&c[i]);
    for (int i=1;i<n;i++)
    {
        int u,w;
        scanf("%d%d",&u,&w);
        add(u,w); 
    }
    getson(1,0); 
    dfs(1,1,0);
    for (int i=1;i<=n;i++) printf("%I64d ",ans[i]);
    return 0;
}

codeforces600E. Lomsat gelral(dsu on tree) 我们就需要学习一种新的数据结构：dsu on tree

相关推荐