2023-01-19

第九章树

树结构广泛存在于我们的日常生活中，刻画了一种广泛存在的事物关系。

树结构是一种常见的数据组织形式，体现的关系是一种 “一对多” 的关系。

树的性质与遍历

例1：公司的组织架构

树是一种特殊的图，树必须是连通的。

例2：P5908 猫猫和企鹅

解法 $1$：深度优先遍历
解法 $2$：广度优先遍历

在一些题目中，具有特殊形态的树也有一些特殊的名称，通常也伴随着特殊的性质。许多题目会提供特殊树的部分分，可以把树上问题简化为序列问题或者是层数为 $2$ 树的问题，进而得到一些分数。

链：如果一棵树除了最后一个结点，每个结点都只有一个子结点，可以发现此时树退化成了线性表。当树退化成链时，从根结点开始采取深度优先遍历会产生最高的递归层数（与结点数相同），通常会用检验程序是否会递归溢出，即所谓的 “爆栈”。但也可以将树上问题直接转变成序列问题，使问题简化。
“菊花图”：树的层数为 $2$，即除了根结点外每个结点都直接连向根结点。当树的形态是 “菊花图” 时，某些算法会多次扫描点点连边，产生较高的复杂度。但正是因为这种树的深度为 $2$，故也可能存在一些可以暴力求解的性质。

树的直径与重心

树作为一种特殊的结构，其自身也具有一些特殊的性质来帮助解决一些树上问题。

例3：P1099 [NOIP2007 提高组] 树网的核

“带边权”——一般而言树到直径是在有边权的树上进行讨论的，但是无边权的树也会存在直径这一概念，此时就相当于一个所有边权均为 $1$ 的特殊情况。
“最远”——如果每一对点之间经过的所有边和点形成的路径叫做树链，那么直径就是其中最长的一条树链。这一性质对很多题目的求解都是有启发的。

求解树的直径有两种常见的方法——两边 $\text{DFS}$ 法和树形动态规划。两边 $\text{DFS}$ 法的流程如下：

随意选择一个结点 $x$ 作为起点，然后进行第一遍 $\text{DFS}$，$\text{DFS}$ 的同时记录下其他点距离 $x$ 的距离，遍历完之后，可以找到距离 $x$ 最远的点，将它记作 $y$；
将 $y$ 作为起点，重复上述的操作，再次找到距离 $y$ 距离最远的点，记作 $z$；
此时 $y$ 与 $z$ 就是直径的两个端点。这样就求出了这棵树的一条直径。

我们需要求得的最小偏心距，要么是由区间的两端点到直径一端贡献的（取较大值），要么就是直径上的一点不经过直径其他点可以到达最远距离贡献的。所以可以使用双指针法的时候求得区间端点可以走的最远距离，并统计直径上的所有点不经过直径上的其他点可以到的最远距离，就可以得到答案。

void DFS(int u, int from) {
    vertex[u].from = from;
    if (vertex[u].dis > vertex[end].dis) end = u;
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        int w = edge[e].weight;
        if (v == from || vertex[v].ondiam) continue;
        vertex[v].dis = vertex[u].dis + w;
        DFS(v, u);
    }
    return;
}

void mian() {
    vertex[1].dis = 1; DFS(1, 0);
    vertex[end].dis = 0; DFS(end, 0);
    for (int i = end, j = end; i; i = vertex[i].from) {
        while (vertex[j].dis - vertex[i].dis > s) j = vertex[j].from;
        ans = std::min(ans, std::max(vertex[end].dis - vertex[j].dis, vertex[i].dis));
    }
    for (int i = end; i; i = vertex[i].from) vertex[i].ondiam = true;
    for (int i = end; i; i = vertex[i].from) vertex[i].dis = 0, DFS(i, vertex[i].from);
    for (int i = 1; i <= n; i++) ans = std::max(ans, vertex[i].dis);
    std::cout << ans << '\n';
}

例4：P1395 会议

在一棵树中，如果我们选择某个结点为根，可以使得它的所有子树中最大的子树最小，那么这个结点就被称作这棵树的重心。从这个定义中，可以推出重心的四个性质。

以重心为树根时，所有子树的大小不超过全树大小的一半。
树中所有点到某个点到距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
在一棵树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

对于求每个点的子树大小，假设将点 $u$ 的子树大小记录进数组 $size[u]$ 中，那么可以得到以下的流程，设当前进入的点为 $u$：

