#PQJ753x4889. QOJ 753_4889
QOJ 753_4889
标题: 愚蠢的在线法官 - Problem - QOJ.ac
#4889. 愚蠢的在线法官
你发现 SOJ,即 Stupid Online Judge,变得越来越愚蠢了,比如 SOJ 并不会做饭而你的狗勾会自己跑到厨房里做四菜一汤。
经过一番探索,你发现 SOJ 愚蠢的原因竟是它内置的在线线性代数求解系统!管理员们由于沉迷于线性代数,整天在研究如何快速计算 2048 阶行列式,从而使得 SOJ 无人维护,甚至还占用了 SOJ 大量的性能。
这个系统里内置了(能在一秒内求解((阶为 114514 秩为 114513 的方阵)的行列式)的程序),本着吃饱了撑着的心理,你决定喂给这个系统若干行列式,但是你并不知道它啥时被你喂撑。为了更好地知道这个系统有没有被搞坏,你决定先自己计算出你提供的问题的答案。
当然管理员们认为他们自己的智商是在线的,所以他们写了一套规则防止这个系统被搞坏,于是你只能以如下的形式上传这个行列式:
- 给系统一棵 n 个点的有根树和每个点的点权 vi,且令根为节点 1,同时传给系统一个长度为 k 的数组 A,构造阶为 k 的方阵 B 其中 bi,j=vLCA(Ai,Aj),即:
B=[vLCA(A1,A1)vLCA(A1,A2)⋯vLCA(A1,Ak)vLCA(A2,A1)vLCA(A2,A2)⋯vLCA(A2,Ak)⋮⋮⋱⋮vLCA(Ak,A1)vLCA(Ak,A2)⋯vLCA(Ak,Ak)]
- 其中 LCA(x,y) 为节点 x 和 y 的最近公共祖先,当你传入数组 A 后,将计算构造出来的这个方阵的行列式。
有了这样一套规则,SOJ 显得更蠢了。由于担心过大的数字会吓坏没见过世面的管理员们,你决定将方阵的值模 998244353 后再给管理员们好好康康。
输入格式
第一行两个正整数 n,k,分别表示树的节点数和 A 的长度。
第二行 n 个非负整数 vi 表示每个点的点权。
第三行 k 个正整数 Ai 表示传给系统的数组。
下面 n−1 行,每行两个正整数 u,v,表示树上的一条无向边 (u,v)。
保证给出的边构成一棵树。
输出格式
一行一个范围在 [0,998244353) 的非负整数,表示答案。
样例一
input
3 2
1 2 3
2 3
1 2
1 3
output
5
explanation
得到的方阵的行列式是
|2113|=2×3−1×1=5
样例二
input
5 1
225348648 810032443 884606707 501975769 428153443
4
1 5
3 5
2 1
4 1
output
501975769
样例三
input
10 5
948691377 65381930 199744893 359204892 47703053 527403959 682504024 581643492 374119650 567695458
5 7 3 8 2
6 3
8 6
10 3
9 3
2 6
1 2
5 3
7 9
4 1
output
141670859
样例四
见下发文件中的 ex_online4.in 与 ex_online4.ans。
该样例满足子任务 3 的性质。
样例五
见下发文件中的 ex_online5.in 与 ex_online5.ans。
该样例满足子任务 4 的性质。
样例六
见下发文件中的 ex_online6.in 与 ex_online6.ans。
该样例满足子任务 6 的性质。
限制与约定
对于所有数据,满足 1≤n,k≤5×105,vi∈[0,998244353),Ai∈[1,n]。
子任务编号 子任务分值 子任务依赖 特殊条件 1 3 无 k>n 2 6 n≤10 3 11 k≤600 4 29 2 n≤3000 5 16 无 A 是 1…n 的排列 6 35 1,3,4,5 无
时间限制:2s
空间限制:512MB