欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[COGS][长链剖分]秘术(天文密葬法)

程序员文章站 2022-05-08 18:29:38
...

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

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

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;
}