题目大意：给定一棵树，询问长度在[l,u]范围内的路径中边权的平均值的最大值
01分数规划，首先想到二分答案
既然是统计路径肯定是点分治
每次统计时我们要找有没有大于0的路径存在
那么对于一棵子树的每一个深度i记录一个路径权值和的最大值
然后在这棵子树之前的所有子树的深度可选范围就是[l-i,u-i] 这个窗口是不停滑动的 因此用单调队列维护最大值即可
↑上面这些网上的题解都说的还是蛮详细的
据说二分套在树分治里面会快一些 但是 尼玛 我被卡常了！！
这里只提供一些剪枝
1.当前分治的总点数<=l 那么一定不能找到一条长度>=l的路径 直接退出即可
2.二分的下界可以设为ans 二分后直接将ans设为l
3.避免一切的memset 利用时间戳来优化
4.一个奇葩的优化：由于剪枝2那里l那里有剪枝 因此二分的时候可以偏向l一些 比如说令mid=(l+l+r)/3 亲测当mid=(l*9+r)/10的时候是最快的
为何乃们都写的那么快……为何我被卡常了……QAQ
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 100100
using namespace std;
struct abcd{
int to,f,next;
bool ban;
}table[M<<1];
int head[M],tot=1;
int n,m,lower,upper;
int size[M],fa[M];
double ans;
namespace IStream{
const int L=1<<15;
char buffer[L];
char *S,*T;
inline char Get_Char()
{
if(S==T)
{
T=(S=buffer)+fread(buffer,1,L,stdin);
if(S==T) return EOF;
}
return *S++;
}
inline int Get_Int()
{
int re=0;
char c;
do c=Get_Char(); while(c<'0'||c>'9');
while(c>='0'&&c<='9')
re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
return re;
}
}
void Add(int x,int y,int z)
{
table[++tot].to=y;
table[tot].f=z;
table[tot].next=head[x];
head[x]=tot;
}
void Get_Centre_Of_Gravity(int x,int n,int from,int &cg)
{
int i,flag=1;
size[x]=1;fa[x]=from;
for(i=head[x];i;i=table[i].next)
if(!table[i].ban&&table[i].to!=from)
{
Get_Centre_Of_Gravity(table[i].to,n,x,cg);
size[x]+=size[table[i].to];
if(size[table[i].to]<<1>n) flag=0;
}
if(n-size[x]<<1>n) flag=0;
if(flag) cg=x;
}
void DFS(int x,int from,double avg,double now,int dpt,double temp[],int& max_dpt)
{
int i;
if(dpt>max_dpt)
{
temp[dpt]=now;
max_dpt=dpt;
}
else temp[dpt]=max(temp[dpt],now);
for(i=head[x];i;i=table[i].next)
if(!table[i].ban&&table[i].to!=from)
DFS(table[i].to,x,avg,now+table[i].f-avg,dpt+1,temp,max_dpt);
}
bool Judge(int cg,double avg)
{
static double max_f[M];
static int tim[M],T;
static double temp[M];
int i;
max_f[0]=0;tim[0]=++T;
for(i=head[cg];i;i=table[i].next)
if(!table[i].ban)
{
int max_dpt=0;
DFS(table[i].to,cg,avg,table[i].f-avg,1,temp,max_dpt);
static int q[M];
int j,k=max(0,lower-max_dpt),r=0,h=0;
for(j=max_dpt;j;j--)
{
for(;j+k<=upper;k++)
{
if(tim[k]!=T) tim[k]=T,max_f[k]=-2147483647;
while(r>h&&max_f[k]>max_f[q[r]])
q[r--]=0;
q[++r]=k;
}
while(r>h&&q[h+1]+j<lower)
q[++h]=0;
if(max_f[q[h+1]]+temp[j]>=0)
return true;
}
for(j=max_dpt;j;j--)
max_f[j]=max(max_f[j],temp[j]);
}
return false;
}
void Tree_Divide_And_Conquer(int root,int size)
{
int i,cg;
if(size<=lower) return ;
Get_Centre_Of_Gravity(root,size,0,cg);
double l=ans,r=m;
while(r-l>1e-4)
{
double mid=(l*9+r)/10.0;
if( Judge(cg,mid) )
l=mid;
else
r=mid;
}
ans=l;
if(fa[cg]) ::size[fa[cg]]=size-::size[cg];
for(i=head[cg];i;i=table[i].next)
if(!table[i].ban)
{
table[i].ban=table[i^1].ban=1;
Tree_Divide_And_Conquer(table[i].to,::size[table[i].to]);
}
}
int main()
{
//freopen("rebuild.in","r",stdin);
//freopen("rebuild.out","w",stdout);
int i,x,y,z;
cin>>n>>lower>>upper;
for(i=1;i<n;i++)
{
//scanf("%d%d%d",&x,&y,&z);
x=IStream::Get_Int();
y=IStream::Get_Int();
z=IStream::Get_Int();
Add(x,y,z);
Add(y,x,z);
m=max(m,z);
}
Tree_Divide_And_Conquer(1,n);
printf("%.3lf\n",ans);
return 0;
}