样例下载

题目描述

有一棵树，包含 $n$ 个结点，编号为 $1$ ~ $n$。其中 $1$ 号点为根节点。

每个节点上挂着一个盲盒，摘取盲盒会获得一定的价值，对于编号为 $i$ 的节点，摘取该节点上的盲盒会获得 $V_i$ 的价值。注意：$V_i$ 可能为负数。

小明要从 $1$ 号点出发，经过若干个点后，最终再回到 $1$ 号点。在中间过程中，可以无限次经过 $1$ 号点。但其他非根节点则有经过次数的限制，对于编号为 $i (1 < i ≤ n)$ 的节点，经过次数不得超过 $T_i$。多次经过同一个节点 $i$，只会获得一次 $V_i$ 的价值。

小明想知道他如何选择路线，可以获得的总价值最大。并且他想知道有多少条路线可以使得他获得最大总价值。

注意：

（1）小明在根节点一直不动，也算一条路线；

（2）两条路线不同，当前仅当经过的节点的集合不同，与经过顺序无关。

你能帮助他吗？

输入格式

第一行：一个整数 $n$。

第二行：$n$ 个整数 $V_i$。数据保证 $V_1=0$；并且 $|V_i| < 10^9 (1 < i ≤ n)$

第三行：$n$ 个整数 $T_i$。数据保证 $T_1=0$，表示根节点无经过次数限制；并且 $T_i ≥ 2 (1 < i ≤ n)$。

接下来的 $n-1$ 行：每行两个整数 $u, v$, 表示节点 $u$ 和节点 $v$ 之间有一条树边。

输出格式

共两行。

第一行：一个整数，表示小明可以获得的最大总价值。

第二行：如果路线唯一，输出 yes, 否则输出 no。

输入样例

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

输出样例

9
yes

样例说明

经过节点集合为 { $1,2,4,5,9$ }。

数据范围

100% 的数据：$5 ≤ n ≤ 10^5$。