树
Time Limit : 6000/3000ms (Java/Other) Memory Limit : 524288/524288K (Java/Other)
Total Submission(s) : 3 Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
给一棵根为 $ 1 $ 的有根树，点 $ i $ 具有一个权值 $ A_i $ 。
定义一个点对的值 $ f(u,v) = \max(A_u, A_v) \times |A_u - A_v| $ 。
你需要对于每个节点 $ i $ ，计算 $ ans_i = \sum_{u\in subtree(i), v\in subtree(i)} f(u,v) $ ，其中 $ subtree(i) $ 表示 $ i $ 的子树。
请你输出 $ \oplus (ans_i \mod 2^{64}) $ ，其中 $ \oplus $ 表示 XOR。
定义一个点对的值 $ f(u,v) = \max(A_u, A_v) \times |A_u - A_v| $ 。
你需要对于每个节点 $ i $ ，计算 $ ans_i = \sum_{u\in subtree(i), v\in subtree(i)} f(u,v) $ ，其中 $ subtree(i) $ 表示 $ i $ 的子树。
请你输出 $ \oplus (ans_i \mod 2^{64}) $ ，其中 $ \oplus $ 表示 XOR。
Input
第一行输入一个 $ n $，表示树的节点个数。
接下来 $ n-1 $ 行输入 $ u_i, v_i $，表示树边。
然后输入一行 $n$ 个数字 $ A_i $，表示点 $i$ 的权值。
满足 $n \leq 5 \times 10^5, 1 \leq A_i \leq 10^6$
接下来 $ n-1 $ 行输入 $ u_i, v_i $，表示树边。
然后输入一行 $n$ 个数字 $ A_i $，表示点 $i$ 的权值。
满足 $n \leq 5 \times 10^5, 1 \leq A_i \leq 10^6$
Output
输出一个数字，表示答案。
Sample Input
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
Sample Output
1130
Hint
答案分别是1918 544 416 224 36 0 0 0 80 0
Source
2024“钉耙编程”中国大学生算法设计超级联赛（1）