树

题目描述

给定一棵以 $1$ 为根的有根树，树上共有 $n$ 个节点，节点从 $1$ 到 $n$ 编号。节点 $i$ 有一个权值 $A_i$。

对于两个节点 $u,v$，定义：

$$f(u,v)=\max(A_u,A_v)\times |A_u-A_v|.$$

对于每个节点 $i$，设 $subtree(i)$ 表示以 $i$ 为根的子树。定义：

$$ans_i=\sum_{u\in subtree(i)}\sum_{v\in subtree(i)} f(u,v).$$

注意，求和中的 $(u,v)$ 是有序点对。因此当 $u\ne v$ 时，$(u,v)$ 和 $(v,u)$ 会分别计算一次；当 $u=v$ 时，贡献为 $0$。

你需要输出：

$$(ans_1 \bmod 2^{64})\oplus(ans_2 \bmod 2^{64})\oplus\cdots\oplus(ans_n \bmod 2^{64}),$$

其中 $\oplus$ 表示按位异或运算。

输入格式

第一行包含一个整数 $n$，表示树的节点个数。

接下来 $n-1$ 行，每行包含两个整数 $u_i,v_i$，表示树上的一条无向边。

最后一行包含 $n$ 个整数 $A_1,A_2,\ldots,A_n$，表示每个节点的权值。

输出格式

输出一行一个整数，表示最终答案。

数据范围

对于所有测试数据，满足：

$$1\le n\le 5\times 10^5,$$ $$1\le A_i\le 10^6.$$

输入保证给出的 $n-1$ 条边构成一棵树。

样例输入

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

样例解释

各节点对应的 $ans_i$ 分别为：

1918 544 416 224 36 0 0 0 80 0

它们对 $2^{64}$ 取模后按位异或，得到：

1130