← 返回题目列表

AtCoder · abc340_g

G. 叶子颜色

中文机器翻译题面 查看原题

分数: 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