通州 网站建设/旺道seo软件

题目：

我是超链接

题解：

首先平均数最大，平均数其实是${\sum a\over \sum 1}$，求最值是01分数规划的问题
二分mid，如果有更优的值$\sum (a-mid)>0$，那么我们的check途径就是通过点分治判断长度在[l,r]区间内有没有一条链的和>0，链的长度为a[i]-mid

而check的过程中对于每个当前子树，维护每个深度的最优值，我们只需要取之前记录的最优的一项更新就好了。我们可以把当前子树中的值按深度从大到小来更新答案，这个过程中使用单调队列维护一个深度下降权值序列，然后每次取队首更新答案即可，每次查看队首的时候把已经相加超过R的踢出去，然后查看队尾，如果比这次要添加的L-j（即下限）更小的话就T出去

这个过程是线性的，而对于全部子树 i 深度最长距离的数组的更新也只是取个max，它也是线性的。$O(nlog^2n)$

这题已经调的我不想写题解了，只能说ljBZOJ

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=150005;
#define INF 1e9
int tot,nxt[N*2],L,R,point[N],v[N*2],f[N],size[N],root,sum,deep[N],DEP,dep,q[N];
double c[N*2],a[N],b[N],mid,ans;bool vis[N];
int read()
{char ch=getchar();int x=0;while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x;
}
void addline(int x,int y,double z)
{++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z;++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; c[tot]=z; 
}
void getroot(int x,int fa)
{f[x]=0; size[x]=1;for (int i=point[x];i;i=nxt[i])if (v[i]!=fa && !vis[v[i]]){getroot(v[i],x);size[x]+=size[v[i]];f[x]=max(f[x],size[v[i]]);}f[x]=max(f[x],sum-size[x]);if (f[x]<f[root]) root=x;
}
void getdeep(int x,int fa)
{deep[x]=deep[fa]+1;for (int i=point[x];i;i=nxt[i])if (v[i]!=fa && !vis[v[i]]) getdeep(v[i],x);DEP=max(DEP,deep[x]);
}
void dfs(int x,int fa,double sum)
{if (deep[x]>R) return;a[deep[x]]=max(a[deep[x]],sum);for (int i=point[x];i;i=nxt[i])if (!vis[v[i]] && v[i]!=fa) dfs(v[i],x,sum+c[i]-mid);dep=max(dep,deep[x]);
}
bool check()
{double maxx=-INF;int now=0;b[0]=0;for (int i=1;i<=DEP;i++) b[i]=-INF;for (int i=point[root];i;i=nxt[i])if (!vis[v[i]]){int l=1,r=0;dep=0;a[0]=0;for (int j=1;j<=DEP;j++) a[j]=-INF;dfs(v[i],root,c[i]-mid);if (now) q[++r]=now;for (int j=1;j<=dep;j++){if (j>R) break;while (l<=r && q[l]+j>R) l++;if (j<=L && L-j<=DEP){while (l<=r && b[q[r]]<b[L-j]) r--;q[++r]=L-j;maxx=max(maxx,b[q[l]]+a[j]);}else if (j>L) maxx=max(maxx,b[q[l]]+a[j]); }for (int j=1;j<=dep;j++){b[j]=max(b[j],a[j]);if (j>=L && j<=R && b[now]<b[j]) now=j;}}return maxx>0;
}
void work()
{DEP=0;////getdeep(root,0);double l=ans,r=1e6;while (r-l>1e-4){mid=(l+r)/2;if (check()) l=mid;else r=mid;}vis[root]=1;ans=l;for (int i=point[root];i;i=nxt[i])if (!vis[v[i]]){sum=size[v[i]]; if (sum<L) continue;root=0; f[0]=INF; getroot(v[i],0);work();}
}
int main()
{int n;n=read();L=read();R=read(); for (int i=1;i<n;i++) {int x,y,z;x=read();y=read();z=read();addline(x,y,z);}deep[0]=-1;sum=n; root=0; f[0]=INF; getroot(1,0);work();printf("%.3lf",ans);
}