E-交换（Hard Version）_牛客练习赛152

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 本题与《D.交换（Easy Version）》共享部分题目背景，但是求解的内容不同。共享部分我们使用特殊的格式标注。

〖引用开始〗

$\hspace{15pt}$ 给定一棵以 $1$ 为根的树，共有 $n$ 个节点（编号为 $1$ 到 $n$ ），每个节点 $i$ 有两个值，分别是权值 $a_i$ 与限制 $s_i$ ，且为 $0$ 或 $1$ 。
$\hspace{15pt}$ 现在你可以执行以下操作任意次（也可以不执行）：
$\hspace{23pt}\bullet\,$ 选择一条父子边 $(p, u)$ （其中 $p$ 是 $u$ 的父亲），需满足 $a_u\geqslant a_p$ ，然后交换节点 $p$ 与节点 $u$ 的权值（即 $\operatorname{swap}(a_p,a_u)$ ）。

$\hspace{15pt}$ 称一个可由初始状态通过若干次操作达到的状态 $b_1,b_2,\dots,b_n$ 为“最终合法状态”，当且仅当：
$\hspace{23pt}\bullet\,$ 对于每个节点 $i \left( 1 \le i \le n \right)$ ，其最终权值 $b_i$ 均满足 $b_i \leqslant s_i$ 。
$\hspace{15pt}$ 两种“最终合法状态” $b_1,b_2,\dots,b_n$ 与 $b_{1}',b_{2}',\dots,b_{n}'$ 不同，当且仅当存在某个位置 $i \left( 1 \leqslant i \leqslant n \right)$ ，使得 $b_i \ne b_i'$ 。

〖引用结束〗

$\hspace{15pt}$ 求解所有不同的“最终合法状态”所需要的最小操作次数之和。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数  ，表示节点数。
此后  行，第  行输入两个整数 ，表示树上第  条无向边连接节点  和节点 。
第  行输入  个整数 ，表示每个节点的权值。
第  行输入  个整数 ，表示每个节点的限制。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示所有不同的“最终合法状态”所需要的最小操作次数之和对  取模后的结果。

示例1

输入

复制

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

输出

复制

3
0

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。