第一次AC这道题，是三年前的一个下午，也许晚上也说不定。当时使用的\(DSU\) \(on\) \(tree\)算法，如今已经淡忘，再学习新的算法过程中，却与旧物重逢。生活中充满不可知会的相遇，即使重逢时多是物是人非。我又想起十六岁时在上海那个船上的夜晚，两岸的霓虹在无边黑暗中照亮了她的脸庞，绿衣在少年的眼瞳里凝滞了时间，那真是个美丽的夜晚，即使看不见星月。前天她给我说说点了个赞，我都高兴了好久，真是卑微呵。那么人世中所有明知卑微却不求告解的人，就是可悲吗？大抵是有更深沉的缘由的，比如最初的悸动从不属于初恋的对象，而是属于动情者的青葱。诗人和舔狗多少是有些区别的，虽然不多，而对于沿叶节点向根的路途，上面的答案会有下面的影响，所以至下而上一路合并即可。合并的过程中，若是同时抵达叶节点，两颗原本子树代表的颜色应该别无二致。树是权值的，一种颜色对应一个节点，所以\(dfs\)过程中针对颜色单点对应节点修改。至于关键的\(push\) \(up\)，多者则独上，相同则齐加，生活亦然。
# include "bits/stdc++.h"
using namespace std;
constexpr int N = 1e5 + 3;
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<int> col(n + 1);
for(int i = 1; i <= n; ++i) cin >> col[i];
vector G(n + 1, vector<int>());
for(int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
struct node {
int l, r, tot;
long long sum;
};
# define ls t[rt].l
# define rs t[rt].r
# define lson t[rt].l, l, mid
# define rson t[rt].r, mid + 1, r
vector<node> t(N * 50);
auto push_up = [&](int rt) -> void {
if(t[ls].tot == t[rs].tot) {
t[rt].tot = t[ls].tot;
t[rt].sum = t[ls].sum + t[rs].sum;
}
else if(t[ls].tot > t[rs].tot) {
t[rt].tot = t[ls].tot;
t[rt].sum = t[ls].sum;
}
else {
t[rt].tot = t[rs].tot;
t[rt].sum = t[rs].sum;
}
};
vector<int> rt(n + 1, 0);
int tree_index = n; // 1~n node has their names
auto update = [&](auto update, int &rt, int l, int r, int x) -> void {
if(!rt) rt = ++tree_index;
if(l == r) {
++t[rt].tot;
t[rt].sum = l;
return;
}
int mid = l + r >> 1;
if(x <= mid)
update(update, lson, x);
else
update(update, rson, x);
push_up(rt);
};
auto merge = [&](auto merge, int x, int y, int l, int r) -> int {
if(!x || !y) return x | y;
if(l == r) {
t[x].tot += t[y].tot;
t[x].sum = l;
return x;
}
int mid = l + r >> 1;
t[x].l = merge(merge, t[x].l, t[y].l, l, mid);
t[x].r = merge(merge, t[x].r, t[y].r, mid + 1, r);
push_up(x);
return x;
};
vector<long long> ans(n + 1);
auto dfs = [&](auto dfs, int u, int father) -> void {
for(auto v : G[u]) {
if(v == father) continue;
dfs(dfs, v, u);
merge(merge, u, v, 1, n);
}
update(update, u, 1, n, col[u]);
ans[u] = t[u].sum;
};
dfs(dfs, 1, 0);
for(int i = 1; i <= n; ++i) cout << ans[i] << " ";
return 0;
}