树的直径

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<int> 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<d[v]+1) {
            sec=fst;
            fst=d[v]+1;
        } else if(sec<d[v]+1) {
            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<int> 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<t.l) {
            sec=fst;
            fst=t;
        } else if(sec.l<t.l) {
            sec=t;
        }
    }
    if(diam.l<fst.l+sec.l){
        diam={fst.l+sec.l,fst.u,sec.u};
    }
    d[u]=fst;
}

直径的性质

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

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

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

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

我们假设，这个图的直径是 (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 <bits/stdc++.h>
using namespace std;

constexpr int N = 1e6 + 7;

int n;
vector<int> 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 <bits/stdc++.h>
using namespace std;

#define int long long

constexpr int N = 2e5 + 7;

struct E {
    int v, w;
};

int n;
vector<E> 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<int> 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 <bits/stdc++.h>
using namespace std;

constexpr int N = 3e5 + 7;

struct E {
    int v, w;
};

int n, s;
vector<E> 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<int> 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] 消防。

总结

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