[题目链接] Lomsat gelral
[原题链接] E. Lomsat gelral
Lomsat gelral
题面翻译
有一棵 n 个结点的以 1 号结点为根的有根树。
每个结点都有一个颜色，颜色是以编号表示的， i 号结点的颜色编号为 c_i。
如果一种颜色在以 x 为根的子树内出现次数最多，称其在以 x 为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。
你的任务是对于每一个 i\in[1,n]，求出以 i 为根的子树中，占主导地位的颜色的编号和。
n\le 10^5,c_i\le n
输入格式
The first line contains integer n ( 1<=n<=10^{5} ) — 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.
输出格式
Print n integers — the sums of dominating colours for each vertex.
样例 #1
样例输入 #1
4
1 2 3 4
1 2
2 3
2 4
样例输出 #1
10 9 3 4
样例 #2
样例输入 #2
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
样例输出 #2
6 5 4 3 2 3 3 1 1 3 2 2 1 2 3
题解
不删除这个输入输出格式是有原因的
解法不少，看到过线段树合并、莫队的算法，不过最近在学 dsu，那我就写 dsu。
DSU ON TREE
中文名树上启发式合并，在笔记中有提到。
思想就是：dfs的时候先去解决那些比较小的儿子，先加上再退回，最后处理最大的儿子时就不用再退回，从而节省时间复杂度。
时间复杂度证明：
我们称当前节点最大的儿子称为重儿子，其他儿子称为轻儿子。
每个节点走到根节点经过的轻边的数量就是这个节点被统计的数量。如果该边为轻边，那一定有一个重边，且重儿子的数量大于等于当前轻儿子的重量，也就是说，每往上经过一条轻边，节点数量必然翻倍，也就是说每个节点最多会被统计 log_n 遍，总复杂度就为 \mathcal{O}(nlogn)。
这道题的做法：
维护一个颜色数组 col ，统计当前情况各种颜色的数量，每遍历完一个轻节点，就清零。最后遍历重节点，遍历完把轻节点加上，统计答案。重节点自始至终不清零！
:exclamation:注意：题目给出的是边而不是父子关系，所以建双向边！
AC Code
#include<bits/stdc++.h>
//几乎就是模板题了
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n;
int c[N];
ll ans[N];
int maxs[N];
int cnt[N];
vector<int> son[N];
ll col[N], mx, sum;
//如何传递mx
void Dfs(int pos, int fa, int p) {//统计答案
col[c[pos]]++;
if(col[c[pos]] > mx) mx = col[c[pos]], sum = c[pos];
else if(col[c[pos]] == mx) sum += c[pos];
for(auto i : son[pos]) {
if(i == fa) continue;
if(i != p) Dfs(i, pos, p);
}
}
void init(int pos, int fa) {//参考题解写的递归清空，将某颗子树的col全部清空
col[c[pos]]--;
for(auto i : son[pos]) {
if(i == fa) continue;
init(i, pos);
}
}
void dfs(int pos, int fa) {
int p = 0;
for(auto i : son[pos]) {
if(i == fa) continue;
if(i != maxs[pos]) {
//如果不是大儿子,从小儿子开始搜
dfs(i, pos);
init(i, pos);
sum = 0, mx = 0;
//最后计算自己的时候，要再dfs一遍是吧
} else p = i;
}
if(p) dfs(p, pos);
Dfs(pos, fa, p);//统计答案，并加上所有儿子
//最后的状态是要全部加上的，以便回溯，如果这个子树不被需要，会清空
ans[pos] = sum;
}
void get_v(int pos, int fa) {
for(auto i : son[pos]) {
if(i == fa) continue;
get_v(i, pos);
cnt[pos] += cnt[i];
if(cnt[i] > cnt[maxs[pos]]) maxs[pos] = i;
}
}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &c[i]);
cnt[i] = 1;
}
int u, v;
for(int i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
son[u].emplace_back(v);
son[v].emplace_back(u);
}
get_v(1, 0);
dfs(1, 0);
for(int i = 1; i <= n; i++) {
printf("%lld ", ans[i]);
}
return 0;
}
