正文
codeforces 600E . 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 .
Input
The first line contains integer n (1 ≤ n ≤ 105) — 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
input
Copy
4
1 2 3 4
1 2
2 3
2 4
output
Copy
10 9 3 4
input
Copy
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
Copy
6 5 4 3 2 3 3 1 1 3 2 2 1 2 3 思路：
对每个点建线段树在线段树上当前点的权值下标+1，每个点与父节点进行线段树合并，这样对树dfs一遍就可以求出所有的值了。
实现代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mid ll m = (l + r) >> 1
const ll M = 1e5 + ; struct node{
ll ans,sum;
}tr[M*]; struct node1{
ll to,next;
}e[M<<];
ll cnt,head[M],idx,ls[M*],rs[M*],root[M],a[M],ans[M]; void add(ll u,ll v){
e[++cnt].to = v;e[cnt].next = head[u];head[u] = cnt;
} void pushup(ll rt){
if(tr[ls[rt]].sum > tr[rs[rt]].sum){
tr[rt].sum = tr[ls[rt]].sum;
tr[rt].ans = tr[ls[rt]].ans;
}
else if(tr[ls[rt]].sum == tr[rs[rt]].sum){
tr[rt].sum = tr[ls[rt]].sum;
tr[rt].ans = tr[rs[rt]].ans + tr[ls[rt]].ans;
}
else{
tr[rt].sum = tr[rs[rt]].sum;
tr[rt].ans = tr[rs[rt]].ans;
}
} void update(ll p,ll c,ll l,ll r,ll &rt){
if(!rt) rt = ++idx;
if(l == r){
tr[rt].sum += c;
tr[rt].ans = l;
return ;
}
mid;
if(p <= m) update(p,c,l,m,ls[rt]);
else update(p,c,m+,r,rs[rt]);
pushup(rt);
} ll Merge(ll x,ll y,ll l,ll r){
if(!x) return y;
if(!y) return x;
if(l == r){
tr[x].sum += tr[y].sum;
tr[x].ans = l;
return x;
}
mid;
ls[x] = Merge(ls[x],ls[y],l,m);
rs[x] = Merge(rs[x],rs[y],m+,r);
pushup(x);
return x;
} void dfs(ll u,ll fa){
for(ll i = head[u];i;i=e[i].next){
ll v = e[i].to;
if(v == fa) continue;
dfs(v,u);
Merge(root[u],root[v],,M);
}
update(a[u],,,M,root[u]);
ans[u] = tr[root[u]].ans;
} int main()
{
ll n,u,v;
scanf("%lld",&n);
for(ll i = ;i <= n;i ++){
scanf("%lld",&a[i]);
root[i] = i;
idx++;
}
for(ll i = ;i < n;i ++){
scanf("%lld%lld",&u,&v);
add(u,v); add(v,u);
}
dfs(,);
for(ll i = ;i <= n;i ++){
printf("%lld ",ans[i]);
}
return ; }
