1012. 仙人掌图

题目描述

在图论中，仙人掌图是指：对于图中的每条边，其最多处于一个简单环内的图。如下图所示。注意：树也是仙人掌图；两个点之间恰好有两条边也构成一个简单环。


你现在画出了一棵十分美丽的仙人掌，但是你的好朋友把其中某些边给擦掉了，只给你剩下了一棵树！现在，你只记得剩下的这棵树上的每条边当初所在的简单环的边数 $c_i$。你的好朋友想要知道，根据这些 $c_i$ 能还原出多少棵不同的符合要求的仙人掌图。答案可能很大，你只需要求出答案对 $998244353$ 取模后的结果。

两棵仙人掌图不同当且仅当它们的边集不同。

输入格式

第一行输入一个正整数 $T$（$1 \le T \le 10^4$），表示数据组数。

对于每一组数据，第一行输入一个正整数 $n$（$2 \le n \le 2 \times 10^5$），表示点数。

接下来 $n - 1$ 行，每行输入三个正整数 $u, v, c$（$1 \le u, v, c \le n$, $u \ne v$），表示树上的一条连接点 $u, v$ 的边，这条边之前所在的简单环的边数为 $c_i$。如果 $c_i = 1$，说明这条边之前不属于任意一个简单环。保证输入是一棵树。

数据保证 $\sum n \le 4 \times 10^6$。

输出格式

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

样例输入

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

样例输出

1
0

来源：2026杭电多校-测试专用（电子科大） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1233&pid=1012