前置芝士
树连剖分及其思想，以及优化时间复杂度的原理。
讲个笑话这个东西其实和 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 \rfloor} \frac n {2^e}\)，简单化简发现它等于 \(n \times (\frac 1 2 + \dots + \frac 1 {2^{\lfloor log_2 n \rfloor}})\)，即 \(n \times (1 - \frac 1 {2^{\lfloor log_2 n \rfloor}})\)，显然它甚至连 \(n\) 都达不到，故其不为算法瓶颈。