Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:256 MB
统计

【题目描述】

阿龙要在学校里建饭堂。学校可以看成一棵 $n$ 个点的树,阿龙要在至少一个点上建饭堂,在第 $i$ 个点上建饭堂会有 $a_i$ 的花费。

学校的每个点处都有学生。对于每个点 $u$,记离 $u$ 最近的饭堂到 $u$ 的距离为 $d(u)$,那么 $u$ 点处的学生就会根据 $d(u)$ 给出他们付给阿龙的贡金 $b_{d(u)}$。

阿龙当然希望获得的收益最大,而非顾及到所有学生的感受。所以他想让你帮他求出,使得收益最大的建造方案的收益是多少,此处的收益指的是阿龙收到的贡金之和减去阿龙建饭堂所消耗的费用之和。

【输入格式】

从标准输入读入数据。 输入数据的第一行包含一个整数 $n$。 第二行包含 $n$ 个整数 $a_1\dots a_n$。 第三行包含 $n$ 个整数 $b_0\dots b_{n-1}$。 接下来 $n-1$ 行,第 $i$ 行包含两个整数 $u_i,v_i$,表示树的第 $i$ 条边。

【输出格式】

输出到标准输出。 输出一行一个整数表示答案。

【样例输入】

3
1 3 2
2 1 0
1 2
2 3

【样例输出】

2

【数据范围】

子任务编号 分值 限制
1 12 $n\le 18$
2 13 $u_i=i=v_i=i+1$
3 15 $u_i=1,v_i=i+1$
4 27 $n\le 200$
5 33 无特殊限制

大样例