树的直径

树的直径

Dangerise

·

2025-04-18 20:30:39

·

算法·理论

引入

树的直径是树上最长的路径，当然，这样的直径有多条，但是它们都相等。

树的直径具有许多特殊的性质，不像其他知识点，学习树的直径我们主要要掌握直径的这些特殊性质（这使得学起来有点像几何而非 OI ）。

树形 DP 求解直径

模板题

求解直径最直观的方式就是使用树形DP了，并且相较于稍后介绍的两次搜索求解方法，树形DP也适用于带负权的情况。

我们知道，树上的任何路径都可以被表示为两个点，(u,v) 。

记 a 为它们的最近公共祖先，它事实上就是 (u,a) 和 (a,v) 两条从上到下的链构成的。

那我们依次考虑每个 a ，寻找它拥有的最长的两条一直延伸到叶子的链，再将两条链拼起来，更新答案。

我们是用 d[u] 表示 u 能到达的最深的距离。

constexpr int N=1e5+7;

int n;

vector g[N];

int d[N];

int diam;

void dfs(int u,int fa) {

int fst=0,sec=0;

for(int v:g[u]) {

if(v==fa) {

continue;

}

dfs(v,u);

if(fst

sec=fst;

fst=d[v]+1;

} else if(sec

sec=d[v]+1;

}

}

diam=max(diam,fst+sec);

d[u]=fst;

}

有时候我们还关心这个直径的两个端点，我们在求解的过程中记录端点即可。

constexpr int N=1e5+7;

struct D{

int l,u;

} d[N];

struct Diam{

int l,u,v;

} diam;

int n;

vector g[N];

void dfs(int u,int fa) {

D fst={0,u},sec={0,0};

for(int v:g[u]) {

if(v==fa) {

continue;

}

dfs(v,u);

D t=d[v];

t.l+=1;

if(fst.l

sec=fst;

fst=t;

} else if(sec.l

sec=t;

}

}

if(diam.l

diam={fst.l+sec.l,fst.u,sec.u};

}

d[u]=fst;

}

直径的性质

直径的性质基本上都依赖于 边权非负 这一先决条件。

接下来要讲解的一些性质，受限于篇幅 （懒和菜） ，只会大概向读者说明它 “为何会成立”，严谨和详细的证明将被略过，读者可另寻资料。

推荐：

StudyingFather-树网的核-题解

树的直径与中心性质整理

树上一点能到达的最远的点一定是直径的一个端点

包括这个性质，几乎所有的性质都是使用反证法来推导的。

我们假设，这个图的直径是 (s,t) 即蓝色部分，从 u 点出发，能到达的最远的路径是 (u,v) ，即绿色部分。

图中无关的点已被略去。

既然 (u,v) 是最远的路径，那么肯定有 (u,v) > (u,s) 和 (u,v) > (u,t) 。

那么我们这么一连，红色部分肯定比原有的直径更长，即 (s,v)=(s,2)+(2,u)+(u,v)>(s,2)+(2,t)=(s,t) ，则导出矛盾。

另一种情况则是：

由 (u,v)>(u,s) ，则有 (2,v) > (2,s) 。

这样红色的部分也比原直径要更长，矛盾 。

所以，树上一点能到达的最远的点一定是直径的一个端点。

那么，我们从树上任意一点出发，就可以通过达到最远的点达到直径的一端，再从这个端点出发，得到直径的另一个端点，就求出了直径的两端。

#include

using namespace std;

constexpr int N = 1e6 + 7;

int n;

vector g[N];

int fa[N], dep[N];

int dfs(int u) {

int ret = u;

for (int v : g[u]) {

if (v == fa[u]) {

continue;

}

fa[v] = u, dep[v] = dep[u] + 1;

int t = dfs(v);

if (dep[ret] < dep[t]) {

ret = t;

}

}

return ret;

}

int main() {

cin >> n;

for (int i = 1; i <= n - 1; i++) {

int u, v;

cin >> u >> v;

g[u].push_back(v);

g[v].push_back(u);

}

int epl = dfs(1);

fa[epl] = dep[epl] = 0;

int epr = dfs(epl);

printf("%d\n", dep[epr]);

}

所有直径必交于一点

现在我们来探讨多条直径之间的关系，首先，很显然，这些直径的长度都相等。

并且它们都交于一点。

假设有两条直径不相交，由于连通性，它们必定有一条路径使两条直径相连。

而通过中间这条路径，我们总能画出一条路径比两条直径都要长，而得到矛盾。

