比赛 |
cdcqの省选膜你赛 |
评测结果 |
WWAAAAAAAAAAAAAAEEEE |
题目名称 |
秘术「天文密葬法」 |
最终得分 |
70 |
用户昵称 |
FoolMike |
运行时间 |
2.310 s |
代码语言 |
C++ |
内存使用 |
33.20 MiB |
提交时间 |
2017-04-11 22:15:13 |
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
const int N=4e5+10;
typedef long long ll;
typedef double db;
int n,m,a[N],b[N],w[N],next[N],head[N];
void add(int f,int t){
static int cnt=0;
w[++cnt]=t;
next[cnt]=head[f];
head[f]=cnt;
}
db ans=1e20;
struct pt{
ll x,y;
pt(ll X=0,ll Y=0){x=X;y=Y;}
bool operator < (const pt a)const{return x==a.x?y>a.y:x<a.x;}
void print()const{printf("%lld %lld\n",x,y);}
};
db k(pt x,pt y){
if (x.x==y.x) return x.y<y.y?1e20:-1e20;
return db(x.y-y.y)/(x.x-y.x);
}
typedef tree<pt,null_mapped_type,less<pt>,rb_tree_tag,tree_order_statistics_node_update> Tree;
struct convex_hall{
Tree T;
Tree::iterator x,l,r,ll,rr;
void init(){
T.clear();
T.insert(pt(-1e10,1e17));
T.insert(pt(-1e10-1,1e18));
T.insert(pt(1e10,1e17));
T.insert(pt(1e10+1,1e18));
}
void ins(pt v){
T.insert(v);
l=r=x=T.find(v);
--l;++r;
while (1){
ll=l;--ll;
if (k(*ll,*l)<k(*l,*x)) break;
T.erase(l);
l=ll;
}
while (1){
rr=r;++rr;
if (k(*x,*r)<k(*r,*rr)) break;
T.erase(r);
r=rr;
}
if (k(*l,*x)>k(*x,*r)) T.erase(x);
}
void query(pt x){
int l=2,r=T.size()-3;
if (l>r) return;
while (l<r){
int mid=(l+r)>>1;
ll=T.find_by_order(mid);
rr=T.find_by_order(mid+1);
if (k(x,*ll)<k(x,*rr)) r=mid;else l=mid+1;
}
ll=T.find_by_order(l);
ans=min(ans,k(x,*ll));
}
}H[200010];
int q[N],size,s[N],big[N],h[N],fa[N];
bool vis[N];
db sa[N],sb[N];
void solve(int x){
q[size=1]=x;fa[x]=x;
for (int i=1;i<=size;i++){
int v=q[i];
s[v]=1;big[v]=0;
for (int i=head[v];i;i=next[i]){
int u=w[i];
if (vis[u]||fa[u]) continue;
fa[u]=v;
q[++size]=u;
}
}
int root=x;
for (int i=size;i;i--){
int v=q[i],u=fa[v];
if (big[v]<=size/2&&s[v]>=size/2) root=v;
s[u]+=s[v];
big[u]=max(big[u],s[v]);
fa[v]=0;
}
vis[root]=1;
q[size=1]=root;
H[0].ins(pt(0,0));
for (int i=head[root];i;i=next[i]){
int S=w[i],last=size;
if (vis[S]) continue;
fa[S]=root;
h[S]=2;
sa[S]=a[root]+a[S];
sb[S]=b[root]+b[S];
q[++size]=S;
for (int i=last+1;i<=size;i++){
int v=q[i];
if (h[v]<=m) H[m-h[v]].query(pt(-sb[v],-sa[v]));
for (int i=head[v];i;i=next[i]){
int u=w[i];
if (fa[u]||vis[u]) continue;
fa[u]=v;
h[u]=h[v]+1;
sa[u]=sa[v]+a[u];
sb[u]=sb[v]+b[u];
q[++size]=u;
}
}
for (int i=last+1;i<=size;i++){
int v=q[i];
h[v]--;
sa[v]-=a[root];
sb[v]-=b[root];
if (h[v]<=m) H[h[v]].ins(pt(sb[v],sa[v]));
}
}
for (int i=1;i<=size;i++){
int v=q[i];
fa[v]=0;
if (h[v]<=m) H[h[v]].init();
}
for (int i=head[root];i;i=next[i])
if (!vis[w[i]]) solve(w[i]);
}
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("%d",&a[i]);
for (int i=1;i<=n;i++) scanf("%d",&b[i]);
for (int i=1;i<n;i++){
int f,t;
scanf("%d%d",&f,&t);
add(f,t);add(t,f);
}
for (int i=0;i<=m;i++) H[i].init();
solve(1);
if (ans<1e20) printf("%.2lf\n",ans);else puts("-1");
return 0;
}