luogu#P9208. 虚人「无」
虚人「无」
题目背景
一点也不美丽的不死鸟。
那双锐爪,沾染了无辜的鲜血。
题目描述
给定二元序列 和一棵以 为根的有根树。第 个点的点权是 。
- 定义一个非根节点的权值为其子树内的 的积乘上其子树补的 的积。
- 定义一个根节点的权值为其子树内的 的积。
形式化的讲,若 不为根节点,则 的权值 为:
$$f_u=\prod\limits_{v\in \operatorname{substree}(u)} c_v\times \prod\limits_{v\notin \operatorname{substree}(u)} v_v $$否则,其权值 为:
试求整棵树所有节点的权值之和,答案对 取模。请注意:保证 是质数。
输入格式
第一行两个正整数 。
接下来 行,每行两个数 ,表示 之间有一条边。
接下来一行 个数,表示 。
接下来一行 个数,表示 。
输出格式
输出一个数,表示答案对 取模后的结果。
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
提示
样例解释
(图片有误,应该交换 的权值。)
数据范围及约定
对于 的数据,满足 ,。