description
题面
给个树，第(i)个点有两个权值(a_i)和(b_i)，现在求一条长度为(m)的路径，使得(frac{sum a_i}{sum b_i})最小
data range
[mle nle 2 imes 10^5
]
solution
0/1分数规划？二分吧。
二分一个值(S),要使得(frac{sum a_i}{sum b_i}le S)
那么$$sum(a_i-Sb_i)le0$$
把每个点的点权做成这个，然后(DP check)最优答案是否(le 0)就行
如何(DP)?
暴力的，(f_{i,j})表示(i)子数内长度为(j)的链的最优解，转移是(O(n^2))的
按照深度的树上(DP)可以使用长链剖分优化到(O(n))
总复杂度就是(O(nlogsum w))
code
#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FILE "cdcq_b"
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-4;
const int mod=998244353;
const int N=200010;
const dd pi=acos(-1);
const int inf=2147483647;
const ll INF=1e18+1;
const ll P=100000;
il ll read(){
RG ll data=0,w=1;RG char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
return data*w;
}
il void file(){
srand(time(NULL)+rand());
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
}
int n,m;dd x[N],y[N];
int head[N],nxt[N<<1],to[N<<1],cnt;
int len[N],son[N];
void dfs1(int u,int fa){
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==fa)continue;
dfs1(v,u);if(len[son[u]]<len[v])son[u]=v;
}
len[u]=len[son[u]]+1;
}
dd *pos,f[N],*A[N],tag[N],ans,K;
void dfs2(int u,int fa){
pos++;A[u]=pos;dd *a=A[u];
if(!son[u]){
a[0]=x[u]*1.0-K*y[u];
if(m==1)ans=min(ans,a[0]);
return;
}
dfs2(son[u],u);
tag[u]=tag[son[u]]+x[u]*1.0-K*y[u];
a[0]=x[u]*1.0-K*y[u]-tag[u];
dd *b;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==fa||v==son[u])continue;
dfs2(v,u);b=A[v];
if(m==1)ans=min(ans,b[0]+tag[v]);
else
for(RG int j=0;j<m-1&&j<len[v];j++)
if(m-j-2<len[u])ans=min(ans,b[j]+tag[v]+a[m-j-2]+tag[u]);
for(RG int j=0;j<len[v];j++)
a[j+1]=min(a[j+1],b[j]+tag[v]+x[u]*1.0-K*y[u]-tag[u]);
}
if(len[u]>=m)ans=min(ans,a[m-1]+tag[u]);
}
dd g[N];
void dfs3(int u,int fa){
if(!son[u]){g[u]=x[u]*1.0-K*y[u];ans=min(ans,g[u]);return;}
dfs3(son[u],u);if(g[son[u]]<0)g[u]+=g[son[u]];else g[u]=0;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==fa||v==son[u])continue;
dfs3(v,u);ans=min(ans,g[u]+x[u]*1.0-K*y[u]+g[v]);
g[u]=min(g[u],g[v]);
}
g[u]+=x[u]*1.0-K*y[u];ans=min(ans,g[u]);
}
il bool check(){
ans=INF;
if(m!=-1){pos=f;memset(f,0,sizeof(f));dfs2(1,0);}
else dfs3(1,0);
return ans<eps;
}
int main()
{
file();
RG dd l=0,r=0,mid,as=-INF;
scanf("%d%d",&n,&m);
if(n==1||(m!=-1&&m>=n)){puts("-1");return 0;}
for(RG int i=1;i<=n;i++){scanf("%lf",&x[i]);r+=x[i];}
for(RG int i=1;i<=n;i++){
scanf("%lf",&y[i]);
}
for(RG int i=1,u,v;i<n;i++){
u=read();v=read();
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
}
dfs1(1,0);
while(r-l>=eps){
K=mid=(l+r)/2;
if(!check())l=mid;
else as=mid,r=mid;
}
if(as==-INF)puts("-1");
else printf("%.2lf
",as);
return 0;
}