#P6901. 吃粮
吃粮
题目描述
给定一棵以 为根的无向树。你从 出发,每次到达点 时先等待 秒。如果该点的度数为 ,等待后结束。否则,等概率选择一个邻点走过去。初次处在根时也要等待。经过边本身不另计时间。
有 次修改。每次将指定点 的等待时间替换为 。求修改前和每次修改后,从根出发直到结束所用时间的期望。
输入格式
第一行一个整数 。第二行 个整数 。接下来 行,每行两个整数 ,描述一条无向边。
接下来一行一个整数 ,再接下来 行,每行两个整数 ,表示将 改为 。
输出格式
输出 行。第一行为初始期望,之后每行为一次修改后的期望。各答案对 取模。
样例
5
3 2 1 4 6
1 2
1 3
2 4
2 5
3
1 100
3 23
4 234
199648878
399297865
137
183
数据范围
保证树至少有一个度数为 的结点,且根的度数不为 ,因此 。,所有等待时间(含修改后的值)满足 。
| 测试点 | 、 的上界 |
|---|---|
| 1–4 | 100 |
| 5–8 | 300 |
| 9–12 | 1000 |
| 13–20 | 100000 |
本站评测使用的树满足以下可逆条件。取原树中所有度数大于 的点作为行列下标,构造矩阵 。对角项为各点在原树中的度数,两个不同点相邻时矩阵项为 ,否则为 。本站评测保证 不被 整除,因此题目所要求的每个期望均可按有理数取模。此条件是根据本站全部评测输入补充的,原 PDF 保留在下方。
By Anoxx。原题面 PDF