Problem 2373. -- [Noip模拟]植树方案

2373: [Noip模拟]植树方案

Time Limit: 4 Sec  Memory Limit: 256 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board]

Description

T 国打算种一批树。所谓树,就是由 N 个结点与 N - 1 条边连接而成的连通无向图。T 国的国王对于这些树有下列要求: 
1、树没有根,但它的形态是给定的(即这 N - 1 条边是给出的); 
2、树的每条边上可以放置一朵花(当然也可以不放置); 
3、共 Q 条约束,第 i 组约束规定:标号 ui 的结点到标号 vi 的结点的简单路径上,花的数量为奇数或偶数。 
现在,国王想事先知道他最多能种多少棵不一样的树
(两棵树被视为不一样当且仅当一棵树中某条边的放花情况与另一棵树不相同)。 

Input

第 1 行两个整数 N, Q; 
接下来 N - 1 行,每行两个整数 u、v,表示 u、v 间存在一条边;
接下来 Q 行,每行三个整数 ui、vi、ki,若 ki 为 0,表示 ui 到 vi 的简单路径上花的个数为偶数,否则为奇数。 
N, Q ≤ 100000、0 ≤ ki ≤ 1。 

Output

一行一个整数,表示能种的不一样的树的种数,对 998244353 取模。 

Sample Input

3 1
1 2
1 3
2 3 1	 

Sample Output

2

HINT

Source

[Submit][Status]