比赛 cdcqの省选膜你赛 评测结果 AAWWWATTTTTTTTTTWWWW
题目名称 秘术「天文密葬法」 最终得分 15
用户昵称 再见 运行时间 30.407 s
代码语言 C++ 内存使用 28.33 MiB
提交时间 2017-04-11 21:23:48
显示代码纯文本
#include <cstdio>
#include <cstdlib>

int vis[200010],cnt,visone,n,m,tot,dep[200010],fa[200010],head[200010],next[400010],to[400010],Tfa[25][30010];
double a[200010],b[200010],suma[25][30010],sumb[25][30010],ans;

inline double min(double &aa,double &bb){return aa<bb?aa:bb;}
inline void swap(int &i,int &j){int t=i; i=j; j=t;}

inline void ae(int u,int v){
	++tot; to[tot]=v;
	next[tot]=head[u]; head[u]=tot;
}

void dfs(int u){
	for(int p=head[u];p;p=next[p])
		if(to[p]!=fa[u]){
			fa[to[p]]=u;
			dep[to[p]]=dep[u]+1;
			dfs(to[p]);
		}
}

inline void update(double K){
	if(!visone) visone=true,ans=K;
	else ans=min(ans,K);
}

inline void work(int u,int v){
	double sa=0,sb=0; int LCA=0;
	if(dep[u]<dep[v]) swap(u,v);
	int d=dep[u]-dep[v],thedis=dep[u]+dep[v];
	if(d+1>m) return; 
	for(int i=0;(1<<i)<=d;i++)
		if(d&(1<<i)){
			sa+=suma[i][u];
			sb+=sumb[i][u];
			u=Tfa[i][u];
		}
	for(int i=22;i>=0;i--)
		if(Tfa[i][u]!=Tfa[i][v]){
			sa+=suma[i][u]; sa+=suma[i][v];
			sb+=sumb[i][u]; sb+=sumb[i][v];
			u=Tfa[i][u]; v=Tfa[i][v];			
		}
	LCA=u;
	sa+=a[LCA]; sb+=b[LCA];
	if(thedis-2*dep[LCA]+1==m)
		update(sa/sb);
}

int Q[200010],dis[200010],qhead,tail;
double rsuma[200010],rsumb[200010];

int bfs(int s){
	qhead=tail=0; Q[tail++]=s;
	for(int i=1;i<=n;i++) dis[i]=0,rsuma[i]=rsumb[i]=0;
	rsuma[s]=a[s]; rsumb[s]=b[s]; dis[s]=1;
	while(qhead<tail){
		int u=Q[qhead++];
		for(int p=head[u];p;p=next[p])
			if(!dis[to[p]]){
				Q[tail++]=to[p]; 
				dis[to[p]]=dis[u]+1;
				rsuma[to[p]]=rsuma[u]+a[to[p]];
				rsumb[to[p]]=rsumb[u]+b[to[p]];
			}
	}
	int mx=1;
	for(int i=1;i<=n;i++)
		if(dis[i]>dis[mx])
			mx=i;
	return mx;
}

void extrawork(){
	int u=bfs(1);
	bfs(u);
	for(int i=1;i<=n;i++)
		if(dis[i]==m) update(rsuma[i]/rsumb[i]),vis[++cnt]=i;
		else if(dis[i]==m+1) vis[++cnt]=i;
	for(int j=1;j<=cnt;j++){
		bfs(vis[j]);
		for(int i=1;i<=n;i++)
			if(dis[i]==m)
				update(rsuma[i]/rsumb[i]);
	}
	if(!visone) printf("-1\n");
	else printf("%.2lf\n",ans);
}

int main(){
	freopen("cdcq_b.in","r",stdin);
	freopen("cdcq_b.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
	for(int i=1;i<=n;i++) scanf("%lf",&b[i]);
	for(int i=1;i<n;i++){
		int u,v; scanf("%d%d",&u,&v);
		ae(u,v); ae(v,u);
	}
	if(n<=30000){
		dfs(1);
		for(int i=1;i<=n;i++){
			Tfa[0][i]=fa[i];
			suma[0][i]=a[i];
			sumb[0][i]=b[i];
		}
		for(int i=1;(1<<i)<=n;i++)
			for(int j=1;j<=n;j++){
				Tfa[i][j]=Tfa[ i-1 ][ Tfa[i-1][j] ];
				suma[i][j]=suma[i-1][j]+suma[i-1][ Tfa[i-1][j] ];
				sumb[i][j]=sumb[i-1][j]+sumb[i-1][ Tfa[i-1][j] ];
			}
		for(int i=1;i<=n;i++)
			for(int j=i;j<=n;j++){
				if(i==j&&m==1) update(a[i]/b[i]);
				if(i!=j) work(i,j);
			}
		if(!visone) printf("-1\n");
		else printf("%.2lf\n",ans);
	}
	else if(m==n-1)
		extrawork();
	else
		printf("-1\n");
	return 0;
}