3736: 爬(第一轮02)
题目描述
鸡尾酒很喜欢让别人爬，于是他种了一棵树。然后在树上放了 n 只蚂蚁，看它 们爬。
树上有 n 个点，用 n − 1 条边相连， 除了根结点外，每个结点都有父亲，根结 点记为 1 号结点，其它结点分别编号为 2 ~ n 。n 个点上分别放有一只蚂蚁， 并且每只蚂蚁有一个属性 ai，除了根节点的蚂蚁之外，每只蚂蚁都可以选择向 上爬到父亲结点或者不爬（只能爬一次）。在所有蚂蚁都选择完毕之后，我们统 计这些蚂蚁产生的快乐值：如果多只蚂蚁在同一点，则产生这些蚂蚁属性的异或 和的快乐值。如果某个点上只有一只蚂蚁或者没有蚂蚁，则不产生快乐值。问所 有方案的所有快乐值之和。
由于答案很大，你只需要输出答案对 109 + 7 取模之后的结果就可以了。
输入
第一行输入一个正整数 n，表示树的点数。
接下来一行输入 n 个正整数 ai ，分别表示每一只蚂蚁的属性。
接下来一行输入 n − 1 个正整数，分别表示 2 ~ n 号结点的父亲结点编号。
输出
输出一行一个整数表示答案对 10^9 + 7 取模后的结果。
样例输入 复制
3
1 2 4
1 2样例输出 复制
12提示
【样例 1 输入】
3
1 2 4
1 2
【样例 1 输出】
12
【样例 1 说明】
树呈一条链，二号结点的父亲是一号结点，三号结点的父亲是二号结点。1， 2， 3 号结点蚂蚁的属性值分别为 1、2、4。这些蚂蚁共有 4 种爬的方案：
方案 1： [{1,2}, { }, {4}] 表示第一个结点有属性值为 1， 2 的两只蚂蚁，第二个 结点无蚂蚁，第三个结点有属性值为 4 的一只蚂蚁。本方案的快乐值为 1 。 2 = 3，其中 。 表示异或。
方案 2： [{1,2}, {4}, { }]，本方案的快乐值为 3。
方案 3： [{1}, {2}, {4}]，没有结点上有大于等于两只蚂蚁，所以快乐值为 0。
方案 4： [{1}, {2,4}, { }]，快乐值为 2 。4 = 6
所有方案的快乐值之和为 3 + 3 + 0 + 6 = 12。
【样例 2 输入】
3
1 2 2
1 1
【样例 2 输出】
7
【样例 2 说明】
方案 1： [{1}, {2}, {2}]
方案 2： [{1,2}, {2}, { }]
方案 3： [{1,2}, { }, {2}]
方案 4： [{1,2,2}, { }, { }]
所有方案的快乐值之和为 0 + 3 + 3 + 1 = 7
【样例 3 输入】
5
0 1 0 2 2
1 1 2 2
【样例 3 输出】
22
【样例 4 输入】
4
1 1 1 0
1 2 2
【样例 4 输出】
2
【数据范围】
本题共有 10 个测试点
对于 1 测试点，有 1 ≤ n ≤ 20
对于 2 − 3 测试点，有 1 ≤ n ≤ 1000
对于 4 测试点，树是一条链
对于 5 − 6 测试点，树是一个二叉树
对于 7 −10 测试点，树的形态无特殊限制， 1 ≤ n ≤ 105 ,0 ≤ ai ≤ 109