#P9770. [2020年省队模拟]零一树

    ID: 6390 传统题 2000ms 512MiB 尝试: 14 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-异或抵消双射计数带权并查集可撤销并查集按大小合并分治回滚可行性剪枝

[2020年省队模拟]零一树

有一棵树,大小为nn,树上每条边都有边权,可以是1,可以是0。现有mm对ui,vi(ui≠vi,1≤ui,vi≤n)u_i,v_i(u_i \neq v_i, 1\leq u_i,v_i \leq n)。

定义一个准路径长度pip_i等于uiu_i到viv_i之间的路径和mod 2。现在问边权值有多少种方案让pip_i 序列满足非递减(pi≤pi+1,1≤i<m)p_i \leq p_{i+1} , 1 \leq i < m)。

答案需要对998 244 353取模。

输入格式

第一行两个整数nn和mm,分别表示树的大小和mm对u,vu,v (2≤n,m≤250000)(2 \leq n,m \leq 250000)。

第二行n−1n-1个整数viv_i ,表示viv_i和i+1i+1 有一条边。

接下来mm行,每行两个数,表示ui,viu_i,v_i。

输出格式

只有一个整数,代表方案数。

样例输入
3 3
1 2
1 2 
2 3
1 3
样例输出
2

对于10分数据满足 2≤n,m≤102 \leq n,m \leq 10

对于20分数据满足2≤n,m≤20002 \leq n,m \leq 2000