题解

题目描述

小红拿到一棵节点总数为 $n$ 的树，编号为 $1$ ~ $n$，保证 $n$ 为奇数。

其中每个点的点权为 $a_i$，附属代价为 $b_i$。

每次操作，小红可以选择一个树上的连通块，再选择连通块中的一个节点，将其点权 $+1$ 或者 $-1$，代价为连通块中所有节点的附属代价之和。

题目内容

小红拿到一棵节点总数为 $n$ 的树，编号为 $1$ ~ $n$，保证 $n$ 为奇数。

其中每个点的点权为 $a_i$，附属代价为 $b_i$。

每次操作，小红可以选择一个树上的连通块，再选择连通块中的一个节点，将其点权 $+1$ 或者 $-1$，代价为连通块中所有节点的附属代价之和。

小红想知道在最少操作次数的前提下，最少需要多少代价，才能将所有节点的点权变为相同(代价可以是负数)。

此题中的连通块定义为：对于树上的任意一个点集 $S$，如果 $S$ 中的任意两点 $u,v$ 之间存在一条路径，且路径上的所有点都在 $S$ 中，则称 $S$ 是一个连通块。

输入描述

第一行一个整数 $n(1 \leq n < 10^5$ 且 $n$ 为奇数$)$，表示树的节点总数。

第二行 $n$ 个整数，表示每个节点的点权 $a_i(1\leq a_i\leq 100)$。

第三行 $n$ 个整数，表示每个节点的附属代价 $b_i(-100 \leq b_i\leq 100)$。

按下来 $n - 1$ 行，每行两个整数 $u,v(1 \leq u,v \leq n,u ≠ v)$，表示树上的一条边。

输出描述

一个整数，表示最少操作次数的前提下，需要的最少代价。

示例1

输入

3
1 3 4
-5 2 3
1 2
1 3

输出

-12

说明

选择连通块 { $1$ } 的结点 $1$ 操作两次 $+1$，代价为 $-10$，此时 $a_1 = 3$。

选择连通块 { $1,3$ } 的结点 $3$ 操作一次 $-1$，代价为 $-2$，此时 $a_3 = 3$。

代价之和为 $-12$。

可以证明这样的操作是最少操作次数下的最少代价。