嘟嘟嘟
要不这篇博客我水一下？
思路很显然，点分治+01分数规划+单调队列。
但就是难写。
点分治的时候我们把每一个点到重心这条链按深度排序，然后对于每一个点的链就有一个连续深度的区间可以和这条链拼上，因为要找一条权值大于(0)的链，那就相当于找这个区间的最大值。然后随着点深度递增，这个区间就不断向左移，就成了滑动窗口了。
细节就看shadowice1984的题解啦！
我写的时候没有把点分树建出来，只记录了重心序列，因为重心是按dfs序找的，所以只要每次用完后标记，就不会出问题，还省去了递归。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e6 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, LL, RR;
struct Edge
{
int nxt, to; ll w;
}e[maxn << 1];
int head[maxn], ecnt = -1;
In void addEdge(int x, int y, ll w)
{
e[++ecnt] = (Edge){head[x], y, w};
head[x] = ecnt;
}
int pos[maxn], pcnt = 0;
bool out[maxn];
int cg, Siz, siz[maxn], Max[maxn];
In void dfs0(int now, int _f, int& cg)
{
siz[now] = Max[now] = 1;
for(int i = head[now], v; ~i; i = e[i].nxt)
{
if((v = e[i].to) == _f || out[v]) continue;
dfs0(v, now, cg);
siz[now] += siz[v];
Max[now] = max(Max[now], siz[v]);
}
Max[now] = max(Max[now], Siz - siz[now]);
if(!cg || Max[cg] > Max[now]) cg = now;
}
In void dfs(int now)
{
cg = 0;
dfs0(now, 0, cg);
pos[++pcnt] = cg;
out[cg] = 1;
for(int i = head[cg], v; ~i; i = e[i].nxt)
if(!out[v = e[i].to]) Siz = siz[v], dfs(v);
}
struct Node
{
int id, val; db w;
In bool operator < (const Node& oth)const
{
return val < oth.val;
}
}t[maxn], q[maxn];
In void dfs_dep(int now, int _f, int dep, int& Max)
{
if(dep > Max) Max = dep;
for(int i = head[now], v; ~i; i = e[i].nxt)
if((v = e[i].to) != _f && !out[v]) dfs_dep(v, now, dep + 1, Max);
}
db b[maxn], dis[maxn], mid, ans;
In void dfs_dis(int now, int _f, int dep, db d)
{
dis[dep] = max(dis[dep], d);
for(int i = head[now], v; ~i; i = e[i].nxt)
if((v = e[i].to) != _f && !out[v]) dfs_dis(v, now, dep + 1, d + e[i].w - mid);
}
int L, R, hd, tl, tcnt = 0;
In void solve()
{
for(int id = 1; id <= pcnt; ++id)
{
tcnt = 0;
for(int i = head[pos[id]], v; ~i; i = e[i].nxt)
{
if(out[v = e[i].to]) continue;
int Max = 0;
dfs_dep(v, pos[id], 1, Max);
t[++tcnt] = (Node){v, Max, (db)e[i].w - mid};
}
sort(t + 1, t + tcnt + 1);
for(int i = 1; i <= t[tcnt].val; ++i) b[i] = -INF;
for(int i = 1; i <= tcnt; ++i)
{
for(int j = 1; j <= t[i].val; ++j) dis[j] = -INF;
dfs_dis(t[i].id, pos[id], 1, t[i].w);
if(i ^ 1)
{
L = max(1, LL - t[i].val), R = max(0, min(t[i - 1].val, RR - t[i].val)), hd = 1, tl = 0;
for(int j = L; j <= R; ++j)
{
while(hd <= tl && q[tl].w < b[j]) --tl;
q[++tl] = (Node){j, 0, b[j]};
}
for(int j = min(RR, t[i].val); j >= max(1, LL - t[i - 1].val); --j)
{
while(hd <= tl && q[hd].id + j < LL) ++hd;
if(R + 1 <= t[i - 1].val && R + 1 + j <= RR)
{
++R;
while(hd <= tl && q[tl].w < b[R]) --tl;
q[++tl] = (Node){R, 0, b[R]};
}
if(hd <= tl) ans = max(ans, q[hd].w + dis[j]);
if(ans > 0) return;
}
}
for(int j = 1; j <= t[i].val; ++j) b[j] = max(b[j], dis[j]);
}
out[pos[id]] = 1;
}
}
int main()
{
Mem(head, -1);
n = read(); LL = read(), RR = read();
for(int i = 1; i < n; ++i)
{
int x = read(), y = read(); ll w = read();
addEdge(x, y, w), addEdge(y, x, w);
}
Siz = n; dfs(1);
db L = 0, R = 1e6;
for(int t = 1; t <= 35; ++t)
{
mid = (L + R + eps) * 0.5;
ans = -INF; Mem(out, 0);
solve();
if(ans > eps) L = mid;
else R = mid - eps;
}
printf("%.3lf
", L);
return 0;
}
/*
8
2 4
1 2 3
1 4 4
3 2 4
3 5 6
6 2 9
6 8 2
2 7 4
*/