3960. LegendOfAdlez

【题目描述】

你有一棵 $n$ 个节点的树，保证节点 $n$ 为叶子。

每个节点上要么没有钥匙，要么恰好有一把钥匙。特殊的，节点 $n$ 上没有钥匙。（共有 $2^{n-1}$ 种初态）

一些边是上锁的，需要消耗一把钥匙打开，打开后可永久通行。

你将从节点 $1$ 出发，试图到达节点 $n$。求有多少种钥匙的初态，使得无论你如何操作，都能到达目的地。

答案对 $998244353$ 取模。

【输入格式】

第一行一个正整数 $n$。

接下来 $n-1$ 行，每行三个整数 $u,v,c$ 表示一条数边 $(u,v)$。若 $c=0$ 代表边是通行的，否则是上锁的。

【输出格式】

一个整数表示答案。

【样例输入1】

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

【样例输出1】

1

【样例输入2】

10
1 2 1
2 3 0
3 4 1
1 5 1
5 6 1
6 7 1
1 8 1
8 9 1
9 10 0

【样例输出2】

8

【数据规模与约定】

$1\le n\le 5\times 10^3$

【来源】

Topcoder SRM650