给出一个序列，序列每个不同的数字代表不同的颜色
    现在有两种操作：
    1：将颜色 x 替换为颜色 y
    2：询问序列中有多少段颜色

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int N = 1e5+5, M = 1e6+5;
    4. int n, m, idx, ans;
    5. int h[M], e[N], ne[N];
    6. int col[N], sz[M], p[M];
    7. void add(int a, int b) {
    8.     e[idx] = b, ne[idx] = h[a];
    9.     h[a] = idx++, sz[a]++;
    10. }
    11. void merge(int& x, int& y) {
    12.     if (x == y)
    13.         return ;
    14.     if (sz[x] > sz[y])
    15.         swap(x, y);
    16.     //遍历x颜色所在的这条链上的点 
    17.     for (int i = h[x]; ~i; i = ne[i]) {
    18.         int j = e[i];
    19.         //看每个点的两端是否为要改变的颜色 
    20.         ans -= (col[j-1]==y)+(col[j+1]==y);
    21.     }
    22.     //头插法将x颜色所在的链插到y颜色所在的链 
    23.     for (int i = h[x]; ~i; i = ne[i]) {
    24.         int j = e[i];
    25.         col[j] = y;
    26.         if (ne[i] == -1) {
    27.             ne[i] = h[y];
    28.             h[y] = h[x];
    29.             break;
    30.         }
    31.     } 
    32.     h[x] = -1;
    33.     sz[y] += sz[x], sz[x] = 0;
    34. }
    35. signed main() {
    36.     scanf("%d%d", &n, &m);
    37.     memset(h, -1, sizeof h);
    38.     for (int i = 1; i <= n; i++) {
    39.         scanf("%d", &col[i]);
    40.         //求出当前段数 
    41.         if (col[i] != col[i-1])
    42.             ans++;
    43.         //将每种颜色的所有序号加入对应的链
    44.         add(col[i], i);
    45.     }
    46.     for (int i = 0; i < M; i++)
    47.         p[i] = i;
    48.     while (m--) {
    49.         int op;
    50.         scanf("%d", &op);
    51.         if (op == 2) {
    52.             cout << ans << '\n';
    53.         } else {
    54.             int x, y;
    55.             scanf("%d%d", &x, &y);
    56.             merge(p[x], p[y]);
    57.         }
    58.     }
    59.     return 0;
    60. }

    image.png

    1. #include <bits/stdc++.h>
    3. using namespace std;
    5. const int N = 1e5+5, M = N*2;
    7. int n, idx, mx;
    8. int h[N], e[M], ne[M];
    9. //son[u]代表节点u的重儿子编号 
    10. int col[N], cnt[N], sz[N], son[N];
    11. long long sum, ans[N];
    13. void add(int a, int b) {
    14.     e[idx] = b;
    15.     ne[idx] = h[a];
    16.     h[a] = idx++;
    17. }
    19. int dfs_son(int u, int fa) {
    20.     sz[u] = 1;
    21.     for (int i = h[u]; ~i; i = ne[i]) {
    22.         int j = e[i];
    23.         if (j == fa)
    24.             continue;
    25.         sz[u] += dfs_son(j, u);
    26.         if (sz[j] > sz[son[u]])
    27.             son[u] = j;
    28.     } 
    29.     return sz[u];
    30. }
    32. void update(int u, int fa, int sign, int pson) {
    33.     int c = col[u];
    34.     cnt[c] += sign;
    35.     if (cnt[c] > mx) {
    36.         mx = cnt[c];
    37.         sum = c;
    38.     } else if (cnt[c] == mx) {
    39.         sum += c;
    40.     }
    41.     for (int i = h[u]; ~i; i = ne[i]) {
    42.         int j = e[i];
    43.         if (j==fa || j==pson)
    44.             continue;
    45.         update(j, u, sign, pson);
    46.     }
    47. } 
    49. void dfs(int u, int fa, int op) {
    50.     //op==0代表该点为轻儿子 
    51.     for (int i = h[u]; ~i; i = ne[i]) {
    52.         int j =e[i];
    53.         if (j==fa || j==son[u])
    54.             continue;
    55.         //搜当前点的轻儿子 
    56.         dfs(j, u, 0);
    57.     } 
    58.     if (son[u])
    59.         dfs(son[u], u, 1);
    60.     update(u, fa, 1, son[u]);
    61.     ans[u] = sum;
    62.     //若为轻儿子，则清空整个子树 
    63.     if (!op) {
    64.         update(u, fa, -1, 0);
    65.         sum = mx = 0;
    66.     }
    67. }
    69. signed main() {
    70.     scanf("%d", &n);
    71.     for (int i = 1; i <= n; i++)
    72.         scanf("%d", &col[i]);
    73.     memset(h, -1, sizeof h);
    74.     for (int i = 0; i < n-1; i++) {
    75.         int u, v;
    76.         scanf("%d%d", &u, &v);
    77.         add(u, v), add(v, u);
    78.     }
    79.     //求重儿子 
    80.     dfs_son(1, -1);
    81.     //搜答案 
    82.     dfs(1, -1, 1);
    83.     for (int i = 1; i <= n; i++)
    84.         cout << ans[i] << " \n"[i==n];
    85.     return 0;
    86. }