#P6901. 吃粮

    ID: 6732 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-期望线性性随机游走期望方程行列式树形 DP前后缀合并排除子节点模逆元增量维护

吃粮

题目描述

给定一棵以 11 为根的无向树。你从 11 出发,每次到达点 xx 时先等待 axa_x 秒。如果该点的度数为 11,等待后结束。否则,等概率选择一个邻点走过去。初次处在根时也要等待。经过边本身不另计时间。

有 QQ 次修改。每次将指定点 uu 的等待时间替换为 yy。求修改前和每次修改后,从根出发直到结束所用时间的期望。

输入格式

第一行一个整数 nn。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。接下来 n−1n-1 行,每行两个整数 u,vu,v,描述一条无向边。

接下来一行一个整数 QQ,再接下来 QQ 行,每行两个整数 u,yu,y,表示将 aua_u 改为 yy。

输出格式

输出 Q+1Q+1 行。第一行为初始期望,之后每行为一次修改后的期望。各答案对 998244353998244353 取模。

样例

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

数据范围

保证树至少有一个度数为 11 的结点,且根的度数不为 11,因此 3≤n≤1053\le n\le10^5。1≤Q≤1051\le Q\le10^5,所有等待时间(含修改后的值)满足 1≤ai,y<9982443531\le a_i,y<998244353。

测试点 nn、QQ 的上界
1–4 100
5–8 300
9–12 1000
13–20 100000

本站评测使用的树满足以下可逆条件。取原树中所有度数大于 11 的点作为行列下标,构造矩阵 LL。对角项为各点在原树中的度数,两个不同点相邻时矩阵项为 −1-1,否则为 00。本站评测保证 detLdet L 不被 998244353998244353 整除,因此题目所要求的每个期望均可按有理数取模。此条件是根据本站全部评测输入补充的,原 PDF 保留在下方。

By Anoxx。原题面 PDF