# CF600E Lomsat gelral

### 题目描述

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$ .

### 输入格式

p>The first line contains integer $n$ ( $1\le n\le10^{5}$ ) — the number of vertices in the tree. The second line contains $n$ integers $c_{i}$ ( $1\le c_{i}\le 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\le x_{j},y_{j}\le n$ ) — the edge of the tree. The first vertex is the root of the tree.

### 输出格式

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

### 样例输入

4
1 2 3 4
1 2
2 3
2 4


### 样例输出

10 9 3 4


### 代码

#include <bits/stdc++.h>
typedef long long ll;

const int N = 1e5+50;

int n, a[N];

struct Graph {
struct Edge {
int to, nxt;
} e[N<<1];

Graph(): top(0) {
}

void add(int u, int v) {
}

void add2(int u, int v) {
}
} G;

int siz[N], son[N];
ll sum[N];
int cnt[N], maxCnt;
ll ans[N];

void dfs1(int u, int fa) {
siz[u] = 1;
for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
int v = G.e[i].to;
if (v == fa) continue;
dfs1(v, u);
siz[u] += siz[v];
if (!son[u] || siz[v] > siz[son[u]])
son[u] = v;
}
}

void change(int u, int val) {
int c = a[u];
sum[cnt[c]] -= c;
cnt[c] += val;
sum[cnt[c]] += c;
if (sum[maxCnt+1]) maxCnt++;
if (!sum[maxCnt]) maxCnt--;
}

void update(int u, int fa, int val) {
change(u, val);
for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
int v = G.e[i].to;
if (v == fa) continue;
update(v, u, val);
}
}

void dfs2(int u, int fa, bool keep) {
for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
int v = G.e[i].to;
if (v == fa || v == son[u]) continue;
dfs2(v, u, false);
}

if (son[u]) dfs2(son[u], u, true);

change(u, 1);
for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
int v = G.e[i].to;
if (v == fa || v == son[u]) continue;
update(v, u, 1);
}

ans[u] = sum[maxCnt];

if (!keep) update(u, fa, -1);
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1, u, v; i < n; i++) {
scanf("%d%d", &u, &v);
}
dfs1(1, 0);
dfs2(1, 0, false);
for (int i = 1; i <= n; i++)
printf("%I64d ", ans[i]);
puts("");
return 0;
}


暂无评论