题解 CF932F 【Escape Through Leaf】

jpwang · 2018-09-25 14:15:59 · 题解

考虑dp，我们设f[i]为以i为起点的答案，那么有f[i]=min(f[j]+a[i]*b[j])这个东西，其中j的范围是i子树内任意点

考虑优化这个东西，我们发现把b看成斜率，f看成截距，那么等价于我们要在一堆直线中找到x=a[i]时的最低点，这个点显然在凸壳上

考虑怎么维护这个凸壳。可以用李超线段树+动态开点合并，也可以用平衡树动态维护凸壳启发式合并，然后就做完了

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)

typedef long long LL;
const LL INF=1000000000000000LL;
const int N=200005;

struct line {LL k,b;};
struct edge {int y,next;} e[N*2];
struct treeNode {int l,r; line rec;} t[N*51];

int a[N],b[N];
int root[N],tot;
int ls[N],edCnt;

LL f[N];

int read() {
    int x=0,v=1; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
    return x*v;
}

void add_edge(int x,int y) {
    e[++edCnt]=(edge) {y,ls[x]}; ls[x]=edCnt;
    e[++edCnt]=(edge) {x,ls[y]}; ls[y]=edCnt;
}

double get_x(line a,line b) {
    return (double)(a.b-b.b)/(b.k-a.k);
}

LL get_y(line a,LL x) {
    return a.k*x+a.b;
}

void modify(int &now,int tl,int tr,line x) {
    if (!now) {
        t[now=++tot].rec=x;
        return ;
    }
    if (get_y(t[now].rec,tl)<get_y(x,tl)&&get_y(t[now].rec,tr)<get_y(x,tr)) return ;
    if (get_y(t[now].rec,tl)>get_y(x,tl)&&get_y(t[now].rec,tr)>get_y(x,tr)) {
        t[now].rec=x; return ;
    }
    double pos=get_x(t[now].rec,x);
    int mid=(tl+tr)>>1;
    if (t[now].rec.k<x.k) {
        if (pos>mid) {
            modify(t[now].r,mid+1,tr,t[now].rec);
            t[now].rec=x;
        } else modify(t[now].l,tl,mid,x);
    } else {
        if (pos<mid) {
            modify(t[now].l,tl,mid,t[now].rec);
            t[now].rec=x;
        } else modify(t[now].r,mid+1,tr,x);
    }
}

LL query(int now,int tl,int tr,int x) {
    if (!now) return INF;
    if (tl==tr) return get_y(t[now].rec,x);
    int mid=(tl+tr)>>1;
    LL tmp,ret=get_y(t[now].rec,x);
    if (x<=mid) tmp=query(t[now].l,tl,mid,x);
    else tmp=query(t[now].r,mid+1,tr,x);
    return std:: min(ret,tmp);
}

int merge(int x,int y,int tl,int tr) {
    if (!x||!y) return x+y;
    if (tl==tr) {
        if (get_y(t[y].rec,tl)<get_y(t[x].rec,tl)) {
            t[x].rec=t[y].rec;
        }
        return x;
    }
    int mid=(tl+tr)>>1;
    t[x].l=merge(t[x].l,t[y].l,tl,mid);
    t[x].r=merge(t[x].r,t[y].r,mid+1,tr);
    modify(x,tl,tr,t[y].rec);
    return x;
}

void dfs(int now,int fa) {
    bool flag=true;
    for (int i=ls[now];i;i=e[i].next) {
        if (e[i].y==fa) continue;
        dfs(e[i].y,now);
        root[now]=merge(root[now],root[e[i].y],-N,N);
        flag=false;
    }
    if (!flag) f[now]=query(root[now],-N,N,a[now]);
    modify(root[now],-N,N,(line) {b[now],f[now]});
}

int main(void) {
    freopen("data.in","r",stdin);
    freopen("myp.out","w",stdout);
    int n=read();
    rep(i,1,n) a[i]=read();
    rep(i,1,n) b[i]=read();
    rep(i,2,n) add_edge(read(),read());
    dfs(1,0);
    rep(i,1,n) printf("%lld\n", f[i]);
    return 0;
}