杀蚂蚁(antbusters)是一款风靡 OI 界的游戏,下面介绍它的一个简单版本。
游戏的地图是一棵 n 个节点的树,其中 1 号点时蚂蚁窝,并且 1 号点只与 2 号点直接相连。
现在有一只蚂蚁拿着蛋糕从树上某个节点 s 出发,按照如下规则随机游走:
- 树上每一个节点 i 都有一定数量的信息素 vi。
- 如果蚂蚁当前位于节点 x,与 x 相邻的节点分别为 y1,y2,⋯,yr,那么蚂蚁下一步走到节点 yi(1≤i≤r)的概率是 vyi∑rk=1vyk。
- 如果蚂蚁在某一步移动结束后位于 1 号点(蚂蚁窝),游戏结束。
现在你有一个攻击装置,这个攻击装置的工作原理是:
- 游戏开始时,你需要选择树上的一条简单路径,这个路径就是该装置的攻击范围,在之后的游戏进程中你不可以改变它。
- 之后在每秒初,如果蚂蚁在这条路径上,则蚂蚁就会被攻击而受到 1 点伤害。
你现在要进行 q 次游戏,每次游戏会给定蚂蚁出生点 s,你想知道,如果在这次游戏中选择 x 号点到 y 号点这条简单路径作为攻击范围,在游戏结束时你对蚂蚁造成伤害的期望值是多少,由于答案非常大而且可能是个分数,你只需要输出答案对 998244353 取模的结果。(如果答案化成最简分数是 xy,那么你要输出 x×y−1mod 的值,其中 y^{-1} 是 y 在模 998\,244\,353 意义下的逆元)。
这里假设蚂蚁的血量是无限的,这意味着蚂蚁走到 1 号点时游戏才会结束。
输入格式
第一行,一个整数 n,表示树的节点数。
接下来一行,有 n 个正整数,第 i 个整数表示 v_i,含义如题面所示。
接下来 n-1 行,每行两个整数 u, v,表示树上的一条连接 u 号点和 v 号点的边。
接下来一行,一个整数 q,表示询问次数。
接下来 q 行,每行三个整数 s, x, y,含义如题面所示。
输出格式
输出共 q 行,每行包含一个整数,第 i 行表示第 i 次询问的答案。
样例数据
样例输入
4
1 1 1 1
1 2
2 3
2 4
1
2 3 4
样例输出
5
子任务
- Subtask 1(10 pts): n \leq 5,v_i = 1,q = 1,s = 2。
- Subtask 2(10 pts): n \leq 100,s = 2。
- Subtask 3(15 pts): v = u + 1,s = 2。
- Subtask 4(15 pts): v = u + 1。
- Subtask 5(20 pts): s = 2。
- Subtask 6(30 pts): 无特殊限制
对于 100\% 的数据,有 n \leq 10^5,q \leq 10^5,\sum_{i=1}^n v_i < 998\,244\,353,v_i \geq 1,2 \leq s, x_i, y \leq n,保证给出的图为一棵树,且 1 号点只与 2 号点直接相连。