环球速讯：AcWing. 1072 树的最长路径

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

环球速讯：AcWing. 1072 树的最长路径

2023-01-16 16:15:42 来源：博客园

题目描述

给定一棵树，树中包含 $n$ 个结点（编号$1$~$n$）和 $n-1$ 条无向边，每条边都有一个权值。

现在请你找到树中的一条最长路径。

(资料图)

换句话说，要找到一条路径，使得使得路径两端的点的距离最远。

注意：路径中可以只包含一个点。

解题思路

$\qquad$首先因为是树所以有这样的一个性质：树上两点之间有且仅有一条路径，路径$(x,y)$可以拆分成两条路径 $(x,r)$ 和 $(r,y)$，其中 $r$ 表示 $LCA(x, y)$。

$\qquad$所以我们可以得到一个思路：枚举断点 $r$，状态 $dist[r]$ 表示 $r$ 的子树中，与 $r$ 距离最远的点的距离。对于 $r$ 的所有子节点 $x_1, x_2, x_3,......x_k$，有

\[\Large dist[r] = \max_{1\le i\le k}\{ dist[x_i] + w(r,x_i)\}\]

$\qquad$ 然后再定义 $f[x]$ 为以 $x$ 为断点的最长链，那么树的直径就是

\[\Large \max_{1\le x\le n}\{f[x]\}\]

求$f$的过程如下图所示对于 $x$ 的任意两个子节点 $y_i$ 和 $y_j$，$f[x]$ 可以分成下面四个部分的和$\qquad 1.$ 从 $y_i$ 到 $y_i$ 的子树的最大距离$\qquad 2.$ 从 $y_i$ 到 $x$ 的距离$\qquad 3.$ 从 $x$ 到 $y_j$ 的距离$\qquad 4.$ 从 $y_j$ 到 $y_j$ 子树的最大距离因此$$\large f[x] = \max_{1\le j

然后就OK了

优化

如果我么顺序枚举，那么在将要枚举到 $i$ 的时候，对于每个已经枚举过的节点 $j < i$ 我们都可以保存到从 $x$ 出发走向以 $y_j$ 为根的子树最大距离，这个距离也就是

\[\large \max_{1\le j < i}\{dist[y_j] + w(x,y_j)\}\]

所以我们可以一边枚举一边用$dist[x] + dist[y_i] + w(x, y_i)$ 更新 $f[x]$，一边用$dist[y_i] + w(x, y_i)$ 更新 $ dist[x]$。

代码

#include #include #include using namespace std;const int N = 10010, M = N << 1;int h[N], e[M], w[M], ne[M], idx = 1;bool st[N]; int n, dist[M], res = -0x3f3f3f;void add(int a, int b, int c){    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;}void dp(int x){    st[x] = true;    for (int i = h[x]; ~i; i = ne[i])     {        int j = e[i];        if (st[j]) continue ;        dp(j);        res = max(res, dist[x] + dist[j] + w[i]);        dist[x] = max(dist[x], dist[j] + w[i]);    }    res = max(res, dist[x]);}int main(){    memset(h, -1, sizeof h);    scanf("%d", &n);    while (n -- )     {        int u, v, w;        scanf("%d%d%d", &u, &v, &w);        add(u, v, w), add(v, u, w);    }    dp(1);    printf("%d\n", res);    return 0;}

关键词：最大距离如下图所示有且仅有