题面：Roads in the Kingdom

题面翻译

题目描述

王国有 $n$ 座城市与 $n$ 条有长度的街道，保证所有城市直接或间接联通，我们定义王国的直径为所有点对最短距离中的最大值，现因财政危机需拆除一条道路并同时要求所有城市仍然联通，求所有拆除方案中王国直径的最小值。

输入格式

第一行一个整数 $n$，接下来 $n$ 行每行三个整数 $u,v,w$ 表示城市 $u,v$ 之间有一条长度为 $w$ 的道路。

输出格式

一行一个答案，表示所有方案中直径最小值。

题目描述

In the Kingdom K., there are $ n $ towns numbered with integers from $ 1 $ to $ n $ . The towns are connected by $ n $ bi-directional roads numbered with integers from $ 1 $ to $ n $ . The $ i $ -th road connects the towns $ u_{i} $ and $ v_{i} $ and its length is $ l_{i} $ . There is no more than one road between two towns. Also, there are no roads that connect the towns with itself.

Let’s call the inconvenience of the roads the maximum of the shortest distances between all pairs of towns.

Because of lack of money, it was decided to close down one of the roads so that after its removal it is still possible to reach any town from any other. You have to find the minimum possible inconvenience of the roads after closing down one of the roads.

输入格式

The first line contains the integer $ n $ ( $ 3<=n<=2·10^{5} $ ) — the number of towns and roads.

The next $ n $ lines contain the roads description. The $ i $ -th from these lines contains three integers $ u_{i} $ , $ v_{i} $ , $ l_{i} $ ( $ 1<=u_{i},v_{i}<=n $ , $ 1<=l_{i}<=10^{9} $ ) — the numbers of towns connected by the $ i $ -th road and the length of the $ i $ -th road. No road connects a town to itself, no two roads connect the same towns.

It’s guaranteed that it’s always possible to close down one of the roads so that all the towns are still reachable from each other.

输出格式

Print a single integer — the minimum possible inconvenience of the roads after the refusal from one of the roads.

样例 #1

样例输入 #1

1
2
3
4
3
1 2 4
2 3 5
1 3 1

样例输出 #1

1
5

样例 #2

样例输入 #2

1
2
3
4
5
6
5
2 3 7
3 1 9
4 1 8
3 5 4
4 5 5

样例输出 #2

1
18

思路

首先，简化题意。题目让我们求的是：删除一棵基环树的环上一边后树的直径的最小值

那么首先我们要知道正常的基环树求直径怎么做，出门右转：

友情链接：

【算法介绍】基环树 | 祝馀宫

那么如果已经知道了基本的基环树求直径，这道题也不算什么了。首先达成了一个共识，这道题的数据范围我们不可能模拟删掉哪条边然后每次计算直径。那么肯定是要像正常的基环树求直径一样得到了什么结果导致我们可以这样搞出来。

继承了基环树求直径的思路，我们应该也是先把每一个点向外扩展的最长路给求出来，那么这时候对于一个断掉的边（假设断掉的边是 $\operatorname{Cir}[i] \rightarrow \operatorname{Cir}[i+1]$），我们会有两种可能：

  1. 过环直径（注意是过环，没过环的直径已经在求最远拓展路的时候算过了）的入环点还有出环点属于区间 $[1,i]$
  2. 过环直径的入环点还有出环点属于 $[i+1,n]$
  3. 过环直径它绕了一圈，也就是一个点在 $[1,i]$ 另一个在 $[i+1,n]$

