Logo Universal Online Judge

UOJ

时间限制:3 s 空间限制:1024 MB
统计

题目描述

你有一个 $n \times n$ 的矩阵 $M$,下标从 $1$ 开始。

对于 $i \in [1, n], M_{i,i} = c_i$

对于 $i \in [2, n], M_{p_i,i} = a_i, M_{i,p_i} = b_i$

否则 $M_{i,j} = x$ 给定 $a_i, bi, ci, pi, x$,求 $\det(M)$ mod $998244353$。

输入格式

第一行一个数 $T$,表示数据组数。

对于每组数组,第一行两个整数 $n, x$。

然后一行 $n$ 个整数,$c_i$。

然后 $n − 1$ 行,每行三个整数,$p_{i+1}, a_{i+1}, b_{i+1}$。

输出格式

$T$ 行每行一个非负整数,表示答案。

样例1输入

1
3 1
2 3 4
1 4 5
2 6 7

样例1输出

998244269

样例2

见选手目录下 gauss2.in 与 gauss2.ans

数据规模与约定

  • subtask1($20$ pts): $n \le 300$

  • subtask2($20$ pts): $p_i = 1$

  • subtask3($20$ pts): $x = 0$

  • subtask4($40$ pts): 无特殊限制。

对于 $100\%$ 的数据,保证 $1 \le T \le 5, 1 \le n \le 10^6, 1 \le p_i < i, 0 \le x, a_i, b_i, c_i < 998244353$

大样例下载