luogu#P9208. 虚人「无」

虚人「无」

题目背景

一点也不美丽的不死鸟。

那双锐爪,沾染了无辜的鲜血。

题目描述

给定二元序列 {(vi,ci)}\{(v_i,c_i)\} 和一棵以 11 为根的有根树。第 ii 个点的点权是 (vi,ci)(v_i,c_i)

  • 定义一个非根节点的权值为其子树内的 cc 的积乘上其子树补的 vv 的积。
  • 定义一个根节点的权值为其子树内的 cc 的积。

形式化的讲,若 uu 不为根节点,则 uu 的权值 fuf_u 为:

$$f_u=\prod\limits_{v\in \operatorname{substree}(u)} c_v\times \prod\limits_{v\notin \operatorname{substree}(u)} v_v $$

否则,其权值 fuf_u 为:

fu=v=1ncvf_u=\prod\limits_{v=1}^n c_v

试求整棵树所有节点的权值之和,答案对 mm 取模。请注意:保证 m\bm m 是质数

输入格式

第一行两个正整数 n,mn,m

接下来 n1n-1 行,每行两个数 u,vu,v,表示 u,vu,v 之间有一条边。

接下来一行 nn 个数,表示 c1,2,,nc_{1, 2, \dots, n}

接下来一行 nn 个数,表示 v1,2,,nv_{1, 2, \dots, n}

输出格式

输出一个数,表示答案对 mm 取模后的结果。

3 998244853
1 2
1 3
2 1 2
1 2 2
10
5 998244353
1 2
1 3
1 4
4 5
5 5 5 2 3
6 6 1 5 3
4656

提示

样例解释

(图片有误,应该交换 v,cv,c 的权值。)

数据范围及约定

对于 100%100\% 的数据,满足 1n3×1051\le n\leq 3\times 10^51vi,ci,m1091\leq v_i,c_i,m\leq 10^9