题解 - CF600E Lomsat gelral

[题目链接] 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$ ，统计当前情况各种颜色的数量，每遍历完一个轻节点，就清零。最后遍历重节点，遍历完把轻节点加上，统计答案。重节点自始至终不清零！

注意：题目给出的是边而不是父子关系，所以建双向边！

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;
}