有一颗 \(n\) 个节点的树，根节点为 \(1\)。每个节点有两个权值，第 \(i\) 个节点的权值为 \(a_i,b_i\)。
你可以从一个节点跳到它的子树内任意一个节点上。从节点 \(x\) 跳到节点 \(y\) 一次的花费为 \(a_x\times b_y\)。跳跃多次走过一条路径的总费用为每次跳跃的费用之和。求每个节点到达树的任意叶子节点的费用的最小值。
\(2 \le n \le 10^5\)，\(-10^5 \le a_i,b_i \le 10^5\)。
比较板一个题。首先显然有 \(\mathcal{O}(n^2)\) DP：设 \(f_u\) 为从 \(u\) 出发的答案，则 \(f_u = \min\limits_{v \in T_u} \{ f_v + a_u \times b_v \}\)，其中 \(T_u\) 表示 \(u\) 的子树。然后这个式子一看就是一次函数的形式，直接上李超树。合并子树的时候李超树合并就行了。注意一下李超树合并是 单 \(\log\) 的。
这题定义域有负数，可以平移一下。但其实也不是必要的。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
#define all(x) x.begin(), x.end()
constexpr int N = 2e5 + 5, M = 1e5 + 5;
constexpr LL inf = 1e18;
bool Mbe;
int n, root[N], tot;
vector <int> e[N];
LL ans[N], a[N], b[N];
int lc[N << 5], rc[N << 5], p[N << 5];
struct line {
LL k, b;
} t[N];
inline LL calc(int i, LL x) { return t[i].k * x + t[i].b; }
#define m ((l + r) >> 1)
void insert(int &x, int l, int r, int id) {
if (!x) return x = ++tot, p[x] = id, void();
if (calc(p[x], m) > calc(id, m)) swap(p[x], id);
if (calc(p[x], l) <= calc(id, l) &&
calc(p[x], r) <= calc(id, r)) return;
if (calc(p[x], l) > calc(id, l)) insert(lc[x], l, m, id);
else insert(rc[x], m + 1, r, id);
}
LL qry(int x, int l, int r, LL pos) {
if (!x) return inf;
LL res = calc(p[x], pos);
if (pos <= m) res = min(res, qry(lc[x], l, m, pos));
else res = min(res, qry(rc[x], m + 1, r, pos));
return res;
}
int merge(int x, int y, int l, int r) {
if (!x || !y) return x + y;
insert(x, l, r, p[y]);
lc[x] = merge(lc[x], lc[y], l, m);
rc[x] = merge(rc[x], rc[y], m + 1, r);
return x;
}
void dfs(int u, int fa) {
for (auto v : e[u]) {
if (v == fa) continue;
dfs(v, u);
root[u] = merge(root[u], root[v], 1, N);
}
ans[u] = qry(root[u], 1, N, a[u] + M);
if (ans[u] == inf) ans[u] = 0;
t[u] = { b[u], ans[u] - b[u] * M };
insert(root[u], 1, N, u);
}
#undef m
void mian() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
}
bool Med;
int main() {
// fprintf(stderr, "%.9lfMb\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
while (t--) mian();
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}