CF1893E Cacti Symphony

给定一个无向连通图，任意两个不同的简单环没有公共顶点。由于图可能非常大，输入以压缩形式给出：对于每条边，还给出一个数字 $d$，表示该边上有 $d$ 个额外的顶点。 你需要为图中的每个顶点和每条边分配一个权值，权值为 $1$ 到 $3$ 的整数。 如果一条边的两个端点的权值的按位异或不等于 $0$ 且不等于该边的权值，则称这条边是好的。 同样地，如果一个顶点相邻的所有边的权值的按位异或不等于 $0$ 且不等于该顶点的权值，则称这个顶点是好的。 你需要计算有多少种分配权值的方式，使得所有顶点和所有边都是好的。由于答案可能很大，请输出答案对 $998\,244\,353$ 取模后的结果。

第一行包含两个整数 $n$ 和 $m$，表示图中顶点数和边数（$2 \le n \le 5 \cdot 10^5$，$n-1 \le m \le 10^6$）。 接下来的 $m$ 行，每行包含三个整数 $a_i, b_i, d_i$（$1 \le a_i, b_i \le n$，$a_i \ne b_i$，$0 \le d_i \le 10^9$），表示有一条连接 $a_i$ 和 $b_i$ 的边，该边上还有 $d_i$ 个额外的顶点。保证给定的图是连通的，没有重边和自环，且任意两个不同的简单环没有公共顶点。

输出一个整数，表示满足条件的权值分配方案数，对 $998\,244\,353$ 取模。

在第一个测试样例中，图是一个 $3$ 个顶点的简单环。可以证明，恰好有 $12$ 种分配权值的方式使得所有顶点和边都是好的。 在第二个测试样例中，图的结构是两个 $3$ 个顶点的简单环通过一条边连接。可以证明，对于这样的图，没有任何一种分配权值的方式能使所有顶点和边都是好的。 由 ChatGPT 4.1 翻译