题目链接
洛谷
BZOJ(没有题面，有数据)
解析
删掉一条边后原树变成两棵树，再连一条边后新树的直径一定不小于这两棵树的直径
考虑再新增一条边，要想新树直径最小，一定是将两树的“中心”相连，经过这条连边的最长路径为两树半径之和加上这条边的长度
枚举修改哪条边，求出断开这条边后两棵树的直径和半径即可统计答案
计算直径一遍\(dp\)，同时处理出每个点\(u\)代表的子树中到该点的最长链\(maxd[u]\)和次长链\(maxd2[u]\)
计算半径再一遍\(dfs\)，记录从子树外到该点的最长链\(up\)，将\(max(maxd[u], up)\)和当前半径取个\(min\)，到儿子的\(up\)为\(max(up, maxd[u])+edge.cost\)，但注意当最长链经过该儿子时要换成次长链
复杂度\(O(n^2)\)，\(5000\)的数据+\(3s\)的时限，常数小点，比如不要\(vector\)存边(说的就是我)，可以过
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define getv(x, y) (edge[y].u == x ? edge[y].v : edge[y].u)
#define MAXN 5005typedef long long LL;
const int inf = 0x3f3f3f3f;
struct Edge {int v, next, cost;Edge(int _v = 0, int _n = 0, int _c = 0):v(_v), next(_n), cost(_c) {}
} edge[MAXN << 1];
int N, ans = 0x3f3f3f3f;
int dist[MAXN], maxd[MAXN], maxd2[MAXN], head[MAXN], cnt, x[MAXN], y[MAXN], c[MAXN];
char vis[MAXN];void calc(int, int &, int &);
void dfs(int, int &);
void dfs2(int, int &, int);
void add_edge(int, int, int);
char gc();
int read();
int main() {memset(head, -1, sizeof head);N = read();for (int i = 1; i < N; ++i) {x[i] = read(), y[i] = read(), c[i] = read();add_edge(x[i], y[i], c[i]);add_edge(y[i], x[i], c[i]);}for (int i = 1; i < N; ++i) {int d1 = 0, r1 = inf, d2 = 0, r2 = inf;vis[y[i]] = 1;calc(x[i], d1, r1);vis[x[i]] = 1, vis[y[i]] = 0;calc(y[i], d2, r2);vis[x[i]] = 0;ans = std::min(ans, std::max(std::max(d1, d2), r1 + r2 + c[i]));}printf("%d\n", ans);return 0;
}
void calc(int rt, int &d, int &r) {dist[rt] = 0;dfs(rt, d);dfs2(rt, r, 0);
}
void dfs(int u, int &d) {maxd[u] = 0, maxd2[u] = -inf;vis[u] = 1;for (int i = head[u]; ~i; i = edge[i].next) {const Edge &e = edge[i];if (vis[e.v]) continue;dist[e.v] = dist[u] + e.cost;dfs(e.v, d);int tmp = maxd[e.v] + e.cost;if (tmp > maxd[u]) maxd2[u] = maxd[u], maxd[u] = tmp;else if (tmp > maxd2[u]) maxd2[u] = tmp;}vis[u] = 0;d = std::max(d, maxd[u] + maxd2[u]);
}
inline char gc() {static char buf[1000000], *p1, *p2;if (p1 == p2) p1 = (p2 = buf) + fread(buf, 1, 1000000, stdin);return p1 == p2 ? EOF : *p2++;
}
inline int read() {int res = 0; char ch = gc();while (ch < '0' || ch > '9') ch = gc();while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + ch - '0', ch = gc();return res;
}
void dfs2(int u, int &r, int up) {vis[u] = 1;r = std::min(r, std::max(up, maxd[u]));for (int i = head[u]; ~i; i = edge[i].next) {const Edge &e = edge[i];if (vis[e.v]) continue;if (maxd[u] == maxd[e.v] + e.cost) dfs2(e.v, r, std::max(up, maxd2[u]) + e.cost);else dfs2(e.v, r, std::max(up, maxd[u]) + e.cost);}vis[u] = 0;
}
inline void add_edge(int u, int v, int c) { edge[cnt] = Edge(v, head[u], c), head[u] = cnt++; }
//Rhein_E
