#6509. 「雅礼集训 2018 Day7」C

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定一棵 nn 个点的树,树上每个点初始有一个 0011 的数字。

考虑这样一个过程:

  1. 等概率随机选择一个点作为起点
  2. 等概率随机选择一个新点并沿着树上的路径移动过去,最后反转这个新点上的数字(注意只反转这个新点上的数字而非经过的所有点的数字)
  3. 如果此时整棵树上的所有数字相同,则过程结束;否则回到步骤 22

求出期望的移动距离,对 109+710^9 + 7 取模。

输入格式

第一行一个整数 nn

第二行一个长度为 nn0101 串,表示每个点的初始数字。

接下来 n1n - 1 行,其中第 ii 行一个整数 ff 表示一条连接 i+1i + 1ff 的边。

输出格式

一行一个整数表示答案。

样例

样例输入 1

2
01
1

样例输出 1

500000004

样例解释 1

  • 初始点为 11,选择的新点为 11,过程结束,距离为 00
  • 初始点为 11,选择的新点为 22,过程结束,距离为 11
  • 初始点为 22,选择的新点为 22,过程结束,距离为 00
  • 初始点为 22,选择的新点为 11,过程结束,距离为 11

答案为 12\frac{1}{2},对 109+710 ^ 9 + 7 取模等于 500000004500000004

样例输入 2

3
001
1
1

样例输出 2

638888896

样例解释 2

一种可能的方案如下:

  1. 22 号点出发,选择了 22 号点自己,这一步的移动步数为 0022 号点数字变为 11
  2. 选择 33 号点,这一步的移动步数为 2233 号点数字变为 00
  3. 选择 22 号点,这一步的移动步数为 2222 号点数字变为 00
  4. 此时所有点均变为 00,过程结束,总移动步数为 44

最终答案为 9536\frac{95}{36},对 109+710^9 + 7 取模等于 638888896638888896

数据范围与提示

对于全部数据, 3n1000003 \leq n \leq 100000,保证初始局面不满足终止条件。

  • 存在 10%10 \%的数据, n5n \leq 5
  • 存在 30%30 \%的数据, n20n \leq 20
  • 存在 50%50 \%的数据, n100n \leq 100
  • 存在 70%70 \%的数据, n1000n \leq 1000