随机游走(wander)

Kujou Kawaii 特别喜欢在树上随机游走。这一棵树很特殊，他每一条边有长度。

现在 Kujo Kawaii 站在 $S$ 号节点上。每一次她会等概率的随机游走到一个与其相邻的节点。

Kujou Kawaii 觉得走很长的路会很累，她定义长度为 $x$ 的道路的疲劳值为 $f(x)$，其中 $f(x)=\sum_{i=1}^ma_ix^i$。

Kujou Kawaii 想要知道，如果她从 $S$ 出发，走到 $T$，疲劳值的期望大小。

由于答案可能很复杂，Kujou Kawaii 只想知道答案对 $998244353$ 取模的结果。

Kujou Kawaii 是一个好奇的女孩子，于是她会有 $Q$ 次不同的询问。

第一行三个正整数 $n,m,Q$ 。

第二行一行 $m+1$ 个非负整数，第 $i$ 个非负整数表示 $a_{i-1}$

接下来 $n-1$ 行，第 $i$ 行有三个数字 $x_i,y_i,v_i$，表示一条连接 $x_i,y_i$，权值为 $v_i$ 的边。

接下来 $Q$ 行，一行两个元素 $S,T$，表示一次询问。

$Q$ 行，第 $i$ 行一个整数表示答案对 $998244353$ 取模的结果。

32
35

测试点 $1 \sim 2$: $n \le 3$

测试点 $3 \sim 5$: $n \le 10,m = 1,a_0 = 0,a_1 = 1$

测试点 $6 \sim 8$: $n \le 50,m = 1,a_0 = 0,a_1 = 1$

测试点 $9 \sim 11$: $n \le 2000,m = 1,a_0 = 0,a_1 = 1$

测试点 $12 \sim 14$: $m = 1,a_0 = 0,a_1 = 1$

测试点 $15 \sim 17$: $m = 1$

测试点 $18 \sim 20$: $1 \le n \le 50$

测试点 $21 \sim 23$: $1 \le n \le 2000$

测试点 $24 \sim 25$: 无特殊限制。

对于所有测试数据，满足 $1 \le n \le 1 \times 10^5,1 \le Q \le min\{n^2,10^5\},1 \le m \le 10$。

对于所有测试数据，满足 $1 \le S,T \le n,1 \le a_i,v_i < 998244353$

时间限制：$\texttt{2s}$

空间限制：$\texttt{512MB}$

Universal Online Judge