← 返回题目
题库练习 「雅礼集训 2018 Day7」C
← 上一题 下一题 →

A6659 | 「雅礼集训 2018 Day7」C

时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

给定一棵 $n$ 个点的树，树上每个点初始有一个 $0$ 或 $1$ 的数字。

考虑这样一个过程：

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

求出期望的移动距离，对 $10^9 + 7$ 取模。

输入格式

第一行一个整数 $n$。

第二行一个长度为 $n$ 的 $01$ 串，表示每个点的初始数字。

接下来 $n - 1$ 行，其中第 $i$ 行一个整数 $f$ 表示一条连接 $i + 1$ 和 $f$ 的边。

输出格式

一行一个整数表示答案。

输入输出样例

输入 #1
2
01
1
输出 #1
500000004
输入 #2
3
001
1
1
输出 #2
638888896
C++ 编辑器
输入
输出