树上问题2——树的直径

概念

树上任意两节点之间最长的简单路径即为树的直径。

显然，一棵树可以有多条直径（虽然简单但容易在做题时被忽视）。

可以用两次 DFS 或者树形 DP 的方法在 $O(n)$ 时间求出树的直径。

求法

两次 DFS

首先从任意节点 $y$ 开始进行第一次 DFS，到达距离其最远的节点，记为 $z$，然后再从 $z$ 开始做第二次 DFS，到达距离 $z$ 最远的节点，记为 $z'$ ，则 $z$ 到 $z'$ 的路径即为树的直径。

显然，如果第一次 DFS 到达的节点 $z$ 是直径的一端，那么第二次 DFS 到达的节点 $z'$ 一定是直径的一端。我们只需证明在任意情况下，$z$ 必为直径的一端。

定理：在一棵树上，从任意节点 $y$ 开始进行一次 DFS，到达的距离其最远的节点 $z$ 必为直径的一端。

注：两次 DFS 不适用于带负权边情况。

性质

定理：如果树上存在多条直径，则它们的中点（到直径两端点距离相等的点）重合。

定理的证明：首先证明所有直径之间都有交点。若存在两条直径 $a→b$ 和 $c→d$ 没有交点，设 $(u,v)$ 是一条树边且 $u$ 在 $a→b$ 上，$v$ 在 $c→d$ 上，则显然 $\max(a→u,u→b)+1+\max(c→v,v→d)$ 比原直径长度大，矛盾。

再证明这些直径的交点就是中点。

若存在直径 $a→u→b$ 和 $c→u→d$ 使得 $u$ 不是 $a→b$ 的中点，则 $\max(a→u,u→b)> \frac 1 2 (c→d)$，那么 $\max(a→u,u→b)+\max(c→u,u→d)$ 一定比原直径长度大，又矛盾。

故定理成立。

例题

1. 模板：Longest path in a tree（SP1437）

题面

给定一棵 $n$ 个结点的树，求出此树的直径长。

2. 核心城市（洛谷P5536）

题面

X 国有 $n$ 座城市，$n−1$ 条长度为 $1$ 的道路。城市和道路形成一棵树。

X 国国王决定将 $k$ 座城市钦定为 X 国的核心城市，这 $k$ 座城市需满足以下两个条件：

这 $k$ 座城市可以通过道路，在不经过非核心城市的情况下两两相互到达。

定义某个非核心城市与这 $k$ 座核心城市的距离为这座城市与 $k$ 座核心城市的距离的最小值。现在要使得所有非核心城市中，与核心城市的距离最大的城市，其与核心城市的距离尽可能小。你需要求出这个最小值。

输入：第一行两个整数 $n,k$，接下来 $n-1$ 行每行两个整数表示一条道路。

输出：一个整数表示答案。

数据范围：$1 \le k \le 10^5,2 \le n \le 10^5$。

解析

先考虑最简单的情况：只有一个城市。这种情况下答案很简单，就是直径的中点。因为树上距离最远的两个点就是直径的两个端点。由之前的定理知道，多条直径的中点必然重合，因此任意一条直径的中点都是解。

那么多个点的话要怎么选呢？我们考虑以直径中点为根，那么此时的最大距离就是结点的最大深度，那么我们为了使答案变小，就需要选最深的结点所在的子树的点，且需要跟树根相连。那么我们把这个点“合并”到根结点上，每次要选的点就变成了当前树中，最深子树的根结点。

具体怎么做呢，我们把根结点以外的点按照“它为根的子树的高度-它自己的深度”进行排序，从小到大再选 $k-1$ 个即可。

3. AGC001C

题面

给你一棵 $n$ 个点的无向树，定义点 $u$ 和 $v$ 之间的距离是从 $u$ 到 $v$ 的简单路径上的边数。

你需要删除一些点，使树的直径小于等于 $k$，当且仅当删除某点不会对树的联通性产生影响时才可以删除。问至少删除多少点才可以满足要求。

输入：第一行两个整数 $n,k$，接下来 $n-1$ 行每行两个整数表示一条边。

输出：一个整数表示答案。

数据范围：$1 \le k < n \le 2000$。

解析

对 $k$ 进行奇偶讨论。

若 $k$ 为偶数，枚举直径的中点 $x$（两个）。DFS 出有多少节点可以在经过 $\frac k 2$ 条边内达到，取最小值即可。

若 $k$ 为奇数，枚举所有直径中间的边，对两端分别 DFS 即可。

作业