QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100
统计

杀蚂蚁(antbusters)是一款风靡 OI 界的游戏,下面介绍它的一个简单版本。

游戏的地图是一棵 $n$ 个节点的树,其中 $1$ 号点时蚂蚁窝,并且 $1$ 号点只与 $2$ 号点直接相连。

现在有一只蚂蚁拿着蛋糕从树上某个节点 $s$ 出发,按照如下规则随机游走:

  1. 树上每一个节点 $i$ 都有一定数量的信息素 $v_i$。
  2. 如果蚂蚁当前位于节点 $x$,与 $x$ 相邻的节点分别为 $y_1, y_2, \cdots, y_r$,那么蚂蚁下一步走到节点 $y_i$($1 \leq i \leq r$)的概率是 $\displaystyle \frac{v_{y_i}}{\sum_{k=1}^r v_{y_k}}$。
  3. 如果蚂蚁在某一步移动结束后位于 $1$ 号点(蚂蚁窝),游戏结束。

现在你有一个攻击装置,这个攻击装置的工作原理是:

  1. 游戏开始时,你需要选择树上的一条简单路径,这个路径就是该装置的攻击范围,在之后的游戏进程中你不可以改变它。
  2. 之后在每秒初,如果蚂蚁在这条路径上,则蚂蚁就会被攻击而受到 $1$ 点伤害。

你现在要进行 $q$ 次游戏,每次游戏会给定蚂蚁出生点 $s$,你想知道,如果在这次游戏中选择 $x$ 号点到 $y$ 号点这条简单路径作为攻击范围,在游戏结束时你对蚂蚁造成伤害的期望值是多少,由于答案非常大而且可能是个分数,你只需要输出答案对 $998\,244\,353$ 取模的结果。(如果答案化成最简分数是 $\displaystyle \frac xy$,那么你要输出 $x \times y^{-1} \bmod 998\,244\,353$ 的值,其中 $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$ 号点直接相连。