然后，我们就要根据这几种情况来分类讨论设计代码了。

  1. 第一种情况：如果我么设 $\operatorname{L0}[i]$ 表示出入环节点为 $[1,i]$ 内部点的过环直径最大值。其实准确点来讲，应该是过环最长链，但是写着写着习惯了，就叫过环直径罢

    那么我们其实不难注意到这就是一道很普通的递推。我们不难发现，这个的答案就是 $w[i]+w[j] + \operatorname{dis}(i,j)$ 这时候就简单了，其实和求直径的时候一模一样。把它变成 $w[i]-dis[i]+w[j]+dis[j]$ 然后维护 $w[j]+dis[j]$ 的最大值即可。

  2. 第二种情况：和第一种情况如出一辙。只不过这次变成了右端点 $n$ 是定点，左端点 $i+1$ 是动点，所以说这时候我们需要从右往左递推，然后维护的得是 $w[i]-dis[i]$ 的最大值，这个为什么就不用说了罢

  3. 第三种情况：这个的话其实说复杂也复杂，说简单的话也真简单。他维护的就是分两段，前一段 $[1,i]$ 和后一段 $[i+1,n]$ 。前一段还是一样的递推，后一段有一个不一样的地方，因为最后要绕一圈，所以要比前一段多加上一个环的小段部分。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

template<int N, int M>
class Graph {
    private :
        struct Edge {
            int to, nt, wt;
            Edge() {}
            Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void clear() { memset(hd, 0, sizeof(hd)), cnte = 0; }
        inline void AddEdge(int u, int v, int w = 0) {
            e[++cnte] = Edge(v, hd[u], w);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline int wt(int u) { return e[u].wt; }
};

const int MaxV = 2e5 + 10;
const int MaxE = 4e5 + 10;

int n;
Graph< MaxV, MaxE >G;

inline void Input() {
    read(n); int u, v, w;
    for(int i = 1; i <= n; i++) {
        read(u, v, w);
        G.AddEdge(u, v, w);
        G.AddEdge(v, u, w);
    }
}

int vis[MaxV];
int Cir[MaxV], tot;
ll dis[MaxV];

int GetCircle(int u, int fa = -1) {
    if(vis[u]) return u;
    else vis[u] = -1;
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i), now = GetCircle(v, u);
        if(v != fa && now) {
            Cir[++tot] = u, dis[tot] = G.wt(i);
            vis[u] = 1;
            return now == u ? 0 : now;
        }
    }
    return 0;
}

ll ans1, ans2, dp[MaxV];

void Dfs(int u, int fa = -1) {
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(vis[v] != 1 && v != fa) {
            Dfs(v, u);
            ans1 = max(ans1, dp[u] + dp[v] + G.wt(i));
            dp[u] = max(dp[u], dp[v] + G.wt(i));
        }
    }
}

ll l[MaxV], l0[MaxV];
ll r[MaxV], r0[MaxV];

inline void CalcCircle() {
    ll res = -1e18;
    l[0] = l0[0] = -1e18;
    for(int i = 1; i <= tot; i++) {
        l0[i] = max(l0[i - 1], dp[Cir[i]] + dis[i] + res);
        l[i] = max(l[i - 1], dp[Cir[i]] + dis[i]);
        res = max(res, dp[Cir[i]] - dis[i]);
        // cout << l0[i] << ' ' << l[i] << endl;
    }
    res = r[tot + 1] = r0[tot + 1] = -1e18;
    for(int i = tot; i >= 1; i--) {
        r0[i] = max(r0[i + 1], dp[Cir[i]] - dis[i] + res);
        r[i] = max(r[i + 1], dp[Cir[i]] + dis[tot] - dis[i]);
        res = max(res, dp[Cir[i]] + dis[i]);
        // cout << r0[i] << ' ' << r[i] << endl;
    }
    ans2 = 1e18;
    for(int i = 1; i <= tot; i++) {
        ans2 = min(ans2, max(l[i - 1] + r[i], max(l0[i - 1], r0[i])));
        // cout << ans2 << ' ';
    }
    // cout << endl;
}

inline void Work() {
    GetCircle(1);
    dis[0] = 0;
    for(int i = 1; i <= tot; i++) {
        Dfs(Cir[i]); 
        dis[i] += dis[i - 1];
    }
    CalcCircle();
    printf("%lld\n", max(ans1, ans2));
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}