初始化 $size[u] = 1$。
逐一枚举 $u$ 的所有子结点，然后递归 $\text{DFS}$，进入这些子结点。
回溯回到 $u$ 的时候，将该子结点的 $size$ 累加进 $size[u]$ 中。

void DFS(int u, int from) {
    vertex[u].size = 1;
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        if (v == from) continue;
        DFS(v, u);
        vertex[u].size += vertex[v].size;
    }
    return;
}

记这棵树总的结点为 $n$，在计算出 $size[u]$ 之后，可以得到 $n - size[u]$ 就是根方向子树的大小。

令 $f[u]$ 为把 $u$ 作为根结点，其最大的子树的大小。在遍历的过程中同时统计 $f$ 数组的最小值和对应的结点编号，最后留下的结点编号就是树的重心。

void DFS(int u, int from) {
    vertex[u].size = 1;
    vertex[u].dist = 0;
    vertex[u].f = 0;
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        if (v == from) continue;
        DFS(v, u);
        vertex[u].size += vertex[v].size;
        vertex[u].dist += vertex[v].size + vertex[v].dist;
        vertex[u].f = std::max(vertex[u].f, vertex[v].size);
    }
    vertex[u].f = std::max(vertex[u].f, n - vertex[u].size);
    if (z > vertex[u].f || (z == vertex[u].f && u <= x)) {
        z = vertex[u].f;
        y = vertex[u].dist;
        x = u;
    }
    return;
}

最近公共祖先

例5：P3379 【模板】最近公共祖先（LCA）

最近公共祖先（$\text{Lowest Common Ancestor, LCA}$）是讨论树上两个点的联系时最重要的一个概念。从图上来看，最近公共祖先是从树根到这两个结点的路径开始分叉的起点，在讨论树上的一些路径问题时，她是一个非常关键的路径分界点。

假设目前要求点 $u$ 和 $v$ 的最近公共祖先。

首先找到两点中深度较深的点（在树上的深度越深表示其越往下），不妨设深度较深的点为 $u$，不停的将 $u$ 往上提，直到 $u$ 的深度和 $v$ 一样。
同时将 $u$ 和 $v$ 向上提，直到 $u$ 和 $v$ 变成了同一个点。这个点就是要求的最近公共祖先。

分析这个算法，每次询问最近公共祖先的时候最坏的情况是需要爬完整棵树，所以每次询问的复杂度是 $\mathcal O(n)$ 的。

解法 $1$（倍增算法）：

void DFS(int u, int from) {
	vertex[u].ancestor[0] = from;
	vertex[u].depth = vertex[from].depth + 1;
	for (int p = 1; p <= logN; p++) vertex[u].ancestor[p] = vertex[vertex[u].ancestor[p - 1]].ancestor[p - 1];
	for (int e = vertex[u].head; e; e = edge[e].next) {
		int v = edge[e].head;
		if (v != from) DFS(v, u);
	}
	return;
}

int LCA(int u, int v) {
	if (vertex[u].depth < vertex[v].depth) std::swap(u, v);
	for (int p = logN; p >= 0; p--) if (vertex[vertex[u].ancestor[p]].depth >= vertex[v].depth) u = vertex[u].ancestor[p];
	if (u == v) return u;
	for (int p = logN; p >= 0; p--) {
		if (vertex[u].ancestor[p] != vertex[v].ancestor[p]) {
			u = vertex[u].ancestor[p];
			v = vertex[v].ancestor[p];
		}
	}
	return vertex[u].ancestor[0];
}

这里有个细节，最后求得的最近公共祖先是 $vertex[u].ancestor[0]$，而不是 $u$。这是因为循环最终只枚举到了 $0$，而 $2^0 = 1$，所以找到的目标并不是两个点本身，而是它们的父亲结点。

由于 $n$ 的二进制下的位数有 $\log(n)$ 个，所以使用倍增算法预处理的时间复杂度是 $\mathcal O(n \log n)$，单次询问的时间复杂度是 $\mathcal O(\log(n))$ 的。

解法 $2$（$\text{Tarjan}$ 算法）：

能否让遍历整棵树的过程变得更有价值一点，能够解决不止一次的询问，甚至所有询问呢？

这就是介绍离散化时提到过的离线思想，将所有的询问记录下来，最后仅通过一次统一的计算，即可求得所有要询问的点对点答案。

