A 女巫（witch）

TIME:2S MEMORY:1024M

【问题描述】

​ 对于一棵边带权的有 $N$ 个点的有根树 $T$，定义其权值为 $\sum_{i=1}^N\sum_{j=i+1}^Nd(i,j)$。其中 $d(i,j)$ 是树上 $i$ 到 $j$ 所经过的简单路径的边权 异或和。

​ 对于一棵边带权的有 $N$ 个点的有根树 $T$，称其点集的一个子集 $S$ 合法，当：$\forall i,j\in S,$ $\operatorname{lca}(i,j)\in S$。

​ 对于一棵边带权的有 $N$ 个点的有根树 $T$，其点集的一个合法子集 $S$ 能生成一棵新树，点集为 $S$，边集为：对于每一个点 $i\in S$，找到在原树上是其祖先的在 $S$ 中的深度最大的点 $j$（如果找不到，则 $i$ 是新树的根），将 $j$ 设为 $i$ 在新树上的父亲，边权为原树上 $i$ 到 $j$ 简单路径的边权和。

​ 给定一棵 $N$ 个点的边带权的树，树的根是 $1$，求出其点集的所有合法子集生成的新树的权值之和。对 $998244353$ 取模。

【输入格式】

​ 从文件 $witch.in$ 中读入数据。

​ 第一行包含一个整数 $N$，表示树的大小。

​ 接下来的 $N-1$ 行每行包含三个整数 $u_i,v_i,w_i$，表示树上有一条 $u_i$ 到 $v_i$ 权值为 $w_i$ 的边。。

【输出格式】

​ 输出到文件 $witch.out$ 中。

​ 输出一行一个整数，表示答案。

【样例输入1】

3
1 2 1
1 3 1

【样例输出1】

4

【样例1解释】

​ $S=\{1\}$ 时权值为 $0$。

​ $S=\{2\}$ 时权值为 $0$。

​ $S=\{3\}$ 时权值为 $0$。

​ $S=\{1,2\}$ 时权值为 $1$。

​ $S=\{1,3\}$ 时权值为 $1$。

​ $S=\{1,2,3\}$ 时权值为 $2$。

​ 所以答案为 $0+0+0+1+1+2=4$。

【样例输入2】

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

【样例输出2】

102

【样例3】

​ 见选手目录下的 $witch/witch3.in$ 与 $witch/witch3.ans$。

【样例4】

​ 见选手目录下的 $witch/witch4.in$ 与 $witch/witch4.ans$。

【样例5】

​ 见选手目录下的 $witch/witch5.in$ 与 $witch/witch5.ans$。

【样例6】

​ 见选手目录下的 $witch/witch6.in$ 与 $witch/witch6.ans$。

【数据范围及约定】

​ 对于所有数据，保证：$1\le N\le 10^5,1\le D\le 2^{20}$。$D$ 为树上的最大深度。

​ 特殊性质 $A$：对于第 $i$ 条边，$v_i=i+1$，$u_i$ 在 $[1,i]$ 均匀随机。

​ 特殊性质 $B$：对于第 $i$ 条边，$v_i=i+1$，$u_i=1$。

​ 特殊性质 $C$：对于第 $i$ 条边，$v_i=i+1$，$u_i=i$。