<div class="post_brief"><p>
好吧我的本意是想学习一下dp的。然后发现了这道纠结了一年半还多的题。</p>

 

首先把环找出来。然后环上会长一些树。先把树的答案求了，因为它很好求。

 

然后考虑环，那么答案应该是随便断一条边之后答案的最小值（而不是最大值）。于是乎记录一下每个点按某个方向到起点的距离，记为d[i]。算一下每个点的树的深度，记为l[i]。于是每次要最大化l[i]+l[j]+|d[i]-d[j]|。反正是最大化所以顺序是没有关系的，但是不能自交。这是个比较容易错的地方。于是就去写个线段树来维护吧。只查询不修改让我总有能线性搞的想法，虽然没想清楚具体怎么实现。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;


struct edge {
int t, v;
edge *next;
};


typedef long long dint;
#ifdef WIN32
#define lld “%I64d”
#else
#define lld “%lld”
#endif
#define _l (long long int)


const int maxn = 100009;


edge elst[maxn << 1], *ep(elst), *head[maxn];
int n, fa[maxn], df[maxn], ol[maxn], d[maxn];
int tlp, lp[maxn << 1];
dint lv[maxn << 1], le[maxn << 1], md[maxn], ans;


inline void addEdge(int u, int v, int w) {
ep-> t = v;
ep-> v = w;
ep-> next = head[u];
head[u] = ep ++;
}


void findLoop() {
static int q[maxn];
int hd(0), tl(1);
int uo(0), vo(0), dx, a;
q[0] = 1;
fa[1] = -1;
d[1] = 1;
memset(ol, 0, sizeof(ol));
memset(fa, 0, sizeof(fa));
while (hd < tl && !uo) {
int p(q[hd ++]);
for (edge* e = head[p]; e; e = e-> next)
if (e-> t ^ fa[p]) {
if (fa[e-> t]) {
uo = p;
vo = e-> t;
dx = e-> v;
break;
}
else {
d[e-> t] = d[p] + 1;
fa[e-> t] = p;
df[e-> t] = e-> v;
q[tl ++] = e-> t;
}
}
}
tlp = 0;
for (int u = uo, v = vo; u ^ v; ++ tlp)
if (d[u] > d[v])
a = u = fa[u];
else
a = v = fa[v];
++ tlp;
for (int u = uo, v = vo; u ^ v; )
if (d[u] > d[v]) {
int i(d[uo] - d[u]);
lp[i] = u;
le[i] = df[u];
u = fa[u];
}
else {
int i(tlp - d[vo] + d[v] - 1);
lp[i] = v;
le[i - 1] = df[v];
v = fa[v];
}
lp[d[uo] - d[a]] = a;
le[tlp - 1] = dx;
for (int i = 0; i < tlp; ++ i)
ol[lp[i]] = 1;
}


void dpTree(int p0) {
static int q[maxn];
int hd(0), tl(1);
q[0] = p0;
while (hd < tl) {
int p(q[hd ++]);
for (edge* e = head[p]; e; e = e-> next)
if (!ol[e-> t]) {
ol[e-> t] = ol[p] + 1;
q[tl ++] = e-> t;
}
}
for (int i = tl - 1; i >= 0; – i) {
int p(q[i]);
dint s2(0);
md[p] = 0;
for (edge* e = head[p]; e; e = e-> next)
if (ol[e-> t] == ol[p] + 1) {
dint v(md[e-> t] + e-> v);
if (v > md[p]) {
s2 = md[p];
md[p] = v;
}
else if (v > s2)
s2 = v;
}
if (md[p] + s2 > ans)
ans = md[p] + s2;
}
}


struct dat {
dint x, y, s;
dat() {}
dat(dint x0, dint y0) {
x = x0, y = y0, s = 0;
}
dat(dat a, dat b) {
s = max(max(a. s, b. s), a. x + b. y);
x = max(a. x, b. x);
y = max(a. y, b. y);
}
};
struct seg {
int l, r;
dat d;
seg *ls, *rs;
};
seg slst[maxn * 5], *sp(slst), *rt;


#define midp(p) ((p->l+p->r)>>1)
inline seg* sgtBuild(int l, int r) {
seg p(sp ++);
p-> l = l;
p-> r = r;
if (l + 1 == r) {
p-> d = dat(lv[l] + le[l], lv[l] - le[l]);
}
else {
p-> ls = sgtBuild(l, midp(p));
p-> rs = sgtBuild(midp(p), r);
p-> d = dat(p-> ls-> d, p-> rs-> d);
}
return p;
}
inline dat sgtQry(seg p, int l, int r) {
if (p-> l == l && p-> r == r)
return p-> d;
else if (r <= midp(p))
return sgtQry(p-> ls, l, r);
else if (l >= midp(p))
return sgtQry(p-> rs, l, r);
else
return dat(sgtQry(p-> ls, l, midp(p)), sgtQry(p-> rs, midp(p), r));
}


void dpLoop() {
dint totl(0);
for (int i = 0; i < tlp; ++ i) {
lv[i + tlp] = lv[i];
le[i + tlp] = le[i];
lp[i + tlp] = lp[i];
totl += le[i];
}
le[tlp * 2] = 0;
for (int i = tlp * 2 - 1; i >= 0; – i)
le[i] += le[i + 1];
rt = sgtBuild(0, tlp * 2);
dint cans(0x7fffffffffffffffll);
for (int i = 0; i < tlp; ++ i) {
cans = min(cans, sgtQry(rt, i, i + tlp). s);
}
ans = max(ans, cans);
}


int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif


scanf("%d", &amp;n);
memset(head, 0, sizeof(head));
for (int i = 0; i &lt; n; ++ i) {
	int u, v, w;
	scanf("%d%d%d", &amp;u, &amp;v, &amp;w);
	addEdge(u, v, w);
	addEdge(v, u, w);
}
findLoop();
ans = 0;
for (int i = 0; i &lt; tlp; ++ i) {
	dpTree(lp[i]);
	lv[i] = md[lp[i]];
}
dpLoop();
printf("%.1lf\n", (double)ans / 2.0);



}