QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100
[+1]

# 5372. 杀蚂蚁简单版

统计

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

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

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

  1. 树上每一个节点 i 都有一定数量的信息素 vi
  2. 如果蚂蚁当前位于节点 x,与 x 相邻的节点分别为 y1,y2,,yr,那么蚂蚁下一步走到节点 yi1ir)的概率是 vyirk=1vyk
  3. 如果蚂蚁在某一步移动结束后位于 1 号点(蚂蚁窝),游戏结束。

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

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

你现在要进行 q 次游戏,每次游戏会给定蚂蚁出生点 s,你想知道,如果在这次游戏中选择 x 号点到 y 号点这条简单路径作为攻击范围,在游戏结束时你对蚂蚁造成伤害的期望值是多少,由于答案非常大而且可能是个分数,你只需要输出答案对 998244353 取模的结果。(如果答案化成最简分数是 xy,那么你要输出 x×y1mod 的值,其中 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 5v_i = 1q = 1s = 2
  • Subtask 2(10 pts): n \leq 100s = 2
  • Subtask 3(15 pts): v = u + 1s = 2
  • Subtask 4(15 pts): v = u + 1
  • Subtask 5(20 pts): s = 2
  • Subtask 6(30 pts): 无特殊限制

对于 100\% 的数据,有 n \leq 10^5q \leq 10^5\sum_{i=1}^n v_i < 998\,244\,353v_i \geq 12 \leq s, x_i, y \leq n,保证给出的图为一棵树,且 1 号点只与 2 号点直接相连。