应该不算评论区题解罢?
rt,这题本人照着[BJOI2017]树的难题的思路敲了暴力的单调队列按秩合并的程序,但没有按照题解中“01分数规划”的思想在外面套一个二分。
我采取的方式是在单调队列尾只要发现新加入答案更优,就弹掉队尾;在队首先弹完不合法的,然后只要排第二的答案更优就弹掉队首。
代码长这样:
while(tmp>=0&&tmp+dep[x]>=L){
while(!dq.empty()&&(buc[tmp]+sum[x])*(dq.back()+dep[x])>=(buc[dq.back()]+sum[x])*(tmp+dep[x]))dq.pop_back();
dq.push_back(tmp--);
}
while(!dq.empty()&&dq.front()+dep[x]>R)dq.pop_front();
while(dq.size()>=2&&(buc[dq[0]]+sum[x])*(dq[1]+dep[x])<=(buc[dq[1]]+sum[x])*(dq[0]+dep[x]))dq.pop_front();
if(!dq.empty())mx=max(mx,1.0*(buc[dq.front()]+sum[x])/(dq.front()+dep[x]));
我感觉这是错的,但是又不知道怎么证伪;况且此代码也能够AC。所以求助各位神仙,可以hack的,给出一组数据;如果能够证明正确性,那么这题就多了种nlogn的做法。
完整代码:
#pragma GCC optimize(3)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const ll fni=-1e11;
int n,L,R;
double mx;
int ROOT,SZ,sz[200100],msz[200100];
int dep[200100],mdp[200100],lim;
ll sum[200100],buc[200100];
vector<pair<int,int> >v[200100];
bool vis[200100];
void getsz(int x,int fa){
sz[x]=1;
for(auto i:v[x])if(!vis[i.first]&&i.first!=fa)getsz(i.first,x),sz[x]+=sz[i.first];
}
void getroot(int x,int fa){
sz[x]=1,msz[x]=0;
for(auto i:v[x])if(!vis[i.first]&&i.first!=fa)getroot(i.first,x),sz[x]+=sz[i.first],msz[x]=max(msz[x],sz[i.first]);
msz[x]=max(msz[x],SZ-sz[x]);
if(msz[x]<msz[ROOT])ROOT=x;
}
void getdep(int x,int fa,int fr){
mdp[fr]=max(mdp[fr],dep[x]);
for(auto i:v[x])if(!vis[i.first]&&i.first!=fa)dep[i.first]=dep[x]+1,sum[i.first]=sum[x]+i.second,getdep(i.first,x,fr);
}
bool cmp(pair<int,int>x,pair<int,int>y){
return mdp[x.first]<mdp[y.first];
}
queue<int>q;
deque<int>dq;
void bfsread(int x){
dq.clear();
q.push(x);
int tmp=lim;
while(!q.empty()){
x=q.front(),q.pop();
while(tmp>=0&&tmp+dep[x]>=L){
while(!dq.empty()&&(buc[tmp]+sum[x])*(dq.back()+dep[x])>=(buc[dq.back()]+sum[x])*(tmp+dep[x]))dq.pop_back();
dq.push_back(tmp--);
}
while(!dq.empty()&&dq.front()+dep[x]>R)dq.pop_front();
while(dq.size()>=2&&(buc[dq[0]]+sum[x])*(dq[1]+dep[x])<=(buc[dq[1]]+sum[x])*(dq[0]+dep[x]))dq.pop_front();
if(!dq.empty())mx=max(mx,1.0*(buc[dq.front()]+sum[x])/(dq.front()+dep[x]));
for(auto i:v[x])if(!vis[i.first]&&dep[i.first]>dep[x])q.push(i.first);
}
}
void bfswrite(int x){
q.push(x);
while(!q.empty()){
x=q.front(),q.pop();
buc[dep[x]]=max(buc[dep[x]],sum[x]),lim=max(lim,dep[x]);
for(auto i:v[x])if(!vis[i.first]&&dep[i.first]>dep[x])q.push(i.first);
}
}
void calc(int x){
sum[x]=dep[x]=0;
for(auto i:v[x])if(!vis[i.first])sum[i.first]=i.second,dep[i.first]=1,getdep(i.first,x,i.first);
sort(v[x].begin(),v[x].end(),cmp);
for(auto i:v[x])if(!vis[i.first])mdp[i.first]=0,bfsread(i.first),bfswrite(i.first);
for(int i=1;i<=lim;i++)buc[i]=fni;lim=0;
}
void solve(int x){
calc(x);
getsz(x,0);
vis[x]=true;
for(auto i:v[x])if(!vis[i.first])ROOT=0,SZ=sz[i.first],getroot(i.first,0),solve(ROOT);
}
void read(int &x){
x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int main(){
read(n),read(L),read(R);
for(int i=1;i<=n;i++)buc[i]=fni;
for(int i=1,x,y,z;i<n;i++)read(x),read(y),read(z),v[x].push_back(make_pair(y,z)),v[y].push_back(make_pair(x,z));
msz[0]=n+1,SZ=n,getroot(1,0),solve(ROOT);
printf("%.3lf\n",mx);
return 0;
}