CF932F Escape Through Leaf

FxorG · 2021-07-10 15:13:44 · 个人记录

前言，感谢 chen_qian 和 cyffff 大佬

\text{Solution}

序列怎么做？

是不是令 f[i] 为 i 到叶子的最小值。

易得

我们发现， f[j]+a[i]*b[j] 有点像一次函数的形式。

即 K=b[j],B=f[j],x=a[i]。

那么可以李超线段树维护下最小值。

到树上我们发现同根不同子树是不能相互干扰的， 父亲到最后的叶子节点就是儿子们到叶子节点的并，那就线段树合并了。

\text{Code}

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>

#define N (int)(5e5+5)
#define M (int)(1e5)
#define ll long long
#define inf 0x7fffffffffffffffLL
#define il inline
#define G getchar()
using namespace std;

struct node {
    int K; ll B;
}s[N];

struct edge {
    int nex,to;
}e[N<<1];

ll f[N];
int head[N],cnt;
int val[N<<2],ls[N<<2],rs[N<<2],ans[N],a[N],b[N],rt[N];
int n,tot=1;

il int rd() {
    int f=1,sum=0; char ch=G;
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=G;}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=G;}
    return sum*f;
}

il void add_edge(int x,int y) {
    e[++cnt]=edge{head[x],y};
    head[x]=cnt;
}

il ll cal(int id,int x) {
    x-=M;
    return 1ll*s[id].K*x+s[id].B;
}

il void update(int &cur,int l,int r,int cl,int cr,int id) {
    if(!cur) {
        cur=++tot; val[cur]=id; return ;
    }
    int mid=(l+r)>>1,v=val[cur];ll res1=cal(val[cur],mid),res2=cal(id,mid);
    if(l==r) {
        if(res1>res2) val[cur]=id;
        return ;    
    }
    if(s[v].K<s[id].K) {
        if(res1>res2) val[cur]=id,update(rs[cur],mid+1,r,cl,cr,v);
        else update(ls[cur],l,mid,cl,cr,id);
    } else {
        if(res1>res2) val[cur]=id,update(ls[cur],l,mid,cl,cr,v);
        else update(rs[cur],mid+1,r,cl,cr,id);
    }
}

il int merge(int x,int y,int l,int r) {
    if(!x||!y) return x|y;
    if(l==r) {
        return cal(val[x],l)>cal(val[y],l)?y:x;
    }
    int mid=(l+r)>>1;
    ls[x]=merge(ls[x],ls[y],l,mid);
    rs[x]=merge(rs[x],rs[y],mid+1,r);
    update(x,l,r,l,r,val[y]);
    return x;
}

il ll fmin(ll x,ll y) {
    return x<y?x:y;
}
il ll query(int cur,int l,int r,int pos) {
    if(!cur) return inf;
    ll res=cal(val[cur],pos);
    if(l==r) return res;
    int mid=(l+r)>>1;
    if(pos<=mid) return fmin(res,query(ls[cur],l,mid,pos));
    else return fmin(res,query(rs[cur],mid+1,r,pos));
}

il void dfs(int x,int fa) {
    bool fl=1;
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].to;
        if(y^fa) dfs(y,x),rt[x]=merge(rt[x],rt[y],0,M<<1),fl=0;
    }
    if(!fl) f[x]=query(rt[x],0,M<<1,a[x]+M); 
    if(f[x]==inf) f[x]=0;
    s[x].K=b[x]; s[x].B=f[x];
    update(rt[x],0,M<<1,0,M<<1,x);
}

il void pr(int x) {
    if(x<0) {putchar('-');x=-x;}
    if(x>9) pr(x/10);
    putchar(x%10+'0');
}

signed main() {
    int x,y;
    n=rd();
    for(int i=1;i<=n;++i) a[i]=rd();
    for(int i=1;i<=n;++i) b[i]=rd();
    for(int i=1;i<n;++i) {
        x=rd(); y=rd();
        add_edge(x,y); add_edge(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=n;++i) printf("%lld ",f[i]);
    return 0;
}