比赛 |
cdcqの省选膜你赛 |
评测结果 |
WWAAAWAAAAAWAAWWAAAA |
题目名称 |
秘术「天文密葬法」 |
最终得分 |
70 |
用户昵称 |
Cydiater |
运行时间 |
5.741 s |
代码语言 |
C++ |
内存使用 |
7.37 MiB |
提交时间 |
2017-04-11 12:24:52 |
显示代码纯文本
//B
//by Cydiater
//2017.4.11
#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <bitset>
#include <set>
#include <complex>
#include <vector>
using namespace std;
#define ll long long
#define db double
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define Auto(i,node) for(int i=LINK[node];i;i=e[i].next)
#define FILE "cdcq_b"
const int MAXN=2e5+5;
const db oo=5e10;
const db eps=1e-4;
int N,M,va[MAXN],vb[MAXN];
bool vis[MAXN];
db ans=oo,mn[MAXN],res=oo;
int dcmp(db x){
if(fabs(x)<eps)return 0;
return x<0?-1:1;
}
namespace Graph{
struct edge{
int y,next;
}e[MAXN];
int LINK[MAXN],len=0,siz[MAXN],mxsiz[MAXN],root;
int sum;
inline void insert(int x,int y){
e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;
}
inline void Insert(int x,int y){
insert(x,y);
insert(y,x);
}
void mkrt(int node,int fa){
siz[node]=1;mxsiz[node]=0;
Auto(i,node)if(e[i].y!=fa&&!vis[e[i].y]){
mkrt(e[i].y,node);
siz[node]+=siz[e[i].y];
cmax(mxsiz[node],siz[e[i].y]);
}
cmax(mxsiz[node],sum-siz[node]);
if(mxsiz[node]<mxsiz[root])root=node;
}
void Go(int node,int fa,int deep,db dis,db k){
if(deep>M)return;
cmin(res,dis+mn[M-deep]);
Auto(i,node)if(!vis[e[i].y]&&e[i].y!=fa)
Go(e[i].y,node,deep+1,dis+va[e[i].y]-vb[e[i].y]*k,k);
}
void Mark(int node,int fa,int deep,db dis,db k){
if(deep>M)return;
cmin(mn[deep],dis);
Auto(i,node)if(!vis[e[i].y]&&e[i].y!=fa)
Mark(e[i].y,node,deep+1,dis+va[e[i].y]-vb[e[i].y]*k,k);
}
void Clear(int node,int fa,int deep){
if(deep>M)return;
mn[deep]=oo;
Auto(i,node)if(!vis[e[i].y]&&e[i].y!=fa)
Clear(e[i].y,node,deep+1);
}
bool check(int node,db k){
res=oo;
Auto(i,node)if(!vis[e[i].y]){
Go(e[i].y,node,2,va[node]-vb[node]*k+va[e[i].y]-vb[e[i].y]*k,k);
Mark(e[i].y,node,1,va[e[i].y]-vb[e[i].y]*k,k);
}
Auto(i,node)if(!vis[e[i].y])
Clear(e[i].y,node,1);
return dcmp(res)<=0;
}
void Fix(int node,int fa){
siz[node]=1;
Auto(i,node)if(!vis[e[i].y]&&e[i].y!=fa){
Fix(e[i].y,node);
siz[node]+=siz[e[i].y];
}
}
void Work(int node){
vis[node]=1;
db leftt=0,rightt=oo,mid;
while(leftt+eps<rightt){
mid=(leftt+rightt)/2;
if(check(node,mid)) rightt=mid;
else leftt=mid;
}
if(check(node,leftt)) cmin(ans,leftt);
else if(check(node,rightt)) cmin(ans,rightt);
Fix(node,0);
Auto(i,node)if(!vis[e[i].y]){
sum=siz[e[i].y];
root=0;
mkrt(e[i].y,node);
Work(root);
}
}
}using namespace Graph;
namespace solution{
void Prepare(){
scanf("%d%d",&N,&M);
up(i,1,N)scanf("%d",&va[i]);
up(i,1,N)scanf("%d",&vb[i]);
up(i,2,N){
int x,y;
scanf("%d%d",&x,&y);
Insert(x,y);
if(M==-1){
if(vb[i]!=0)cmin(ans,1.0*va[i]/vb[i]);
}
}
mn[0]=0;
up(i,1,N)mn[i]=oo;
}
void Solve(){
if(M==-1){
printf("%.2lf\n",ans);
return;
}
mxsiz[0]=N+1;root=0;
sum=N;
mkrt(1,0);
Work(root);
if(ans==-oo){
puts("-1");
return;
}
printf("%.2lf\n",ans);
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
Prepare();
Solve();
return 0;
}