题目描述

给一棵根为 $1$ 的有根树，点 $i$ 具有一个权值 $A_i$。

定义一个点对的值 $f(u,v)=\max (A_u,A_v)\times |A_u-A_v|$ 。

你需要对于每个节点 ，计算 $ans_i=\sum\limits_{u\in subtree(i),v\in subtree(i)}f(u,v)$，其中 $subtree(i)$ 表示 $i$ 的子树。

请你输出 $\bigoplus(ans_i\ \text{mod}\ 2^{64})$ ，其中 $\bigoplus$ 表示 XOR。

输入格式

第一行输入一个 $n$ ，表示树的节点个数。

接下来 $n - 1$ 行输入 $u_i,v_i$，表示树边。

然后输入一行 $n$ 个数字 $A_i$，表示点 $i$ 的权值。

满足 $n \le 5 \times 10^5,1\le A_i \le 10^6$。

输出格式

输出一个数字，表示答案。

输入样例

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

输出样例

1130

提示

答案分别是$1918,544,416,224,36,0,0,0,80,0$。