Escape Through Leaf

题面

有一颗 $n$ 个节点的树（节点从 $1$ 到 $n$ 依次编号），根节点为 $1$ 。每个节点有两个权值，第 $i$ 个节点的权值为 $a_i,b_i$ 。

你可以从一个节点跳到它的子树内任意一个节点上。从节点 $x$ 跳到节点 $y$ 一次的花费为 $a_x\times b_y$ 。跳跃多次走过一条路径的总费用为每次跳跃的费用之和。请分别计算出每个节点到达树的每个叶子节点的费用中的最小值。

注意：就算根节点的度数为 $1$ ，根节点也不算做叶子节点。另外，不能从一个节点跳到它自己.

$2\leq n\leq 10^5$ ， $-10^5\leq a_i\leq 10^5$ ， $-10^5\leq b_i\leq 10^5$ 。

题解

设 $f_{x,y}$ 为从 $x$ 号节点到达 $i$ 号叶子节点的最小费用。

$$f_{x,i}=\min_{y \in \text{subtree}(x)} \{f_{y,i}+a_x\times b_y\} $$

当 $y$ 的值固定的时候，这个式子其实就是 $kx+b$ ，于是可以使用李超线段树来维护。在树上合并答案就李超线段树合并。

代码

const int N = 1e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	int a[N], b[N];
	ll f[N];
	
	int head[N], tot;
	struct Edge {
		int to, next;
	} e[N << 1];
	void Add (int u, int v) {
		e[++tot] = (Edge) {v, head[u]}, head[u] = tot;
	}

	struct Line {
		ll k, b;
		int id;
		Line(ll k = 0, ll b = 0, int id = 0): k(k), b(b), id(id) {}
		ll calc(int x) { return k * x + b; }
		ll cross (Line T) { return (T.b - b) / (k - T.k); }
	};

	struct LCST {
		struct Tree {
			Line L;
			int l, r;
		} t[N << 4];
		int root [N * 20];
		int tot;
		void Insert (int &p, int l, int r, Line val) {
			if (!p) p = ++tot;
			int mid = (l + r) >> 1;
			if (t[p].L.calc(mid) > val.calc(mid) || !t[p].L.id) swap(t[p].L, val);
			if (l == r || t[p].L.k == val.k || !val.id) return;
			ll x = t[p].L.cross(val);
			if (x < l || x > r) return;
			if (val.k > t[p].L.k) Insert (t[p].l, l, mid, val);
			else Insert (t[p].r, mid + 1, r, val);
			return;
		}
		int Merge (int p, int q, int l, int r) {
			if (!p || !q) return p + q;
			Insert (p, l, r, t[q].L);
			int mid = (l + r) >> 1;
			t[p].l = Merge(t[p].l, t[q].l, l, mid);
			t[p].r = Merge(t[p].r, t[q].r, mid + 1, r);
			return p;
		}
		Line Query (int p, int l, int r, int x) {
			if (l == r) return t[p].L;
			int mid = (l + r) >> 1;
			Line ans;
			if (mid >= x) ans = Query (t[p].l, l, mid, x);
			else ans = Query (t[p].r, mid + 1, r, x);
			if (!ans.id || t[p].L.calc(x) < ans.calc(x)) return t[p].L;
			return ans;
		}
	} st;

	void dfs (int u, int fa) {
		for (int i = head[u]; i; i = e[i].next) {
			int v = e[i].to;
			if (v == fa) continue;
			dfs (v, u);
			st.root[u] = st.Merge(st.root[u], st.root[v], -1e5, 1e5);
		}
		int x = st.Query (st.root[u], -1e5, 1e5, a[u]).id;
		f[u] = 1ll * a[u] * b[x] + f[x];
		st.Insert (st.root[u], -1e5, 1e5, Line(b[u], f[u], 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();
			Add (u, v), Add(v, u);
		}
		dfs(1, 0);
		for (int i = 1; i <= n; i++) printf ("%lld ", f[i]);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}