[题目链接] 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;
}