对于一棵树，如果我们需要统计每一个点的子树的信息，比如求子树中哪个点权出现的次数最多（最大值这种就是树剖裸题了搞什么$dsu$ $on$ $tree$？）这样子，如果我们对于每一个子树都进行遍历的话，时间复杂度将达到$O(n^2)$，当$n \leq 1e5$的时候，这个时间复杂度无法接受。那么我们应该怎么办呢？这个时候就需要使用$dsu$ $on$ $tree$。
我们知道，树链剖分可以把一棵树分成$O(log_2 n)$条重链，剩下的都是轻边。现在证明一下从根到某结点经过的轻边的数量：因为每经过一条轻边，结点数是一半，所以$size \leq \frac{n}{2^{edge}}$，又$n > 2^{edge}$，所以$edge<log_2 n$。即只会经过$O(log_2 n)$条轻边。
我们先从上到下遍历结点，然后对于某个节点，我们访问所有的轻儿子，然后求得了这些轻儿子的子树信息，接下来我们考虑重儿子。访问重儿子，然后保留重儿子的信息，对于轻儿子就暴力处理。我们分析它的时间复杂度：我们假设这棵子树的大小是$n$。则我们暴力统计所有轻儿子的时间复杂度是$O(log_2 n)$，保留重儿子信息，即重儿子信息$O(1)$上推，则我们就可以$O(log_2 n)$求出这棵子树的信息。
当然，树不能有修改，不然重儿子的信息就会失效。
并且，所有询问都针对子树。
其思想是启发式合并，因为我还没有学，所以先这样，学了再回来总结。
算法流程：
一、轻重链剖分
然后这个过程不好理解，我给出路径：
进入轻儿子直到叶节点，处理这个叶节点的信息，然后更新这个轻儿子答案，并删除轻儿子的信息，然后回溯到它的父亲，然后进入重儿子，假设这个重儿子是叶节点，我们处理重儿子的信息，保留信息并更新答案，然后回溯到它的父亲，它的父亲将会暴力统计这个轻儿子的信息，然后更新自己（因为重儿子信息没有删除），然后删除轻儿子的信息，这个节点处理完，回溯到上一层，这样子我们就保留了重儿子的信息以处理这个子树根结点的父亲。显然，因为本身我们进入的是一个轻儿子，所以在处理完它的父节点时，这个轻儿子的信息会被删除（这个建议画图理解，非常绕）。
给出一棵树，求出每个节点的子树中出现次数最多的颜色的编号和。
直接$dsu$ $on$ $tree$，用桶记录颜色次数即可。
AC代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e5 + 5; vector<int> G[MAXN]; int col[MAXN], son[MAXN], sz[MAXN]; bool vis[MAXN]; ll tot[MAXN], ans[MAXN]; ll maxn, c; void dfs1(int u, int fa) { sz[u] = 1; for (auto i : G[u]) if (i != fa) { dfs1(i, u); sz[u] += sz[i]; if (sz[i] > sz[son[u]]) son[u] = i; } } void update(int u, int fa, int p) { tot[col[u]] += p; if (p > 0 && maxn == tot[col[u]]) c += col[u]; else if (p > 0 && maxn < tot[col[u]]) c = col[u], maxn = tot[col[u]]; for (auto i : G[u]) if (i != fa && !vis[i]) update(i, u, p); } void dfs2(int u, int fa, int op) { for (auto i : G[u]) if (i != son[u] && i != fa) dfs2(i, u, 0); if (son[u]) dfs2(son[u], u, 1), vis[son[u]] = 1; update(u, fa, 1), ans[u] = c; if (son[u]) vis[son[u]] = 0; if (!op) update(u, fa, -1), maxn = c = 0; } int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &col[i]); int a, b; for (int i = 1; i < n; ++i) { scanf("%d%d", &a, &b); G[a].push_back(b); G[b].push_back(a); } dfs1(1, 0); //tot: n dfs2(1, 0, 0); //tot: n+2nlogn for (int i = 1; i <= n; ++i) printf("%lld%c", ans[i], i == n ? ‘\n‘ : ‘ ‘); return 0; }
注：为什么$update$之后$vis[son[u]]$要置零，这是因为，只要$op$是$0$，这个对于其父亲来说轻儿子，所以实际上执行到这里的时候，它的父亲的重儿子的信息处理好了，所以就要把这个轻儿子的所有信息全部删去，这个很绕。
给出一棵树，树上每个节点上有一个小写字符，给出一些询问，询问包括节点和深度，求出以这个节点为根，固定深度的节点上能否组成一个回文串。
看满不满足使用条件：无修改，查询子树。满足条件，然后我们看维护什么，维护一个回文串，这个其实不好做，显然我们不能把这些深度的字符串都保存下来，因为这将达到$O(n^2)$的空间，所以我们只能用更加省空间的方案。一个字符串构成回文串，里面的同种字符的数量至多出现一个奇数，所以我们实际关注的是，这些字符串模$2$的和是不是小于$2$，因为模$2$就是二进制，所以我们直接用一个整数维护这个字符串，用异或增减字符即可。
为什么我们这里可以处理相对某个结点深度大于$1$的结点呢？这是因为处理完重儿子之后到删除轻儿子信息之前，这棵子树的任何一个结点除了它自己的信息都是知道的，因为重儿子信息被保存，轻儿子子树的所有结点信息被处理出来，所以就可以把这个子树为根的询问全部回答了。
AC代码：
#include <bits/stdc++.h> using namespace std; const int MAXN = 5e5 + 5; vector<int> G[MAXN]; struct Q { int pos, dep; Q(int _pos, int _dep) : pos(_pos), dep(_dep) {} }; vector<Q> q[MAXN]; bool ans[MAXN]; int dep[MAXN], val[MAXN], sz[MAXN]; int tot[MAXN], son[MAXN]; bool vis[MAXN]; void dfs1(int u, int fa) { dep[u] = dep[fa] + 1; sz[u] = 1; for (auto i : G[u]) if (i != fa) { dfs1(i, u); sz[u] += sz[i]; if (sz[i] > sz[son[u]]) son[u] = i; } } bool get1(int val) { int rt = 0; while (val) rt += val % 2, val >>= 1; return rt < 2; } void update(int u, int fa) { tot[dep[u]] ^= val[u]; for (auto i : G[u]) if (i != fa && !vis[i]) update(i, u); } void del(int u, int fa) { tot[dep[u]] = 0; for (auto i : G[u]) if (i != fa && !vis[i]) del(i, u); } void dfs2(int u, int fa, int op) { for (auto i : G[u]) if (i != fa && i != son[u]) dfs2(i, u, 0); if (son[u]) dfs2(son[u], u, 1), vis[son[u]] = 1; update(u, fa); for (int i = 0; i < q[u].size(); ++i) ans[q[u][i].pos] = get1(tot[q[u][i].dep]); if (son[u]) vis[son[u]] = 0; if (!op) del(u, fa); } char str[MAXN]; int main() { int n, m; scanf("%d%d", &n, &m); int a; for (int i = 1; i < n; ++i) { scanf("%d", &a); G[i + 1].push_back(a); G[a].push_back(i + 1); } scanf("%s", str + 1); for (int i = 1; i <= n; ++i) val[i] = 1 << (str[i] - ‘a‘); int x, y; for (int i = 1; i <= m; ++i) { scanf("%d%d", &x, &y); q[x].push_back(Q(i, y)); } dfs1(1, 0); dfs2(1, 0, 0); for (int i = 1; i <= m; ++i) printf(ans[i] ? "Yes\n" : "No\n"); return 0; }
（$To$ $be$ $continued$）博主先去做了
原文：https://www.cnblogs.com/Aya-Uchida/p/12716998.html
