[COGS][长链剖分]秘术（天文密葬法）

没有传送门
题意：你有一棵有n个点的树，每个点有两个权值ai，bi，请找出一条长为m的路径，使得ans=∑ai/∑bi最小，若没有长度为m的路径输出-1

解法：明显的分数规划，二分后问题转化为求有没有一条长度为m的路径的权值和使$\sum{ai}-mid*\sum{bi}$∑ai−mid∗∑bi$\le0$≤0
就可以长链剖分了

Code：

#include<bits/stdc++.h>
#define db double
#define eps 1e-3
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
	while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
	return res*f;
}
const int N=2e5+5;
int n,m,a[N],b[N],tot=0,vis[N<<1],head[N<<1],nxt[N<<1];
inline void add(int x,int y){vis[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
int pt[N],len[N],lson[N];
db val[N],tmp[N],*f[N],*id=tmp,ans=1e18;
void dfs(int v){
	pt[v]=1;
	for(int i=head[v];i;i=nxt[i]){
		if(pt[vis[i]]) continue;
		dfs(vis[i]);
		if(len[vis[i]]>len[lson[v]]) lson[v]=vis[i];
	}
	len[v]=len[lson[v]]+1;
}
void dp(int v,db mid){
	pt[v]=1;
	val[v]=a[v]-mid*b[v],f[v][0]=0;
	if(lson[v]) f[lson[v]]=f[v]+1,dp(lson[v],mid),val[v]+=val[lson[v]],f[v][0]-=val[lson[v]];
	for(int i=head[v];i;i=nxt[i]){
		int y=vis[i];
		if(pt[y]) continue;
		f[y]=id;id+=len[y];dp(y,mid);
		for(int j=0;j<len[y] && j<m;j++) if(m-j-1<len[v]) ans=min(ans,f[y][j]+val[y]+f[v][m-j-1]+val[v]);
		for(int j=0;j<len[y] && j<m;j++) f[v][j+1]=min(f[v][j+1],f[y][j]+val[y]-val[v]+a[v]-mid*b[v]);
	}
	if(m<len[v]) ans=min(ans,f[v][m]+val[v]);
}
int main(){
	n=read(),m=read()-1;
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) b[i]=read();
	for(int i=1;i<=n;i++) ans=min(ans,1.0*a[i]/b[i]);
	if(m==-2 || !m) {printf("%.2lf",ans);return 0;}
	for(int x,y,i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);
	dfs(1);
	db l=0,r=N;
	while(r-l>eps){
		db mid=(l+r)/2;
		memset(pt,0,sizeof(pt));memset(tmp,0x7f,sizeof(tmp));ans=1e18;
		id=tmp;f[1]=id;id+=len[1];dp(1,mid);
		if(ans>=0) l=mid;
		else r=mid;
	}
	if(l>=2e5) puts("-1");
	else printf("%.2lf",l);
	return 0;
}