分析

我们可以先写出暴力转移方程 表示 节点到子树中某个叶子节点的最小代价。那么转移方程为 可以看出这个是类似 的直线方程的，但是斜率并不单调，所以考虑李超线段树，但是从一个子树转移到另一个子树不能暴力转移，否则时间复杂度为 。所以我们考虑线段树合并，处理完子树后进行线段树合并。这样时间复杂度为 ，有大佬通过势能分析，时间复杂度为 。最后跑的还是挺快。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const LL N = 2e6 + 100,M = 1e5,inf = 0x3f3f3f3f3f3f3f3f;
LL a[N],b[N],n,f[N];
LL t[N],lc[N],rc[N],size,rt[N];
LL read() {LL x;scanf("%lld",&x);return x;}
LL g(LL x,LL p) {return b[x] * p + f[x];}
vector<LL> G[N];
void insert(LL &u,LL l,LL r,LL id) {
    if(!u) {u = ++size;t[u] = id;return;}
    LL mid = l + r >> 1;
    LL val_l = g(t[u],l),val_r = g(t[u],r),val_L = g(id,l),val_R = g(id,r);
    if(!t[u] || val_R <= val_r && val_L <= val_l) {t[u] = id;return;}
    if(val_l <= val_L && val_r <= val_R) {return;}
    insert(lc[u],l,mid,id);insert(rc[u],mid+1,r,id);
}
LL ask(LL u,LL l,LL r,LL p) {
    if(!u) return inf;
    if(l == r) {return g(t[u],p);}
    LL ans = g(t[u],p);LL mid = l + r >> 1;
    if(p <= mid) return min(ans,ask(lc[u],l,mid,p));
    else return min(ans,ask(rc[u],mid+1,r,p));
}
LL merge(LL x,LL y,LL l,LL r) {
    if(!x || !y) return x|y;
    int mid = l + r >> 1;
    insert(x,l,r,t[y]);
    lc[x] = merge(lc[x],lc[y],l,mid);rc[x] = merge(rc[x],rc[y],mid+1,r);
    return x;
}
void solve(LL x,LL fa) {
    int son = 0;
    for(auto y:G[x]) {
        if(y == fa) continue;
        solve(y,x);
        rt[x] = merge(rt[x],rt[y],-M,M);
    }
    f[x] = ask(rt[x],-M,M,a[x]);
    if(f[x] == inf) f[x] = 0;
    insert(rt[x],-M,M,x);
}
int main() {
    n = read();f[0] = inf;
    for(LL i = 1;i <= n;i++) a[i] = read();
    for(LL i = 1;i <= n;i++) b[i] = read();
    for(LL i = 1;i < n;i++) {
        LL a = read(),b = read();
        G[a].push_back(b);G[b].push_back(a);
    }
    solve(1,0);
    for(LL i = 1;i <= n;i++) printf("%lld ",f[i]);
    printf("\n");
}