前置芝士
树连剖分及其思想，以及优化时间复杂度的原理。
讲个笑话这个东西其实和 Dsu（并查集）没什么关系。
算法本身
Dsu On Tree，一下简称 DOT，常用于解决子树间的信息合并问题。
其实本质上可以理解为高维树上 DP 的空间优化，也可以理解为暴力优化。
在这里我们再次明确一些定义：
- 重儿子 & 轻儿子：一个节点的儿子中子树最大的儿子称为该节点的重儿子，其余的儿子即为轻儿子。特殊的，如果子树最大的有多个，我们任取一个作为重儿子。
- 重边 & 轻边：连接一个节点与它的重儿子的边称为重边，连接一个节点与它的轻儿子的边称为轻边。
- 重链 & 轻链：全由重边构成的链称为重链，全由轻边构成的链称为轻链。重链和轻链互不相交。
对于需要统计一个子树的信息的问题，暴力的时间复杂度通常是 (O(n^2)) 。
为了优化时间复杂度，DOT 采用了一个非常巧妙的转移方式。
我们利用 (O(1)) 的时间复杂度维护并上传每个节点的重儿子及其子树的信息。
在遭遇一次查询时，我们再暴力统计当前节点的所有轻儿子及其子树信息，并和重儿子信息结合得到答案。可以证明到对于每个节点统计轻儿子及其子树的时间复杂度和是 (O(n log_2 n)) 的。具体流程详见代码。
时间复杂度具体口胡证明方法如下。
树上性质 1
结论：如果有一条轻边 ((u, v))，且 (u) 是 (v) 的父亲。则一定有 (size(v) leq frac {size(u)} {2}) 。其中 (size(x)) 表示 (x) 的子树大小。
不难发现，若 (size(v) > frac {size(u)} {2}) ，则它一定是 (u) 的重儿子，这与轻边 ((u, v)) 矛盾，得证。
树上性质 2
结论：从某一子树的根节点 (u) 到该子树上的任意节点 (v) 的路径经过的轻边数一定小于等于 (log_2(size(u)))。
由性质 (1) 可知，经过一条轻边，至少会将节点个数减半。设总共会经过 (e) 条轻边，则有 (size(v) leq frac {size(u)} {2^e})。且 (size(v) geq 1)，所以有 (1 leq frac {size(u)} {2^e})。故 (2^e leq size(u))，即 (e leq log_2(size(u)))，得证。
关于统计轻儿子的时间复杂度
对于当前节点 (u)，到达其任意子树上的节点经过的轻边数小于等于 (log_2(size(u)))。故可以粗略理解为在这条路径上存在 (log_2(size(u))) 个轻儿子。所以在这个子树上总共有小于等于 (size(u)log_2 size(u)) 个亲儿子。
而所有的重儿子子树我们都是一直向上传递，直到遇到一条轻边，故重儿子部分仍然是 (O(1))。
那么对于 (u)，得到它完整的信息所需时间复杂度为 (size(u)log_2 size(u))， 故对于根节点，整个树的信息统计仅需耗时 (n log_2 n)。
具体实现
#include <cstdio>
#include <vector>
using namespace std;
typedef long long LL;
int Max(int x, int y) { return x > y ? x : y; }
int Min(int x, int y) { return x < y ? x : y; }
int Abs(int x) { return x < 0 ? -x : x; }
int read() {
int k = 1, x = 0;
char s = getchar();
while (s < '0' || s > '9') {
if (s == '-')
k = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * k;
}
void write(LL x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
void print(LL x, char s) {
write(x);
putchar(s);
} // 漂亮的输入输出优化及一些模板。
const int MAXN = 1e5 + 5;
struct data {
int id, x;
// id 表示这是第几个查询，x 表示是谁的子树信息。
data() {}
data(int Id, int X) {
id = Id;
x = X;
}
} vector<data> q[MAXN];
// DOT 虽然解决了时间复杂度，但如果想要保存所有子树的信息还是有平方的空间复杂度。
// 所以我们经常采用边跑 DOT，边在有查询的节点 x 上统计答案的思路。
vector<int> mp[MAXN];
void Add_Edge(int u, int v) {
mp[u].push_back(v);
mp[v].push_back(u);
} // 加边 & 建树。
int Son[MAXN], Size[MAXN];
// Son 代表节点 u 的重儿子节点编号，Size 代表节点 u 的子树大小。
LL ans[MAXN];
// 用于统计答案。
void dfs(int u, int fa) {
Size[u] = 1;
Son[u] = -1;
int ma = -1; // 用于寻找最大子树。
// 一些初始化。
for (int i = 0, v; i < mp[u].size(); i++) {
v = mp[u][i];
if (v == fa)
continue;
dfs(v, u);
Size[u] += Size[v]; // 计算子树大小。
if (Size[v] > ma) {
ma = Size[v];
Son[u] = v; // 找重儿子。
}
}
}
int son = -1;
void calc(int u, int fa, int val) { // 暴力统计除重儿子及其子树外的残缺子树信息。
...; // 一些操作因题而异。
for (int i = 0, v; i < mp[u].size(); i++) {
v = mp[u][i];
if (v == fa || v == son)
continue;
calc(v, u, val);
}
}
void dfs2(int u, int fa, bool keep) {
// u, fa 来自树上遍历的常规变量。
// 若 keep 为 1，表示当前节点是 fa
// 的重儿子，当前节点统计的轻儿子加重儿子的信息不需要清空，保留下来直接上传。 若 keep 为 2，表示当前节点是
// fa 的轻儿子，则当前节点统计的轻儿子加重儿子的信息需要清空，不清空的话，在 fa 上会再统计一次，这一段是
// DOT 的核心操作，可以借助画图深入理解。
for (int i = 0, v; i < mp[u].size(); i++) {
v = mp[u][i];
if (v == fa || v == Son[u])
continue;
dfs2(v, u, false);
}
if (Son[u] != -1) {
dfs2(Son[u], u, true);
son = Son[u];
}
calc(u, fa, 1); // 统计贡献。
for (int i = 0; i < q[u].size(); i++) ans[q[u][i].id] = ...;
son = -1;
// 注意，清空贡献是整个子树，不止是去除了重儿子及其子树的残缺子树。
// 当然这里的不会影响到总体的时间复杂度。见补充
if (!keep)
calc(u, fa, -1); // 清空贡献。
}
int main() {
// 显然主函数因题而异。
int n = read();
for (int i = 1, u, v; i < n; i++) {
u = read(), v = read();
Add_Edge(u, v);
}
int m = read();
for (int i = 1; i <= m; i++) {
int x = read();
q.push_back(data(i, x));
}
dfs(1, -1);
dfs2(1, -1, 1);
for (int i = 1; i <= m; i++) print(ans[i], ' ');
return 0;
}
补充
对于每一层，我们需要清空的节点个数大概是 (frac n {2^e}) 个（即当前层轻儿子的子树大小和），所以总需要清空的节点数近似于 (sum_{e = 1}^{lfloor log_2 n floor} frac n {2^e})，简单化简发现它等于 (n imes (frac 1 2 + dots + frac 1 {2^{lfloor log_2 n floor}}))，即 (n imes (1 - frac 1 {2^{lfloor log_2 n floor}}))，显然它甚至连 (n) 都达不到，故其不为算法瓶颈。
应用场景
给两个比较常见的适用模型吧。
大概是维护一些子树信息，或者维护一些与同一层，同一深度有关的信息时常用。
T1「CF600E」Lomsat gelral
求子树众数和。这显然可以 dfn 序加一些数据结构来做。考场上就直接套莫队吧。
但因为我们在讲 DOT，所以说这是一道 DOT。
我们尝试存储一个子树中每一种不同颜色出现的次数。然后再维护一个 (sum) 作为每次的答案。
#include <cstdio>
#include <vector>
using namespace std;
typedef long long LL;
int Max(int x, int y) {
return x > y ? x : y;}
int Min(int x, int y) {
return x < y ? x : y;}
int Abs(int x) {
return x < 0 ? -x : x;}
int read() {
int k = 1, x = 0;
char s = getchar();
while (s < '0' || s > '9') {
if (s == '-')
k = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * k;
}
void write(LL x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
void print(LL x, char s) {
write(x);
putchar(s);
}
const int MAXN = 1e5 + 5;
vector<int> mp[MAXN];
void Add_Edge(int u, int v) {
mp[u].push_back(v);
mp[v].push_back(u);
}
int Son[MAXN], cnt[MAXN], Size[MAXN], c[MAXN];
LL ans[MAXN];
void dfs(int u, int fa) {
Size[u] = 1;
Son[u] = -1;
int ma = -1;
for (int i = 0, v; i < mp[u].size(); i++) {
v = mp[u][i];
if (v == fa)
continue;
dfs(v, u);
Size[u] += Size[v];
if (Size[v] > ma) {
ma = Size[v];
Son[u] = v;
}
}
}
int son = -1, ma = -1;
LL sum = 0;
void calc(int u, int fa, int val) {
cnt[c[u]] += val;
if (cnt[c[u]] > ma) { // 更改众数。
ma = cnt[c[u]];
sum = c[u];
} else if (cnt[c[u]] == ma) // 因为时众数和，所以我们允许多个众数存在。
sum += c[u];
// 核心操作。
for (int i = 0, v; i < mp[u].size(); i++) {
v = mp[u][i];
if (v == fa || v == son)
continue;
calc(v, u, val);
}
}
void dfs2(int u, int fa, bool keep) {
for (int i = 0, v; i < mp[u].size(); i++) {
v = mp[u][i];
if (v == fa || v == Son[u])
continue;
dfs2(v, u, false);
}
if (Son[u] != -1) {
dfs2(Son[u], u, true);
son = Son[u];
}
calc(u, fa, 1);
son = -1;
ans[u] = sum; // 更新答案即可。
if (!keep) {
calc(u, fa, -1);
sum = 0, ma = 0;
}
}
int main() {
int n = read();
for (int i = 1; i <= n; i++) c[i] = read();
for (int i = 1, u, v; i < n; i++) {
u = read(), v = read();
Add_Edge(u, v);
}
dfs(1, -1);
dfs2(1, -1, 1);
for (int i = 1; i <= n; i++) print(ans[i], ' ');
return 0;
}
T2「CF208E」Blood Cousins
题目大意：若节点 (u) 和节点 (v) 有一个公共祖先 (t)，且 (t) 到 (u)、(v) 的距离均为 (k)，则称 (u)，(v) 互为 (k) 级血亲，现给出 (m) 次询问，每次查询 (x) 有多少个 (k) 级血亲。
我们稍微变形一下。如果以 (x) 为起点向上移动 (k) 个单位到 (y)，则答案即为在 (y) 的子树中与 (y) 相差 (k) 个单位的节点的个数。
这就是一个明显的 DOT 了。我们维护每个深度的节点个数，如果现在回溯到 (x) 了，则当前记录的信息即为该子树的信息。若当前节点有查询要求，统计即可。
将 (x) 向上移动采用倍增。
#include <cstdio>
#include <vector>
using namespace std;
typedef long long LL;
int Max(int x, int y) {
return x > y ? x : y;}
int Min(int x, int y) {
return x < y ? x : y;}
int Abs(int x) {
return x < 0 ? -x : x;}
int read() {
int k = 1, x = 0;
char s = getchar();
while (s < '0' || s > '9') {
if (s == '-')
k = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * k;
}
void write(LL x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
void print(LL x, char s) {
write(x);
putchar(s);
}
const int MAXN = 1e5 + 5;
vector<int> mp[MAXN];
void Add_Edge(int u, int v) {
mp[u].push_back(v);
mp[v].push_back(u);
}
int Son[MAXN], Size[MAXN], fa[MAXN][35], dep[MAXN], ans[MAXN];
struct data {
int d, id;
data() {}
data(int D, int Id) {
d = D;
id = Id;
}
};
vector<data> q[MAXN];
void dfs(int u, int f) {
Size[u] = 1;
Son[u] = -1;
int ma = -1;
fa[u][0] = f;
for (int i = 1; i <= 18; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (int i = 0, v; i < mp[u].size(); i++) {
v = mp[u][i];
if (v == f)
continue;
dep[v] = dep[u] + 1;
dfs(v, u);
Size[u] += Size[v];
if (Size[v] > ma) {
ma = Size[v];
Son[u] = v;
}
}
}
int son = -1, cnt[MAXN];
void calc(int u, int fa, int val) {
cnt[dep[u]] += val;
for (int i = 0, v; i < mp[u].size(); i++) {
v = mp[u][i];
if (v == fa || v == son)
continue;
calc(v, u, val);
}
}
void dfs2(int u, int fa, bool keep) {
for (int i = 0, v; i < mp[u].size(); i++) {
v = mp[u][i];
if (v == fa || v == Son[u])
continue;
dfs2(v, u, false);
}
if (Son[u] != -1) {
dfs2(Son[u], u, true);
son = Son[u];
}
calc(u, fa, 1);
son = -1;
for (int i = 0; i < q[u].size(); i++) ans[q[u][i].id] = cnt[dep[u] + q[u][i].d] - 1;
if (!keep)
calc(u, fa, -1);
}
int main() {
int n = read();
for (int i = 1, x; i <= n; i++) {
x = read();
Add_Edge(x, i);
}
dfs(0, 0);
int m = read();
for (int i = 1, x, p; i <= m; i++) {
x = read(), p = read();
for (int j = 0; j <= 18; j++)
if ((1 << j) & p)
x = fa[x][j];
if (x != 0 && x != -1)
q[x].push_back(data(p, i));
}
dfs2(0, 0, 1);
for (int i = 1; i <= m; i++) print(ans[i], ' ');
return 0;
}