可以发现，如果有两个点 $x, y$ 都在结点 $u$ 的子树内，那么它们的最近公共祖先就是 $u$。当然，这里的 $u$ 我们也会有要求，它必须得离这两个点尽量的近。也就是说 $x, y$ 是 $u$ 的不同分支。

一个结点的子树一定是它所有祖先结点的子树的一个部分。也就是说，当递归处理完一个结点并且返回的时候，可以将已经访问过的该子树的所有部分直接划归为它的父结点的一部分。以此类推，最后所有的结点都会成为根结点的子树。

读入所有的边建树。同时将查询也直接读入存储。如果要查询的边为 $u$ 和 $v$，就在 $u$ 的要查询结点记录中记录 $v$，并且在 $v$ 的要查询结点记录中记录 $u$。
从根结点开始 $\text{DFS}$。
在进入一个结点的时候，首先在并查集中将它的父亲设为自己。如果它还有没有被访问过的子结点，就先进入子结点；
在回到这个点时，处理和这个点相关的所有询问。遍历这个点的待查询结点，如果里面有已经访问过的结点，那么该结点所在的并查集的代表元就是他们的公共祖先；
回溯离开该结点时，在并查集上将它所处的集合与它的父亲结点所处的集合合并。

void DFS(int u, int from) {
    vertex[u].fa = u;
    vertex[u].vis = true;
    for (int e = vertex[u].headE; e; e = edge[e].next) {
        int v = edge[e].head;
        if (vertex[v].vis) continue;
        DFS(v, u);
        DSU.Union(v, u);
    }
    for (int q = vertex[u].headQ; q; q = query[q].next) {
        int i = query[q].id;
        int v = query[q].other;
        if (!vertex[v].vis) continue;
        ans[i] = DSU.Find(v);
    }
    return;
}

这是一个离线算法，因为这里的并查集结构较为特殊，因此即时是只使用路径压缩优化，单次 $\text{Find}$ 操作的均摊复杂度也是 $\mathcal O(1)$，因此该算法的时间复杂度为 $\mathcal O(n + m)$。

例6：P3128 [USACO15DEC]Max Flow P

如果实在线性表中，多次操作从第 $i$ 到第 $j$ 个元素都增加 $1$，最后统计每个元素都值，可以使用差分思想——维护差分序列，在区间开头 $+ 1$，区间结束后 $- 1$，最后求前缀和还原序列。在树上也可以使用同样的操作，这种操作被称为树上差分。

令 $LCA(A, B)$ 表示 $A$ 结点和 $B$ 结点的最近公共祖先，$fa(u)$ 为结点 $u$ 的父节点，$p$ 数组就是差分数组，$p[u] = p[fa(u)]$ 表示 $u$ 结点的点权。

假设从 $u$ 到 $v$ 的路径上每个元素都要增加 $1$，那么这条路径是从 $u$ 到 $LCA(u, v)$ 再到 $v$ 的，所以可以把从 $u$ 到 $LCA(u, v)$ 与 $LCA(u, v)$ 到 $v$ 两条路径加 $1$，由于结点 $LCA(u, v)$ 重复计算了一次，所以这个点到点权还要减 $1$。因此，只需将 $p[u]$ 和 $p[v]$ 增加 $1$，$p[LCA(u, v)]$ 和 $p[fa(LCA(u, v))]$ 各减 $1$ 即可。使用倍增求 $\text{LCA}$。最后遍历整棵树，根据差分数组计算前缀和，还原出每个点到点权并统计答案。

void DFS(int u, int from) {
    for (int p = 1; p <= logN; p++) vertex[u].fa[p] = vertex[vertex[u].fa[p - 1]].fa[p - 1];
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        if (v == from) continue;
        vertex[v].fa[0] = u;
        vertex[v].dep = vertex[u].dep + 1;
        DFS(v, u);
        vertex[u].val += vertex[v].val;
    }
    ans = std::max(ans, vertex[u].val);
    return;
}

void mian() {
    DFS(1, 0);
    for (int i = 1; i <= K; i++) {
        vertex[s[i]].val++;
        vertex[t[i]].val++;
        vertex[LCA(s[i], t[i])].val--;
        vertex[vertex[LCA(s[i], t[i])].fa[0]].val--;
    }
    DFS(1, 0);
    return;
}

第九章 树