树上启发式合并（dsu on tree)

　　树上启发式合并属于暴力的优化，复杂度O(nlogn)

　　主要解决的问题特点在于：

　　　　1.对于树上的某些信息进行查询

　　　　2.一般问题的解决不包含对树的修改，所有答案可以离线解决

　

　　算法思路：这类问题的特点在于父节点的信息是通过子节点更新而来

　　所以如果是暴力解决的话就是对每一个节点往下跑一次图，复杂度在O(n^2)

　　因为父节点是有子节点跟新而来，所以我们可以考虑每次保留一部分子节点的信息，将另一部分子节点信息暴力合并得到父节点的信息

　　这样的话我们就考虑保留重子节点的信息（子树中子节点数最多的节点），这样我们就可以减少合并次数

　　从树链剖分的性质中我们可以得知，一个点到根节点最多不超过logn条路径，所以这样就将算法的复杂度大大降低为O(nlogn)

　　引例一：https://www.luogu.com.cn/problem/U41492

　　求一颗子树中出现的颜色个数

　　

　　我们的具体做法如下：

　　1.每次先遍历轻子节点，计算轻子节点的信息和答案，但是不保存其信息

　　2.遍历重子节点，计算重子节点信息和答案，保存其信息

　　3.暴力合并轻子节点信息到重子节点上

　　这里比较有疑惑的就是第一和第三步能不能合并到一起，以及为什么在第一步不保存轻子节点的信息。

　　其实这是同一个问题，之所以在第一次遍历轻子节点的时候不保存其信息，是为了避免轻子节点的信息对重子节点信息的影响

　　换句人话讲：因为我们统计节点颜色的时候，我们是定义一个cnt[]数组进行统计，假设我们第一次遍历轻子节点的时候保留信息

　　cnt[]数组记录下当前有的颜色数为totcol = 5,那么在遍历重子节点的时候，如果遍历到一个新的颜色，totcol这个时候会变成6，进而

　　在保存数据的时候在重子节点这记录为当前子树内的颜色数为6，这就造成了数据错误，如果不记录轻子节点信息的情况下，当回溯到

　　父节点时，轻子节点的信息会不断随着del()函数，totcol减少，然后从0开始遍历重子节点，这样才能正确的计算出重子节点重蕴含的信息。

　　

　　

 1 # include<iostream>

 2 # include<bits/stdc++.h>

 3 using namespace std;

 4 # define int long long

 5 # define endl "\n"

 6 const int N = 2e5 + 10;

 7 int sz[N], big[N], col[N], l[N], r[N], rnk[N], totdfn;
　　/*
　　　　　sz[]子树大小
　　　　big[]重儿子
　　　　l[],r[]dfs序列下，子树的边界
　　　　rnk[] dfs序列对应的节点编号
　　　　totdfn dfs序列
　　*/

 8 int ans[N], cnt[N], totcolor;

 9 vector<int> g[N];

10 void add(int u) {

11     if (cnt[col[u]] == 0) ++totcolor;

12     cnt[col[u]]++;

13 }

14

15 void del(int u) {

16     cnt[col[u]]--;

17     if (cnt[col[u]] == 0) --totcolor;

18 }

19

20 int getans() {

21     return totcolor;

22 }

23 void dfs0(int u, int fa) {

24     l[u] = ++totdfn;

25     rnk[totdfn] = u;

26     sz[u] = 1;

27     for (int v : g[u]) {

28         if (v != fa) {

29             dfs0(v, u);

30             sz[u] += sz[v];

31             if (!big[u] || sz[v] > sz[big[u]]) big[u] = v;

32         }

33

34     }

35     r[u] = totdfn;

36 }

37 //keep表示是否保留节点信息

38 void dfs1(int u, int fa, bool keep) {

39     for (int v : g[u]) {

40         if (v != fa && v != big[u]) {

41             dfs1(v, u, false);

42         }

43     }//计算轻子节点信息

44     if (big[u]) {

45         dfs1(big[u], u, true);

46     }//计算重子节点信息

47     for (int v : g[u]) {

48         if (v != fa && v != big[u]) {

49             for (int i = l[v]; i <= r[v]; ++i) {

50                 add(rnk[i]);

51             }

52         }

53     }

54     add(u);

55     ans[u] = getans();

56     if (keep == false) {

57         for (int i = l[u]; i <= r[u]; ++i) {

58             del(rnk[i]);

59         }

60     }//删除轻子节点信息

61 }

62

63 void solve() {

64     int n;

65     cin >> n;

66     for (int i = 1; i  <= n; ++i) g[i].clear();

67     for (int i = 1; i < n; ++i) {

68         int u, v;

69         cin >> u >> v;

70         g[u].push_back(v);

71         g[v].push_back(u);

72     }

73     for (int i  = 1; i <= n; ++i) cin >> col[i];

74     dfs0(1, 0);

75     dfs1(1, 0, false);

76     int m;

77     cin >> m;

78     while (m--) {

79         int k;

80         cin >> k;

81         cout << ans[k] << endl;

82     }

83

84 }

85 int tt;

86 signed main() {

87     ios::sync_with_stdio(false);

88     cin.tie(0);

89     cout.tie(0);

90     tt = 1;

91     while (tt--)solve();

92

93

94     return 0;

95 }

　　

树上启发式合并（dsu on tree)的相关教程结束。