A5912. 「联合省选 2020 A」树
编程题
省选/NOI-
知识点
题目描述
给定一棵 $n$ 个结点的有根树 $T$，结点从 $1$ 开始编号，根结点为 $1$ 号结点，每个结点有一个正整数权值 $v_i$。
设 $x$ 号结点的子树内（包含 $x$ 自身）的所有结点编号为 $c_1, c_2, \dots, c_k$，定义 $x$ 的价值为：
$$ val(x) = (v_{c_1} + d(c_1, x)) \oplus (v_{c_2} + d(c_2, x)) \oplus \cdots \oplus (v_{c_k} + d(c_k, x)) $$
其中 $d(x, y)$ 表示树上 $x$ 号结点与 $y$ 号结点间唯一简单路径所包含的边数，$d(x, x) = 0$。$\oplus$ 表示异或运算。
请你求出 $\sum_{i=1}^n val(i)$ 的结果。
设 $x$ 号结点的子树内（包含 $x$ 自身）的所有结点编号为 $c_1, c_2, \dots, c_k$，定义 $x$ 的价值为：
$$ val(x) = (v_{c_1} + d(c_1, x)) \oplus (v_{c_2} + d(c_2, x)) \oplus \cdots \oplus (v_{c_k} + d(c_k, x)) $$
其中 $d(x, y)$ 表示树上 $x$ 号结点与 $y$ 号结点间唯一简单路径所包含的边数，$d(x, x) = 0$。$\oplus$ 表示异或运算。
请你求出 $\sum_{i=1}^n val(i)$ 的结果。
输入格式
第一行一个正整数 $n$ 表示树的大小。
第二行 $n$ 个正整数表示 $v_i$。
接下来一行 $n-1$ 个正整数，依次表示 $2$ 号结点到 $n$ 号结点，每个结点的父亲编号 $p_i$。
第二行 $n$ 个正整数表示 $v_i$。
接下来一行 $n-1$ 个正整数，依次表示 $2$ 号结点到 $n$ 号结点，每个结点的父亲编号 $p_i$。
输出格式
仅一行一个整数表示答案。
输入输出样例
输入 #1
5 5 4 1 2 3 1 1 2 2
输出 #1
12
说明/提示
$10\%$ 的数据：$1\le n\le 2501$。
$40\%$ 的数据：$1\le n\le 152501$。
另有 $20\%$ 的数据：所有 $p_i = i - 1 (2\le i\le n)$。
另有 $20\%$ 的数据：所有 $v_i = 1 (1\le i\le n)$。
$100\%$ 的数据：$1\le n, v_i \le 525010, 1\le p_i\le n$。
$40\%$ 的数据：$1\le n\le 152501$。
另有 $20\%$ 的数据：所有 $p_i = i - 1 (2\le i\le n)$。
另有 $20\%$ 的数据：所有 $v_i = 1 (1\le i\le n)$。
$100\%$ 的数据：$1\le n, v_i \le 525010, 1\le p_i\le n$。