Codeforces

Luogu

分析

容易想到一个 DP。设 $dp_u$ 表示 $u$ 跳到叶子节点的最小花费，显然有转移

可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑李超线段树，转移时直接查询对应位置的最小值，然后向上合并即可。
$$
dp_u=\min_{v\in subtree_u}\left\{dp_v+a_u\times b_v\right\}
$$
可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑李超线段树，转移时直接查询对应位置的最小值，然后向上合并即可。

李超线段树合并就是在合并时把另一棵树上每个节点维护的线段插入到合并到的树上对应的节点。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const ll inf=0x3f3f3f3f3f3f3f3f;

int n,a[N],b[N];
vector<int> E[N];

#define ls(o) t[o].ls
#define rs(o) t[o].rs
int rt[N],tot=0;
struct line { int k; ll b; } s[N];
struct node { int ls,rs,id; } t[N*30];
ll f(int i,int x) { return 1ll*s[i].k*x+s[i].b; }
void modify(int& o,int l,int r,int x) {
    if (!o) { o=++tot,t[o].id=x; return; }
    if (l==r) {
        if (f(x,l)<f(t[o].id,l)) t[o].id=x;
        return;
    }
    int mid=(l+r)>>1;
    if (s[x].k<s[t[o].id].k) {
        if (f(x,mid)<f(t[o].id,mid)) modify(t[o].ls,l,mid,t[o].id),t[o].id=x;
        else modify(t[o].rs,mid+1,r,x);
    } else if (s[x].k>s[t[o].id].k) {
        if (f(x,mid)<f(t[o].id,mid)) modify(t[o].rs,mid+1,r,t[o].id),t[o].id=x;
        else modify(t[o].ls,l,mid,x);
    } else if (s[x].b<s[t[o].id].b) t[o].id=x;
}
ll query(int o,int l,int r,int x) {
    if (!o) return inf;
    if (l==r) return f(t[o].id,l);
    int mid=(l+r)>>1; ll res=f(t[o].id,x);
    if (x<=mid) res=min(res,query(ls(o),l,mid,x));
    else res=min(res,query(rs(o),mid+1,r,x));
    return res;
}
int merge(int x,int y,int l,int r) {
    if (!x||!y) return x|y;
    if (l==r) return f(t[x].id,l)<f(t[y].id,l)?x:y;
    int mid=(l+r)>>1;
    ls(x)=merge(ls(x),ls(y),l,mid);
    rs(x)=merge(rs(x),rs(y),mid+1,r);
    modify(x,l,r,t[y].id);
    return x;
}

ll dp[N];
void dfs(int u,int f) {
    if (f&&E[u].size()==1) dp[u]=0;
    else {
        for (int v:E[u])
            if (v!=f) dfs(v,u),rt[u]=merge(rt[u],rt[v],-1e5,1e5);
        dp[u]=query(rt[u],-1e5,1e5,a[u]);
    }
    s[u]=(line){b[u],dp[u]},modify(rt[u],-1e5,1e5,u);
}

int main() {
    n=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=n;++i) b[i]=read();
    for (int i=1;i<n;++i) {
        int u=read(),v=read();
        E[u].emplace_back(v),E[v].emplace_back(u);
    }
    dfs(1,0);
    for (int i=1;i<=n;++i) printf("%lld ",dp[i]); puts("");
    return 0;
}