原题传送门

---

题意

给定一个n条边n个点的连通图，求该图的某一点在该图距离最远的点距离它的距离的最小值。

---

题解

显然，答案是\(\frac {原图直径}{2}\)。

本体的图有 \(n\) 个点 \(n\) 条边，很显然是基环树。

那么拆掉任意一条环上的边，该图就会变为一颗普通树。

随意选择一条环上的边断开，设一端为 \(s\)，一端为 \(t\)， 长度为 \(len\)。

分类讨论一下该图的直径经过环和断边的情况：

1、直径经过断开的边；

2、直径不经过断开的边，经过环；

3、直径不经过环。

显然，若直径经过断开的边，就需要得出环上每个点的字数距离 \(s\) 最远点距离 \(s\) 的值，此值很显然可以在环上跑一边 \(DP\) 求出；

若直径不经过断开的边，则需要得出环上某两个点的子树的最远点之间的距离的最大值，此值仍然可以在环上跑一边 \(DP\) 求出。

故我们可以从 \(s\) 点开始，\(O(n)\) 从两个方向扫两遍环，在扫环的过程中，求出直径不经过环的情况的答案，同时维护两个 \(DP\) 值：

1、经过的环上的点的子树中，距离 \(s\) 最远的点距离 \(s\) 的值，定义该值为 \(u_1\)（正向）和 \(u_2\)（反向）；

2、在经过的环上的点中，某两个距离最远的子树的最远点之间的距离，定义该值为 \(v_1\)（正向）和 \(v_2\)（反向）；

扫描结束后，再遍历一遍环上的点更新答案值。

\(DP\) 方程：

\(ans = min(ans, max (max (v_1[i], v_2[i + 1]), u_1[i] + u_2[i + 1] + len))\)

注意更新结束后，还需要与直径不经过环的情况求一下最值。

---

代码：

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 5;

int n, sum, mx, cirsum, ans, ans1, tim, lstlen, f[N], u1[N], u2[N], v1[N], v2[N], fa[N], fal[N], tims[N], oncir[N], cirnum[N], cirlen[N];

vector <pair <int, int> > v[N];

void make_cir (int s, int t) {

	int now = s;

	while (now != t) {

		oncir[now] = 1;

		cirnum[++ cirsum] = now;

		cirlen[cirsum] = fal[now];

		now = fa[now];

	}

	return ;

}

void dfs (int x) {

	tims[x] = ++ tim;

	for (int i = 0; i < v[x].size (); i ++) {

		int y = v[x][i].first;

		if (tims[y] && tims[y] > tims[x]) {

			make_cir (y, x);

			oncir[x] = 1;

			cirnum[++ cirsum] = x;

			cirlen[cirsum] = v[x][i].second;

		} else if (!tims[y]) {

			fa[y] = x;

			fal[y] = v[x][i].second;

			dfs (y);

		}

	}

	return ;

}

void dfs2 (int x, int lst) {

	for (int i = 0; i < v[x].size(); i ++) {

		int y = v[x][i].first, w = v[x][i].second;

		if (y == lst || oncir[y])

			continue ;

		dfs2 (y, x);

		ans = max (ans, f[x] + f[y] + w);

		f[x] = max (f[x], f[y] + w);

	}

	return ;

}

signed main () {

	scanf ("%lld", &n);

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

		int uu, vv, ww;

		scanf ("%lld%lld%lld", &uu, &vv, &ww);

		v[uu].push_back (make_pair (vv, ww));

		v[vv].push_back (make_pair (uu, ww));

	}

	dfs (1);

	for (int i = 1; i <= cirsum; i ++)

		dfs2 (cirnum[i], 0);

	for (int i = 1; i <= cirsum; i ++) {

		sum += cirlen[i - 1];

		u1[i] = max (u1[i - 1], f[cirnum[i]] + sum);

		v1[i] = max (v1[i - 1], f[cirnum[i]] + mx + sum);

		mx = max (mx, f[cirnum[i]] - sum);

	}

	lstlen = cirlen[cirsum];

	cirlen[cirsum] = 0;

	sum = 0;

	mx = 0;

	for (int i = cirsum; i >= 1; i --) {

		sum += cirlen[i];

		u2[i] = max (u2[i + 1], f[cirnum[i]] + sum);

		v2[i] = max (v2[i + 1], f[cirnum[i]] + mx + sum);

		mx = max (mx, f[cirnum[i]] - sum);

	}

	ans1 = v1[cirsum];

	for (int i = 1; i < cirsum; i ++)

		ans1 = min (ans1, max (max (v1[i], v2[i + 1]), u1[i] + u2[i + 1] + lstlen));

	ans = max (ans, ans1);

	printf ("%.1lf\n", (double)(ans / 2));

	return 0;

}

本博客思路参考自 https://blog.csdn.net/zlttttt/article/details/73149529