1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140
| #include<vector> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
inline int rin(int &r){ int b=1,c=getchar();r=0; while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar(); while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar(); return r*=b; } const int N=1e5+10; #define con(type) const type & const double EPS=1e-8; typedef pair<int,int> pii;
struct SuperDeque{ int ary[N],le,ri; void clear(){le=1,ri=0;} void push_back(con(int)x){ary[++ri]=x;} void pop_back(){ri--;} void pop_front(){le++;} int back(){return ary[ri];} int front(){return ary[le];} int size(){return ri-le+1;} }que;
int n,bonl,bonr,rsiz,rwei,rroot; int siz[N],hgt[N]; double val_bas; double val_bin[N],tmp_bin[N]; bool ban[N],ifsort[N]; vector<pii> lnk[N];
int findCenter(con(int)u,con(int)fa){ int maxsizv=0,sizu=1; for(int it=0,itt=(int)lnk[u].size();it<itt;it++){ int v=lnk[u][it].first; if(v==fa || ban[v]) continue; int sizv=findCenter(v,u); maxsizv=max(maxsizv,sizv); sizu+=sizv; } int weiu=max(rsiz-sizu,maxsizv); if(weiu<rwei) rwei=weiu,rroot=u; return sizu; } int dataDFS(con(int)u,con(int)fa,con(double)val,con(int)dep){ int ret=0; siz[u]=1; tmp_bin[dep]=max(tmp_bin[dep],val); for(int it=0,itt=(int)lnk[u].size();it<itt;it++){ int v=lnk[u][it].first; if(v==fa || ban[v]) continue; ret=max(ret,dataDFS(v,u,val+lnk[u][it].second-val_bas,dep+1)); siz[u]+=siz[v]; } return ret+1; } int highDFS(con(int)u,con(int)fa){ int ret=0; for(int it=0,itt=(int)lnk[u].size();it<itt;it++){ int v=lnk[u][it].first; if(v==fa || ban[v]) continue; ret=max(ret,highDFS(v,u)); } return ret+1; } bool cmp(con(pii)a,con(pii)b){return hgt[a.first]<hgt[b.first];} bool ina_abs(con(double)key){return key<0?-key:key;} int sgn(con(double)key){return ina_abs(key)<EPS?0:(key<0?-1:1);} bool dacDFS(int u,con(int)totsiz){ ban[u]=true; if(!ifsort[u]){ for(int it=0,itt=(int)lnk[u].size();it<itt;it++){ int v=lnk[u][it].first; if(ban[v]) continue; hgt[v]=highDFS(v,u); } sort(lnk[u].begin(),lnk[u].end(),cmp); ifsort[u]=true; } fill(val_bin,val_bin+totsiz+1,-1e9),val_bin[0]=0; int ardlen=0; for(int it=0,itt=(int)lnk[u].size();it<itt;it++){ int v=lnk[u][it].first; if(ban[v]) continue; int hgtv=dataDFS(v,0,lnk[u][it].second-val_bas,1); que.clear(); for(int i=1,j=ardlen;i<=hgtv;i++){ while(j>=bonl-i && j>=0){ while(que.size() && sgn(val_bin[que.back()]-val_bin[j])<=0) que.pop_back(); que.push_back(j); j--; } while(que.size() && que.front()>bonr-i) que.pop_front(); if(que.size() && sgn(val_bin[que.front()]+tmp_bin[i])>=0) return true; } for(int i=1;i<=hgtv;i++){ val_bin[i]=max(val_bin[i],tmp_bin[i]); tmp_bin[i]=-1e9; } ardlen=hgtv; } for(int it=0,itt=(int)lnk[u].size();it<itt;it++){ int v=lnk[u][it].first; if(ban[v]) continue; rwei=1e9,rsiz=siz[v]; findCenter(v,0); if(dacDFS(rroot,siz[v])) return true; } return false; } bool check(con(double)mmi){ fill(tmp_bin,tmp_bin+1+n,-1e9); for(int i=1;i<=n;i++) ban[i]=false; val_bas=mmi; rsiz=n,rwei=1e9,findCenter(1,0); return dacDFS(rroot,n); } int main(){ rin(n),rin(bonl),rin(bonr); for(int i=1,u,v,l;i<n;i++){ rin(u),rin(v),rin(l); lnk[u].emplace_back(v,l); lnk[v].emplace_back(u,l); } double lle=0,rri=1e6,mmi; while(lle+1e-4<rri){ mmi=(lle+rri)/2; if(check(mmi)) lle=val_bas; else rri=val_bas; } printf("%.3f\n",lle); return 0; }
|