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

2019.03.11 COGS2652 秘术(天文密葬法)(分数规划长链剖分)

程序员文章站 2022-03-02 22:48:07
...

传送门
题意:nn个点的树,每个点两个值a,ba,b,问长度为mm的路径aibi\frac{\sum a_i}{\sum b_i}的最大值。


思路:一眼要01分数规划,考虑checkcheck可以用点分治水掉。
然而也可以用长链剖分,复杂度降低一个loglog
代码:

#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
	static char buf[rlen],*ib,*ob;
	(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
	return ib==ob?-1:*ib++;
}
inline int read(){
	int ans=0;
	char ch=gc();
	while(!isdigit(ch))ch=gc();
	while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
	return ans;
}
typedef long long ll;
const int N=1e5+5;
int mdep[N],dep[N],top[N],hson[N],len[N],fa[N],n,m,a[N],b[N];
vector<int>e[N];
double ans,w[N],ftmp[N<<1],*f[N],*tmp;
void dfs1(int p){
	for(ri i=0,v;i<e[p].size();++i){
		if((v=e[p][i])==fa[p])continue;
		fa[v]=p,mdep[v]=dep[v]=dep[p]+1,dfs1(v),mdep[p]=max(mdep[p],mdep[v]);
		if(mdep[hson[p]]<mdep[v])hson[p]=v;
	}
	len[p]=mdep[p]-dep[p]+1;
}
void dfs2(int p){
	if(hson[p])f[hson[p]]=f[p]+1,dfs2(hson[p]);
	for(ri i=0,v;i<e[p].size();++i){
		if((v=e[p][i])==fa[p]||v==hson[p])continue;
		f[v]=tmp,tmp+=len[v],dfs2(v);
	}
}
void dfs3(int p){
	f[p][0]=(w[p]+=w[fa[p]]);
	if(!hson[p])return;
	dfs3(hson[p]);
	for(ri i=0,v;i<e[p].size();++i){
		if((v=e[p][i])==fa[p]||v==hson[p])continue;
		dfs3(v);
		for(ri j=0;j<len[v];++j)if(j+1+len[p]>m&&m>j)ans=min(ans,f[p][m-j-1]+f[v][j]-(w[p]+w[fa[p]]));
		for(ri j=0;j<len[v];++j)f[p][j+1]=min(f[p][j+1],f[v][j]);
	}
	if(len[p]>m)ans=min(ans,f[p][m]);
}
int main(){
	n=read(),m=read();
	for(ri i=1;i<=n;++i)a[i]=read();
	for(ri i=1;i<=n;++i)b[i]=read();
	for(ri i=1,u,v;i<n;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
    if(m<0){for(int i=1;i<=n;++i)ans=min(ans,(double)a[i]/b[i]);return printf("%.2lf\n",ans),0;}
	dfs1(1);
	tmp=ftmp,f[1]=tmp,tmp+=mdep[1];
	dfs2(1);
	--m;
	double l=0.0,r=1e9;
	while(r-l>=1e-3){
		double mid=(l+r)/2;
		ans=1e18;
		for(ri i=1;i<=n;++i)w[i]=(double)a[i]-mid*b[i];
		dfs3(1);
		ans<=0?r=mid:l=mid;
	}
	printf("%.2lf",l);
	return 0;
}
相关标签: 分治