时空限制

2S/512M

题目描述

有 $n$ 座观测塔，由 $n-1$ 条双向道路连接成一棵树。第 $i$ 座观测塔的高度为 $h_i$，并保存着价值为 $w_i$ 的一份数据。所有观测塔的高度互不相同。

选择两座不同的观测塔作为接收站。对于观测塔 $u$ 和接收站 $v$，当且仅当 $u$ 是 $u$ 到 $v$ 的简单路径上最高的观测塔时，观测塔 $u$ 的数据能被接收站 $v$ 完整接收。特别地，每座接收站都能完整接收自身保存的数据。

若一份数据能被至少一座接收站完整接收，则获得其价值；同一份数据的价值只被计算一次。

求合理选择两座接收站后，能够获得的最大价值总和。

格式

输入格式

第一行包含一个整数 $n$，表示观测塔的数量。

第二行包含 $n$ 个整数 $h_1,h_2,\ldots,h_n$，表示每座观测塔的高度。

第三行包含 $n$ 个整数 $w_1,w_2,\ldots,w_n$，表示每座观测塔中数据的价值。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示观测塔 $u$ 与观测塔 $v$ 之间有一条双向道路。

输出格式

输出一个整数，表示能够获得的最大价值总和。

样例

样例输入 #1

7
7 4 6 1 3 5 2
4 8 5 6 3 7 9
1 2
1 3
2 4
2 5
3 6
3 7

样例输出 #1

32

样例解释 #1

选择观测塔 $4$ 和观测塔 $7$ 作为接收站。能够被完整接收的数据来自观测塔 $1,2,3,4,7$，其价值总和为 $4+8+5+6+9=32$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

特殊性质 A：对于每个 $1\le i<n$，观测塔 $i$ 与观测塔 $i+1$ 之间有一条道路。

对于 $100\%$ 的数据，满足 $2\le n\le2\times10^5$，$1\le h_i\le n$，$1\le w_i\le10^9$，所有 $h_i$ 两两不同，$1\le u,v\le n$，$u\ne v$，且输入的道路构成一棵树。