现在改了优化 90 了：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const double INF=1e9,eps=1e-6;
int n,L,U,sz[N],mx[N],len[N],deq[N],q[N],vis[N],viss[N],top,last,flag,rt,sum,cnt,G[N];
vector<pair<int,double> >v[N];
double dis[N],f[N];
void getrt(int u,int faa)
{
sz[u]=1;mx[u]=0;
for(auto t:v[u])
{
if(t.first==faa||vis[t.first])continue;
getrt(t.first,u);
sz[u]+=sz[t.first];
mx[u]=max(mx[u],sz[t.first]);
}
mx[u]=max(mx[u],sum-sz[u]);
if(mx[u]<mx[rt])rt=u;
return;
}
void bfs(int src)
{
viss[q[++top]=src]=1;
for(int i=last+1;i<=top;i++)
{
int u=q[i];
for(auto t:v[u])
{
if(vis[t.first]||viss[t.first])continue;
dis[t.first]=dis[u]+t.second;
len[t.first]=len[u]+1;
viss[q[++top]=t.first]=1;
}
}
for(int i=last+1;i<=top;i++)viss[q[i]]=0;
return;
}
void check()
{
int h=1,t=0,tip=last+1;
for(int i=min(U,len[q[top]]);i;i--)
{
int tl=i>=L?0:L-i,tr=U-i;
while(h<=t&&len[deq[h]]<tl)++h;
while(tip<=top&&len[q[tip]]<tl)++tip;
while(tip<=top&&len[q[tip]]<=tr)
{
while(h<=t&&dis[deq[t]]+eps<=dis[q[tip]])--t;
deq[++t]=q[tip++];
}
if(h<=t&&f[i]+dis[deq[h]]>=-eps)
{
flag=1;
return;
}
}
}
void calc(int u)
{
f[0]=dis[u]=len[u]=0;top=0;
q[0]=u;
for(auto t:v[u])
{
if(vis[t.first])continue;
dis[t.first]=t.second;
len[t.first]=1;
last=top;
bfs(t.first);
check();
for(int i=last+1;i<=top;i++)
f[len[q[i]]]=max(f[len[q[i]]],dis[q[i]]);
}
for(int i=0;i<=top;i++)f[len[q[i]]]=-INF;
return;
}
void solve()
{
int u=G[++cnt];
vis[u]=1;calc(u);
for(auto t:v[u])
{
if(!vis[t.first])
solve();
}
vis[u]=0;
return;
}
bool check(double mid)
{
// memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++)
for(auto &t:v[i])t.second-=mid;
flag=0;cnt=0;
solve();
for(int i=1;i<=n;i++)
for(auto &t:v[i])t.second+=mid;
return flag;
}
void init(int u)
{
mx[rt=0]=INF;
getrt(u,0);
G[++cnt]=rt;
vis[rt]=1;
int x=rt;
for(auto t:v[rt])
{
if(!vis[t.first])sum=sz[t.first],init(t.first);
}
vis[x]=0;
return;
}
int main()
{
clock_t c1=clock();
#ifdef LOCAL
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>L>>U;
double l=0,r=0;
for(int i=1;i<=n-1;i++)
{
int a,b,c;
cin>>a>>b>>c;
r+=c;
v[a].push_back(make_pair(b,c));
v[b].push_back(make_pair(a,c));
f[i]=-INF;
}
// sz[1]=n;
sum=n;
init(1);
while(l<=r-eps)
{
double mid=(l+r)/2.0;
if(check(mid))l=mid;
else r=mid-eps;
}
printf("%.3lf",l);
#ifdef LOCAL
cerr<<"Time used:"<<clock()-c1<<"ms";
#endif
return 0;
}
```
by AAA404 @ 2024-02-04 20:17:09
@[AAA404](/user/723198) 你考虑加几个剪枝，我几个月前写这题时也被卡了，加个剪枝就过了。具体的我不记得了。
by Saka_Noa @ 2024-02-04 20:20:32
```cpp
void dfs(int u, int Fa, long double len)
{
de[u] = de[Fa] + 1;
if (g[de[u] - 1] <= len) // this
{
g[de[u] - 1] = len;
id_g[de[u] - 1] = u;
}
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if (v == Fa || vis[v])
continue;
dfs(v, u, len + (e[i].w - Check_X));
}
}
```
我好像是加了这个
by Saka_Noa @ 2024-02-04 20:24:07
好像不是，我再看看。
by Saka_Noa @ 2024-02-04 20:25:01
@[Saka_Noa](/user/498612) 精度改成 1e-4 就过了....难蚌
by AAA404 @ 2024-02-04 20:25:11
此帖终
by AAA404 @ 2024-02-04 20:25:25
@[AAA404](/user/723198)
```cpp
void solve(int u)
{
vis[u] = 1;
calc(u);
if (ans >= 0)
return;
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if (vis[v])
continue;
root = de[u] = de[v] = 0;
sum = si[v];
if (si[v] < in_l) //this
continue;
get_core(v, 0);
pre_dfs(root, 0);
//if (dep[root] < in_l)
// return;
solve(root);
}
}
```
想起来了
by Saka_Noa @ 2024-02-04 20:28:38
@[Saka_Noa](/user/498612) `in_l` 是什么
by AAA404 @ 2024-02-04 20:30:47
@[AAA404](/user/723198) 题目输入边界 `l`
by Saka_Noa @ 2024-02-04 20:32:26
@[AAA404](/user/723198) 可以优化我写的点分治 $0.5s$ 左右。
by Saka_Noa @ 2024-02-04 20:37:35