维什戴尔

Problem Description

“何以为我？” 给定一棵由编号为 $1,2,3,\cdots,n$ 的点构成的树。记集合 $S=\lbrace0,1\rbrace$。记整数 $w_i$（$w_i\in S$）表示编号为 $i$（$1\le i\le n$）的点的权值。 对于第 $i$（$1\le i\lt n$）条树上的边双向连接编号为 $u_i,v_i$ 的点：

1. 给定 $x_i$ 满足若断开第 $i$ 条边，存在整数 $k$（$k\in S$）使得此时编号为 $u_i$ 的点所在的连通块中恰有 $x_i$ 个点的权值是 $k$。
2. 给定 $y_i$ 满足若断开第 $i$ 条边，存在整数 $k$（$k\in S$）使得此时编号为 $v_i$ 的点所在的连通块中恰有 $y_i$ 个点的权值是 $k$。 出于一些原因，你不知道每个点的权值。故你需要计算有多少个不同的权值序列 $w_1,w_2,w_3,\cdots,w_n$ 满足以上所有条件，对 $998244353$ 取模。 可能不存在任何权值序列满足所有条件，此时答案为 $0$。

Input

本题包含多组测试数据。 首先在第一行输入一个整数 $T$（$1\le T\le3\times10^5$）表示测试数据组数。 对于每一组测试数据，输入包含 $n$ 行。 第一行包含一个整数 $n$（$1\le n\le 10^5$，$1\le\sum n\le3\times10^5$）表示树上点的数量。 接下来 $n-1$ 行，第 $i+1$（$1\le i\lt n$）行包含四个整数 $u_i,v_i,x_i,y_i$（$1\le u_i,v_i\le n$，$0\le x_i,y_i\lt n$），表示第 $i$ 条树上的边。 保证输入的点构成一棵树。

Output

对于每一组测试数据，输出包含一行一个整数表示答案对 $998244353$ 取模后的值。

Sample Input

2
4
1 2 2 1
1 3 2 1
1 4 2 1
4
1 2 1 2
2 3 1 1
3 4 2 1

Sample Output

8
4

Hint

在样例的第一组测试数据中，以下权值序列满足条件：

1. $w_1=0,w_2=0,w_3=1,w_4=1$。
2. $w_1=0,w_2=1,w_3=0,w_4=1$。
3. $w_1=0,w_2=1,w_3=1,w_4=0$。
4. $w_1=0,w_2=1,w_3=1,w_4=1$。
5. $w_1=1,w_2=0,w_3=0,w_4=0$。
6. $w_1=1,w_2=0,w_3=0,w_4=1$。
7. $w_1=1,w_2=0,w_3=1,w_4=0$。
8. $w_1=1,w_2=1,w_3=0,w_4=0$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（4）