Disjoint Set Union，树上启发式合并。
我也不知道为什么叫 dsu on tree ......
如果不算套的数据结构的话，这个东西可以在 \(O(\log{n})\) 的时间内完成对子树信息的查询。
我们每次 dfs 到一个点 u ，执行以下流程：
- 递归处理所有的轻儿子，不保留所有轻儿子的信息
- 递归处理重儿子，保留重儿子的信息
- 计算整棵子树的答案(即轻儿子 +它本身，重儿子的答案已经保留)
- 若 u 不是重儿子，清楚它的信息
看上去是个暴力，但实际上可以优化到 \(O(\log{n})\) 。
如果结点 u 会被遍历 x 次，那么显然它的重儿子也会被遍历 x 次，而轻儿子会被遍历 2x 次。也就是说，一个点会被重复计算的次数是它到根结点路径上的轻边条数，而一个点到根结点的路径上的轻边数量不会超过 \(\log{n}\) 条，故这个算法的复杂度是 \(O(\log{n})\) 。
给出一棵 \(n\) 个结点的树，每个结点有一个颜色 \(c_i\) 。 询问 \(q\) 次，每次询问以 \(v\) 结点为根的子树中，出现次数 \(≥k\) 的颜色有多少种。树的根节点是 \(1\) 。
#include <bits/stdc++.h>
#define N 100005
#define lowbit(i) i&-i
#define PII pair<int, int>
using namespace std;
int gi() {
int x = 0, f = 1; char c = getchar();
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n, q;
int col[N], ans[N];
int sz[N], son[N], tot[N], c[N];
int to[N << 1], nxt[N << 1], hd[N << 1], cnt;
vector <PII> ve[N];
vector <PII> :: iterator it;
void insert(int u, int v) { to[++cnt] = v, nxt[cnt] = hd[u], hd[u] = cnt; }
void add(int i, int k) {
if (!i) return;
while (i <= N) {
c[i] += k;
i += lowbit(i);
}
}
int query(int i) {
if (!i) return 0;
int ret = 0;
while (i) {
ret += c[i];
i -= lowbit(i);
}
return ret;
}
void dfs1(int u, int fa) {
sz[u] = 1;
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i];
if (v == fa) continue;
dfs1(v, u);
sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
void modify(int u, int fa, int k) {
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i];
if (v == fa) continue;
modify(v, u, k);
}
add(tot[col[u]], -1);
tot[col[u]] += k;
add(tot[col[u]], 1);
}
void dfs2(int u, int fa) {
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i];
if (v != fa && v != son[u]) dfs2(v, u), modify(v, u, -1);
}
if (son[u]) dfs2(son[u], u);
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i];
if (v != fa && v != son[u]) modify(v, u, 1);
}
add(tot[col[u]], -1);
tot[col[u]]++;
add(tot[col[u]], 1);
for (it = ve[u].begin(); it != ve[u].end(); ++it)
ans[it -> second] = query(N) - query(it -> first - 1);
}
int main() {
int u, v;
n = gi(), q = gi();
for (int i = 1; i <= n; ++i) col[i] = gi();
for (int i = 1; i < n; ++i) {
u = gi(), v = gi();
insert(u, v), insert(v, u);
}
for (int i = 1; i <= q; ++i) {
u = gi(), v = gi();
ve[u].push_back(PII(v, i));
}
dfs1(1, 0);
dfs2(1, 0);
for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
return 0;
}给你一片森林，每次询问和一个点有相同的 \(k\) 次祖先的点有多少个。
#include <bits/stdc++.h>
#define N 100003
#define PII pair<int, int>
using namespace std;
int gi() {
int x = 0, f = 1; char c = getchar();
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n, m;
int ans[N], tot[N];
int nxt[N], hd[N];
int fa[N][25], dep[N], rt[N], sz[N], son[N];
bool vis[N];
vector <PII> vec[N];
vector <PII> :: iterator it;
void insert(int u, int v) { nxt[u] = hd[v], hd[v] = u; }
void pre_dfs(int u, int f) {
sz[u] = 1, dep[u] = dep[f] + 1, fa[u][0] = f;
for (int i = 1; i <= 20; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (int v = hd[u]; v; v = nxt[v]) {
if (v == f) continue;
pre_dfs(v, u);
sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
void modify(int u, int k) {
tot[dep[u]] += k;
for (int v = hd[u]; v; v = nxt[v])
if (!vis[v]) modify(v, k);
}
void dfs(int u, bool keep) {
for (int v = hd[u]; v; v = nxt[v])
if (v != son[u]) dfs(v, 0);
if (son[u]) dfs(son[u], 1), vis[son[u]] = 1;
modify(u, 1);
vis[son[u]] = 0;
for (it = vec[u].begin(); it != vec[u].end(); ++it)
ans[it -> second] = tot[it -> first] - 1;
if (!keep) modify(u, -1);
}
int main() {
int u, v, k;
n = gi();
for (int i = 1; i <= n; ++i) {
u = gi();
if (!u) rt[++rt[0]] = i;
else insert(i, u);
}
for (int i = 1; i <= rt[0]; ++i) pre_dfs(rt[i], 0);
m = gi();
for (int i = 1; i <= m; ++i) {
u = gi(), k = gi(), v = dep[u];
for (int j = 0; j <= 20; ++j)
if (k & (1 << j)) u = fa[u][j];
vec[u].push_back(PII(v, i));
}
for (int i = 1; i <= rt[0]; ++i) dfs(rt[i], 0);
for (int i = 1; i <= m; ++i) printf("%d ", ans[i]);
return 0;
}一棵根为 1 的树，每条边上有一个字符（ a - v 共 22 种）。 一条简单路径被称为 \(Dokhtar-kosh\) 当且仅当路径上的字符经过重新排序后可以变成一个回文串。 求每个子树中最长的 \(Dokhtar-kosh\) 路径的长度。
#include <bits/stdc++.h>
#define N 500003
#define REP(i, l, r) for (int i = (l); i != (r); ++i)
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define DRP(i, l, r) for (int i = (l); i != (r); --i)
#define DFR(i, l, r) for (int i = (l); i >= (r); --i)
#define NXT(i, u) for (int i = hd[(u)], v = to[i]; i; i = nxt[i])
using namespace std;
int gi() {
int x = 0, f = 1; char c = getchar();
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n, tot;
int hd[N], nxt[N], to[N], val[N], cnt;
int dep[N], dis[N], mk[N << 5], ans[N], sz[N], son[N], st[N], ed[N], ord[N];
void insert(int u, int v, int w) {
to[++cnt] = v, val[cnt] = w, nxt[cnt] = hd[u], hd[u] = cnt;
}
void pre_dfs(int u, int fa) {
ord[++tot] = u, st[u] = tot;
sz[u] = 1, dep[u] = dep[fa] + 1;
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i], w = val[i];
dis[v] = dis[u] ^ w;
pre_dfs(v, u);
sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
ed[u] = tot;
}
void modify(int u) {
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i];
if (v != son[u]) {
for (int j = st[v]; j <= ed[v]; ++j) {
int x = ord[j];
if (mk[dis[x]]) ans[u] = max(ans[u], mk[dis[x]] + dep[x] - dep[u] * 2);
for (int k = 0; k < 22; ++k) {
if (mk[dis[x] ^ (1 << k)])
ans[u] = max(ans[u], mk[dis[x] ^ (1 << k)] + dep[x] - dep[u] * 2);
}
}
for (int j = st[v]; j <= ed[v]; ++j)
mk[dis[ord[j]]] = max(mk[dis[ord[j]]], dep[ord[j]]);
}
}
}
void dfs(int u, bool keep) {
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i];
if (v != son[u]) {
dfs(v, 0);
ans[u] = max(ans[u], ans[v]);
}
}
if (son[u]) dfs(son[u], 1), ans[u] = max(ans[u], ans[son[u]]);
if (mk[dis[u]]) ans[u] = max(ans[u], mk[dis[u]] - dep[u]);
for (int i = 0; i < 22; ++i) {
if (mk[dis[u] ^ (1 << i)])
ans[u] = max(ans[u], mk[dis[u] ^ (1 << i)] - dep[u]);
}
mk[dis[u]] = max(mk[dis[u]], dep[u]);
modify(u);
if (!keep) for (int i = st[u]; i <= ed[u]; ++i) mk[dis[ord[i]]] = 0;
}
int main() {
int u; char ch;
n = gi();
for (int i = 2; i <= n; ++i) {
u = gi(); scanf("%c", &ch);
insert(u, i, 1ll << (ch - 'a'));
}
pre_dfs(1, 0);
dfs(1, 0);
for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
return 0;
}原文：https://www.cnblogs.com/hlw1/p/12263914.html