题意：在基环树上找一点，使得这个点到所有点的距离最大值最小。这个点可以在某条边上。
解：很容易想到找出直径然后/2对吧...这里的直径是指任意两点间最短距离的最大值。
然而我这个SB冥思苦想了半天之后想到了一个傻逼绝伦的做法：枚举边！
这个点一定在某条边上。
所以知道边的两端点最长延伸多长即可。
如果是子树里的边，很显然下面那个点就是子树内最长链。而上面那个点就是子树外最长链或深度 + 根节点在环上最长延伸距离。
如果是环上的边，就是两端点子树最长链或者环上延伸的最长距离。
值得注意的是，这两个"环上最长延伸距离"并不是一样的。
因为前者只有一个点在环上，没有别的环上的点跟它竞争。
而后者要跟环上另一个点相互竞争。所以还要分两种情况。
具体实现上，首先找环，然后每个子树做两次树形DP，第二次是二次扫描与换根法。
然后把环的信息提取出来DP，利用单调队列来求最长延伸距离，反正我写了4个......
最后枚举边判定。
反正就是仔细写，耐心Debug...
(为什么别人1k就能A而我要5k啊...)
#include <cstdio>
#include <algorithm>
#include <stack>
#include <cstring> typedef long long LL;
const int N = ; struct Edge {
int nex, v;
LL len;
}edge[N << ]; int top = ; int e[N], n, cir[N], tc, p[N], head, tail, fr[N], nex[N], pre[N];
std::stack<int> S;
bool vis[N], is_cir[N];
LL d[N], len1[N], len2[N], lenup[N], dis[N], p2[N], sum[N], Long[N], Long_l[N], Long_r[N]; inline void add(int x, int y, LL z) {
top++;
edge[top].v = y;
edge[top].len = z;
edge[top].nex = e[x];
e[x] = top;
return;
} void Df(int x, int f) {
vis[x] = ;
S.push(x);
for(int i = e[x]; i && !vis[]; i = edge[i].nex) {
int y = edge[i].v;
if(y == f) {
continue;
}
if(vis[y]) {
vis[] = ;
while(x != y) {
x = S.top();
S.pop();
is_cir[x] = ;
cir[++tc] = x;
}
return;
}
Df(y, x);
}
if(vis[]) {
return;
}
S.pop();
vis[x] = ;
return;
} void DFS_1(int x, int f, int aim) { // get d len1 len2
if(!fr[x]) {
fr[x] = fr[f];
}
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == f || is_cir[y]) {
if(cir[aim] == y) {
dis[aim] = edge[i].len;
nex[x] = y;
pre[y] = x;
}
continue;
}
d[y] = d[x] + edge[i].len;
DFS_1(y, x, aim);
if(len1[x] < len1[y] + edge[i].len) {
len2[x] = len1[x];
len1[x] = len1[y] + edge[i].len;
}
else if(len2[x] < len1[y] + edge[i].len) {
len2[x] = len1[y] + edge[i].len;
}
}
return;
} void DFS_2(int x, int f) {
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == f || is_cir[y]) {
continue;
}
if(len1[y] + edge[i].len == len1[x]) {
lenup[y] = std::max(lenup[x], len2[x]) + edge[i].len;
}
else {
lenup[y] = std::max(lenup[x], len1[x]) + edge[i].len;
}
DFS_2(y, x);
}
return;
} int main() {
int x, y;
LL z, Sum = ;
double ans = ;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d%d%lld", &x, &y, &z);
add(x, y, z);
add(y, x, z);
ans += z;
}
Df(, ); for(int i = ; i <= tc; i++) {
fr[cir[i]] = cir[i];
DFS_1(cir[i], , (i == tc ? : i + ));
DFS_2(cir[i], );
cir[tc + i] = cir[i];
}
for(int i = ; i <= tc; i++) {
Sum += dis[i];
dis[tc + i] = dis[i];
}
for(int i = ; i <= tc * ; i++) {
sum[i] = sum[i - ] + dis[i];
} LL dt = ;
head = ;
tail = ;
for(int i = ; i <= tc * ; i++) {
// DP
while(head <= tail && sum[i] - sum[p[head]] > Sum - (sum[i] - sum[p[head]])) {
head++;
}
dt += dis[i];
if(head <= tail) {
Long[cir[i]] = std::max(Long[cir[i]], p2[head] + dt);
}
while(head <= tail && len1[cir[i]] - dt >= p2[tail]) {
tail--;
}
p[++tail] = i;
p2[tail] = len1[cir[i]] - dt;
}
head = ;
tail = ;
dt = ;
for(int i = tc * ; i >= ; i--) {
while(head <= tail && sum[p[head]] - sum[i] > Sum - (sum[p[head]] - sum[i])) {
head++;
}
dt += dis[i + ];
if(head <= tail) {
Long[cir[i]] = std::max(Long[cir[i]], p2[head] + dt);
}
while(head <= tail && len1[cir[i]] - dt >= p2[tail]) {
tail--;
}
p[++tail] = i;
p2[tail] = len1[cir[i]] - dt;
}
// -------------------------------------------------------------------------------------------------------
head = ;
tail = ;
dt = ;
dis[tc * + ] = dis[];
for(int i = ; i <= tc * ; i++) {
// DP
while(head <= tail && sum[i] - sum[p[head]] > Sum - (sum[i] - sum[p[head]] + dis[i + ])) {
head++;
}
dt += dis[i];
if(head <= tail) {
Long_l[cir[i]] = std::max(Long_l[cir[i]], p2[head] + dt);
}
while(head <= tail && len1[cir[i]] - dt >= p2[tail]) {
tail--;
}
p[++tail] = i;
p2[tail] = len1[cir[i]] - dt;
}
head = ;
tail = ;
dt = ;
for(int i = tc * ; i >= ; i--) {
while(head <= tail && sum[p[head]] - sum[i] > Sum - (sum[p[head]] - sum[i - ])) {
head++;
}
dt += dis[i + ];
if(head <= tail) {
Long_r[cir[i]] = std::max(Long_r[cir[i]], p2[head] + dt);
}
while(head <= tail && len1[cir[i]] - dt >= p2[tail]) {
tail--;
}
p[++tail] = i;
p2[tail] = len1[cir[i]] - dt;
}
//
for(int i = ; i <= top; i += ) {
int x = edge[i].v, y = edge[i ^ ].v;
LL a, b;
if(is_cir[x] && is_cir[y]) {
if(nex[y] == x) {
std::swap(x, y);
}
a = std::max(Long_l[x], len1[x]);
b = std::max(Long_r[y], len1[y]);
}
else {
if(d[x] > d[y]) {
std::swap(x, y);
}
a = len1[y];
b = std::max(lenup[y] - edge[i].len, d[x] + Long[fr[x]]);
}
if(a < b) {
std::swap(a, b);
}
if(a >= edge[i].len + b) {
ans = std::min(ans, (double)a);
}
else {
ans = std::min(ans, (a + b + edge[i].len) / 2.0);
}
} printf("%.1f", ans);
return ;
}
AC代码