两题都是树分治。
1758这题可以二分答案avgvalue，因为avgvalue=Σv(e)/s，因此二分后只需要判断Σv(e)-s*avgvalue是否大于等于0，若大于等于0则调整二分下界，否则调整二分上界。假设一棵树树根为x，要求就是经过树根x的最大答案，不经过树根x的可以递归求解。假设B[i]为当前做到的一颗x的子树中的点到x的距离为i的最大权值，A[i]为之前已经做过的所有子数中的点到x的距离为i的最大权值(这里的权值是Σv(e)-i*avgvalue),那么对于当前子树的一个距离i，可以从之前处理的子树中取到树根x距离为L-i到U-i权值中最大的那个，判断B[i]+max(A[L-i],A[U-i])是否大于等于0，这里max(A[L-i],A[U-i])可以用一个单调队列求，每处理完一颗子树用B数组更新A数组。
2599数据范围在讨论里，比较简单。
代码:
//bzoj1758
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<vector>
#include<cmath>
#include<string>
#define N 500010
#define M 1010
using namespace std;
double ans,A[N],B[N],P;
int AS,BS;
int pre[N],p[N],tt[N],ww[N],dp,n,L,U,a,b,c,father[N],s[N],flag[N],tmproot,i,j,l,r,f[N];
double left,right,mid;
void link(int x,int y,int z)
{
dp++;pre[dp]=p[x];p[x]=dp;tt[dp]=y;ww[dp]=z;
}
void getroot(int x,int fa,int sum)
{
int i,f=;
i=p[x];
father[x]=fa;
s[x]=;
while (i)
{
if ((tt[i]!=fa)&&(!flag[tt[i]]))
{
getroot(tt[i],x,sum);
s[x]=s[x]+s[tt[i]];
if (s[tt[i]]>sum/) f=;
}
i=pre[i];
}
if (sum-s[x]>sum/) f=;
if (f==) tmproot=x;
}
void dfs(int x,int fa,int deep,double value)
{
int i;
i=p[x];
B[deep]=max(B[deep],value-mid*double(deep));
BS=max(deep,BS);
while (i)
{
if ((tt[i]!=fa)&&(!flag[tt[i]]))
dfs(tt[i],x,deep+,value+ww[i]);
i=pre[i];
}
}
void work(int x,int sum)
{
int i,root,ti,ff;
getroot(x,,sum);
root=tmproot;
flag[root]=;
i=p[root];
while (i)
{
if (!flag[tt[i]])
{
if (father[root]!=tt[i])
work(tt[i],s[tt[i]]);
else
work(tt[i],sum-s[root]);
}
i=pre[i];
}
//----------------------------------
left=;right=;ti=;
while (ti<=)
{
ti++;
mid=(left+right)/;
ff=;
for (i=;i<=AS;i++)
A[i]=P;AS=;
i=p[root];
while (i)
{
if (!flag[tt[i]])
{
for (j=;j<=BS;j++)
B[j]=P;BS=;
dfs(tt[i],,,ww[i]);
r=;l=;
for (j=min(U-,AS);j>=L;j--)
{
r++;f[r]=j;
while ((l<r)&&(A[f[r]]>=A[f[r-]]))
{
f[r-]=f[r];
r--;
}
}
for (j=;j<=BS;j++)
{ if ((L<=j)&&(j<=U))
if (B[j]>=) ff=; while ((l<=r)&&(f[l]+j>U)) l++;
if (L-j>)
{
r++;f[r]=L-j;
while ((l<r)&&(A[f[r]]>=A[f[r-]]))
{
f[r-]=f[r];
r--;
}
if (A[f[l]]+B[j]>=) ff=;
}
}
for (j=;j<=BS;j++)
A[j]=max(A[j],B[j]);
AS=max(AS,BS);
}
if (ff) break;
i=pre[i];
} if (ff) left=mid;else right=mid;
}
ans=max(ans,left);
flag[root]=;
}
int main()
{
scanf("%d",&n);
scanf("%d%d",&L,&U);
P=;
P=-P*P;
for (i=;i<=n-;i++)
{
scanf("%d%d%d",&a,&b,&c);
link(a,b,c);
link(b,a,c);
}
for (i=;i<=n;i++)
{
A[i]=P;
B[i]=P;
}
ans=;
work(,n);
printf("%.3lf",ans);
}
//bzoj2599
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<vector>
#include<cmath>
#include<string>
#define N 1000010
#define M 1010
#define P 1000000007
using namespace std;
int i,j,p[N],tt[N],s[N],father[N],ww[N],pre[N],tmproot,n,m;
int dp,flag[N],a,b,c,f[N],g[N],AS,BS,A[N],B[N],ans;
void link(int x,int y,int z)
{
dp++;pre[dp]=p[x];p[x]=dp;tt[dp]=y;ww[dp]=z;
}
void getroot(int x,int fa,int sum)
{
int i,f=;
i=p[x];
father[x]=fa;
s[x]=;
while (i)
{
if ((tt[i]!=fa)&&(!flag[tt[i]]))
{
getroot(tt[i],x,sum);
s[x]=s[x]+s[tt[i]];
if (s[tt[i]]>sum/) f=;
}
i=pre[i];
}
if (sum-s[x]>sum/) f=;
if (f==) tmproot=x;
}
void dist(int x,int fa,int deep,int value)
{
int i;
i=p[x];
if (value<=m)
{
if (g[value]==0x37373737)
{
BS++;
B[BS]=value;
}
g[value]=min(g[value],deep);
}
else
return;
while (i)
{
if ((tt[i]!=fa)&&(!flag[tt[i]]))
dist(tt[i],x,deep+,value+ww[i]);
i=pre[i];
} }
void work(int x,int sum)
{
int i,root;
getroot(x,,sum);
root=tmproot;
flag[root]=;
i=p[root];
while (i)
{
if (!flag[tt[i]])
{
if (tt[i]==father[root])
work(tt[i],sum-s[root]);
else
work(tt[i],s[tt[i]]);
}
i=pre[i];
}
//-----------------------------
for (i=;i<=AS;i++)
f[A[i]]=0x37373737;AS=;
i=p[root];
while (i)
{
if (!flag[tt[i]])
{
for (j=;j<=BS;j++)
g[B[j]]=0x37373737;BS=;
dist(tt[i],,,ww[i]);
for (j=;j<=BS;j++)
ans=min(ans,g[B[j]]+f[m-B[j]]);
for (j=;j<=BS;j++)
if (f[B[j]]==0x37373737)
{
AS++;A[AS]=B[j];
}
for (j=;j<=BS;j++)
f[B[j]]=min(f[B[j]],g[B[j]]);
}
i=pre[i];
}
flag[root]=;
}
int main()
{
scanf("%d%d",&n,&m);
for (i=;i<=n-;i++)
{
scanf("%d%d%d",&a,&b,&c);
a++;b++;
link(a,b,c);
link(b,a,c);
}
for (i=;i<=m;i++)
{
f[i]=0x37373737;
g[i]=f[i];
}
ans=0x37373737;
work(,n);
if (ans!=0x37373737)
printf("%d",ans);
else
printf("-1");
}