即分别取两条直径中的较长段，再拼上中间的路径。

首先，(s,t)=(u,v) 。

\max((s,2),(2,t)) > \frac{1}{2}(s,t),\max((u,5),(5,v))>\frac{1}{2}(u,v)

\max((s,2),(2,t)) + (2,5) + \max((u,5),(5,v)) > \frac{1}{2}(s,t)+\frac{1}{2}(u,v) = (s,t) = (u,v)

现在我们已经知道了两条直径交于一点，现在我们引入第三条直径。

第三条直径应该与第一，第二条直径都有交点，但是三条直径一定交于一点吗？

假如三条直径两两相交但不都交于一点，则有：

然后我们发现，我们得到了一个环，这与树是矛盾的。

所有直径共中点

这里所说的中点，并不一定指的是一个结点，它也有可能在边上。

我们考虑有两条直径。

首先，一条直径的中点一定在另一条直径上，否则：

⬛ 黑色的线段表示直径， 🟦 蓝色的点表示中点，我们已经知道直径交于一点，那么我们可以连出 🟥 红色的路径使得比两条直径更长，矛盾。

在我们得到一条直径的中点在另一条直径上后，再假设两个中点不重合，还能继续发现。

🟥 红色的路径仍要比原有直径更长。

所以两条直径的中点一定重合，进而得到所有直径的中点一定重合。

所有直径在公共部分以外的部分相等

由于我们已经得到了所有直径共交点，共中点，那么所有直径会有一个公共部分，尽管这个公共部分在有时候只是一个点。

而这三条 🟦 蓝色的路径，显然是两两相等的。

🟥 红色的显然也是。

P3304 [SDOI2013] 直径

掌握了这些性质以后，我们终于可以开始做这道题了。

题目要求，先求出直径的长度，再统计所有直径的必经边的数量。

直径怎么求不再赘述，现在来讲第二问。

刚刚我们知道了，必经边其实就是所有直径的 公共部分 的边，也就是我们要求出公共部分的边的数量。

怎么做呢？首先我们先求出任意一条直径，那么它的中点肯定在公共部分上。从中点分别往这条直径的两个端点爬，一直爬到公共部分的端点为止。

在公共部分的端点上，我们可以从这一点出发，不经过任何一条原有直径上的边，找到一条最远的路径，与这个点到最近的原有直径的端点的距离相等。

这么说有点绕，其实就是这种情况。

我们已经求出了一条直径 (a,e) ，在公共部分的端点 2 上，可以找到一条 🟦 蓝色的路径，这条路径的边不与 (a,e) 有交，与 🟥 红色路径相等。

其他就不再多说，直接放代码了。

#include

using namespace std;

#define int long long

constexpr int N = 2e5 + 7;

struct E {

int v, w;

};

int n;

vector g[N];

int fa[N], dep[N];

bool on_diam[N];

int dfs(int u) {

int ret = u;

for (E e : g[u]) {

int v = e.v, w = e.w;

if (v == fa[u] || on_diam[v]) {

continue;

}

fa[v] = u, dep[v] = dep[u] + w;

int t = dfs(v);

if (dep[ret] < dep[t]) {

ret = t;

}

}

return ret;

}

signed main() {

cin >> n;

for (int i = 1; i <= n - 1; i++) {

int u, v, w;

cin >> u >> v >> w;

g[u].push_back({v, w});

g[v].push_back({u, w});

}

int epl = dfs(1);

fa[epl] = dep[epl] = 0;

int epr = dfs(epl);

printf("%lld\n", dep[epr]);

vector diam, dis;

// 由于我们第二次搜索时以直径的一端为根

// 所以直径在这里是一条自根向下的链

{

int u = epr;

while (u != epl) {

on_diam[u] = 1;

diam.push_back(u);

dis.push_back(dep[u]);

u = fa[u];

}

on_diam[epl] = 1;

}

int medium = -1;

// 寻找中点

for (int i = 0; i < diam.size(); i++) {

int u = diam[i];

if (dep[u] * 2 >= dep[epr] && dep[fa[u]] * 2 < dep[epr]) {

medium = i;

break;

}

}

memset(fa, 0, sizeof(fa));

memset(dep, 0, sizeof(dep));

// 寻找公共部分的上端点和下端点

int upper = diam.size(), lower = 0;

for (int i = medium; i < diam.size(); i++) {

int u = diam[i];

int t = dfs(u);

if (dep[t] == dis[i]) {

upper = i;

break;

}

}

for (int i = medium - 1; i >= 0; i--) {

int u = diam[i];

int t = dfs(u);

if (dep[t] == dis[0] - dis[i]) {

lower = i;

break;

}

}

printf("%lld\n", upper - lower);

return 0;

}

