题目链接 Roads in the Kingdom
题意 给出一个环套树的结构,现在要删去这个结构中的一条边,满足所有点依然连通。
删边之后的这个结构是一棵树,求所有删边情况中树的直径的最小值。
显然能被删掉的边是环上的边。
首先预处理出这个环。环上的每一个点都是一棵树的根。
假设环上有$cnt$个点,首先我们要求出这$cnt$棵树的树的直径的最大值$ret$。
然后我们要求出这$cnt$棵树的最大深度$deep[i]$。
接下来我们就只考虑环上的点了。
设$fl[i]$为从环上的$1$号点开始往右走,走到$i$或之前的某一棵子树的路径长度最大值。
设$fr[i]$为从环上的$n$号点开始往左走,走到$i$或之后的某一棵子树的路径长度最大值。
设$cl[i]$为从左边开始往右走走到环上的第$i$的点停止不动的时候经过的路径长度最大值。
设$cr[i]$为从右边开始往左走走到环上的第$i$的点停止不动的时候经过的路径长度最大值。
设$gl[i]$为起点终点都在$i$点或之前能经过的路径长度最大值。(起点终点可能在某个子树中)
设$gr[i]$为起点终点都在$i$点或之后能经过的路径长度最大值。
做一遍$DP$即可。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define MP make_pair
#define fi first
#define se second typedef long long LL;
typedef pair <int, LL> PII; const int N = 2e5 + 10; vector <PII> v[N];
vector <int> c;
int isroot[N], a[N], father[N], vis[N], cnt = 0, n;
int cnt_node;
LL now_dis, ans, ret;
LL val[N], deep[N], pre[N], suc[N], fl[N], fr[N], cl[N], cr[N], gl[N], gr[N];
map <pair <int, int>, LL > mp; int get_circle(int x){
vis[x] = 1;
for (auto now : v[x]){
int u = now.fi;
if (u == father[x]) continue;
father[u] = x;
if (vis[u]){
cnt = 0;
int w = x;
while (w ^ u){
a[++cnt] = w;
isroot[w] = cnt;
w = father[w];
} a[++cnt] = u;
isroot[u] = cnt;
return 1;
} if (get_circle(u)) return 1;
} return 0;
} void dfs(int node, int x, int fa, LL dep){
if (dep > deep[node]){
cnt_node = x;
deep[node] = dep;
} for (auto now : v[x]){
int u = now.fi;
if (u == fa) continue;
if (isroot[u]) continue;
dfs(node, u, x, dep + now.se);
}
} void dfs2(int x, int fa, int extra, LL dep){
now_dis = max(now_dis, dep);
for (auto now : v[x]){
int u = now.fi;
if ((u == fa) || (isroot[u] && u != extra)) continue;
dfs2(u, x, extra, dep + now.se);
}
} int main(){ scanf("%d", &n);
rep(i, 1, n){
int x, y;
LL z;
scanf("%d%d%lld", &x, &y, &z);
v[x].push_back(MP(y, z));
v[y].push_back(MP(x, z));
mp[MP(x, y)] = mp[MP(y, x)] = z;
} father[1] = 0;
get_circle(1); rep(i, 1, cnt){
cnt_node = 0;
dfs(i, a[i], 0, 0);
if (deep[i] > 0){
now_dis = 0;
dfs2(cnt_node, 0, a[i], 0);
ret = max(ret, now_dis);
}
} val[0] = mp[MP(a[1], a[cnt])];
rep(i, 1, cnt - 1) val[i] = mp[MP(a[i], a[i + 1])]; pre[1] = 0; rep(i, 2, cnt) pre[i] = pre[i - 1] + val[i - 1];
suc[cnt] = 0; dec(i, cnt - 1, 1) suc[i] = suc[i + 1] + val[i]; fl[1] = deep[1]; rep(i, 2, n) fl[i] = max(fl[i - 1], pre[i] + deep[i]);
fr[cnt] = deep[cnt]; dec(i, n - 1, 1) fr[i] = max(fr[i + 1], suc[i] + deep[i]); cl[1] = 0; cl[2] = deep[1] + val[1];
rep(i, 3, cnt) cl[i] = max(cl[i - 1], deep[i - 1]) + val[i - 1];
cr[cnt] = 0, cr[cnt - 1] = deep[cnt] + val[cnt - 1];
dec(i, cnt - 2, 1) cr[i] = max(cr[i + 1], deep[i + 1]) + val[i]; rep(i, 2, cnt) gl[i] = max(gl[i - 1], cl[i] + deep[i]);
dec(i, cnt - 1, 1) gr[i] = max(gr[i + 1], cr[i] + deep[i]); ans = gl[cnt];
rep(i, 1, cnt - 1) ans = min(ans, max(fl[i] + fr[i + 1] + val[0], max(gl[i], gr[i + 1]))); ans = max(ans, ret);
printf("%lld\n", ans);
return 0;
}