分数: 600 点
问题陈述
有一棵树 T 与 N 顶点编号自 1 to N。的 i第一条边连接顶点 u_i 和 v_i。另外,顶点 i 涂有颜色 A_i.
求模数 998244353,(非空)子集 S 的顶点集 T 满足以下条件:
- 诱导子图 G of T by S 满足以下所有条件:
- G 是一棵树。
- 所有带有度数的顶点 1 具有相同的颜色。
什么是归纳子图?
让 S 是图顶点的子集 G。的诱导子图 G by S 是一个图,其顶点集为 S 且其边集由中的所有边组成 G 的两个端点都在 S.约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- 1 \leq u_i \lt v_i \leq N
- 输入中给出的图是一棵树。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 \dots A_N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
输出
打印数字,模数 998244353,(非空)子集 S 的顶点集 T 满足问题陈述中的条件。
示例输入 1
3 1 2 1 1 2 2 3
示例输出 1
4
以下四组顶点满足条件。
- \lbrace 1 \rbrace
- \lbrace 1, 2, 3 \rbrace
- \lbrace 2 \rbrace
- \lbrace 3 \rbrace
示例输入 2
5 2 2 1 1 1 2 5 3 4 1 3 1 5
示例输出 2
9
示例输入 3
15 5 3 5 1 1 4 4 4 2 5 5 4 4 2 5 3 13 4 10 7 11 8 9 2 10 2 14 5 11 5 6 6 13 12 13 9 14 9 13 1 13 1 15
示例输出 3
48