P1099 [NOIP 2007 提高组] 树网的核

概括一下题意。在一棵树上，定义路径的偏心距为所有点到路径距离的最大值，求一段长度不超过给定的 s 的路径，在直径上，且使偏心距最小。输出最小的偏心距。

如果只有一条直径，这题就好做了，但是一棵树可以有多条直径，直径的选择对答案会有影响吗？

考虑两条直径，我们选择了一条不在公共部分的路径（绿色 🟩 ）。

对于 🟩 的偏心距，它可能来自于蓝色 🟦 ，黄色 🟨 ，紫色 🟪 。

但是 🟪 真的有可能吗？如果 🟪 > 🟨 ，我们就可以导出矛盾，与直径冲突。

所以说 🟪 对这样的一条路径而言，对答案没有影响，也就是说，我们没有必要为了降低 🟪 的长度，而选择一条不包含公共部分的路径。

那我们先包含公共路径，然后向任意一个直径的端点延伸呢？

我们可以发现，对于 🟩 ，答案只会来自于 🟦 ， 🟪 ， 🟨 ，所以对往哪条直径去延伸没有影响，即我们在哪条直径上求解答案对答案没有影响。

那么我们求解的时候，只要任意求出一条直径就可以了。

然后我们开始想办法求解答案，虽然原题的数据范围很小，但是其实可以做到 O(n \log n) 的二分。

每次检查能否得到偏心距为 x 的路径，我们先从直径的两端向中点移动 x ，就可以得到一条路径满足到直径的两端 \le x，然后搜索到其他点的距离，判断是否满足 \le x 即可。

#include

using namespace std;

constexpr int N = 3e5 + 7;

struct E {

int v, w;

};

int n, s;

vector g[N];

int fa[N], dep[N];

bool selected[N];

// 找最远点

int dfs(int u) {

int rch = u;

for (E e : g[u]) {

int v = e.v;

int w = e.w;

if (v == fa[u] || selected[v]) {

continue;

}

fa[v] = u;

dep[v] = dep[u] + w;

int t = dfs(v);

if (dep[rch] < dep[t]) {

rch = t;

}

}

return rch;

}

vector diam, dis;

int epr, epl;

// 直径的两端

bool check(int x) {

int sr = 0, sl = 0;

// 被选的路径的两端

for (int i = 0; i < diam.size(); i++) {

if (dis[i] <= x) {

sr = i;

break;

}

}

for (int i = diam.size() - 1; i >= 0; i--) {

if (dis[0] - dis[i] <= x) {

sl = i;

break;

}

}

if (sr < sl) {

return 1;

}

if (dis[sl] - dis[sr] > s) {

return 0;

}

memset(selected, 0, sizeof(selected));

memset(fa, 0, sizeof(fa));

memset(dep, 0, sizeof(dep));

for (int i = sl; i <= sr; i++) {

int u = diam[i];

selected[u] = 1;

}

for (int i = sl; i <= sr; i++) {

int u = diam[i];

int v = dfs(u);

if (dep[v] > x) {

return 0;

}

}

return 1;

}

signed main() {

cin >> n >> s;

for (int i = 2; i <= n; i++) {

int u, v, w;

cin >> u >> v >> w;

g[u].push_back({v, w});

g[v].push_back({u, w});

}

epr = dfs(1);

fa[epr] = dep[epr] = 0;

epl = dfs(epr);

{

int u = epl;

while (1) {

diam.push_back(u);

dis.push_back(dep[u]);

if (u == epr) {

break;

}

u = fa[u];

}

}

int ans = -1;

{

int l = 0, r = dep[epl] - dep[epr];

while (l <= r) {

int mid = (l + r) >> 1;

if (check(mid)) {

ans = mid;

r = mid - 1;

} else {

l = mid + 1;

}

}

}

printf("%d\n", ans);

}

如果我们再进一步想一想，其实可以发现，使偏心距最小的路径其实就一定在直径上。不妨留作课后习题，读者自证不难 。

那么我们直接把上一题的代码复制一遍就可以通过 P2491 [SDOI2011] 消防。

总结

树的直径的性质有很多，不过理解起来并不难。一些题目需要自己推导性质，而且大多无法直接通过注意力得到。如果遇到与 “最长” 有关的树上的问题，不妨就想想与直径有没有关系。