#P13497. [ABC340G] Leaf Color

    ID: 12681 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-虚树树形 DP计数 DP树上倍增DFS 序排序补充相邻点 LCA栈建虚树

[ABC340G] Leaf Color

AT_abc340_g [ABC340G] Leaf Color

题目描述

有一棵包含 NN 个顶点的树 TT,顶点编号为 11 到 NN。第 ii 条边连接顶点 uiu_i 和顶点 viv_i。此外,顶点 ii 被染成颜色 AiA_i。

请计算满足以下条件的 TT 的顶点集合(非空子集)SS 的个数,并对 998244353998244353 取模:

  • SS 所对应的诱导子图 GG 满足以下所有条件:
    • GG 是一棵树。
    • 所有度数为 11 的顶点的颜色都相同。

诱导子图的定义如下:对于图 GG 的顶点子集 SS,SS 所对应的诱导子图是指顶点集合为 SS,边集合为“GG 中两端都属于 SS 的所有边”的图。

输入格式

输入以如下格式从标准输入读入:

NN
A1 A2 … ANA_1\ A_2\ \dots\ A_N
u1 v1u_1\ v_1
u2 v2u_2\ v_2
⋮\vdots
uN−1 vN−1u_{N-1}\ v_{N-1}

输出格式

输出满足题目条件的顶点集合 SS 的个数,对 998244353998244353 取模。

输入输出样例 #1

输入 #1

3
1 2 1
1 2
2 3

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

9

输入输出样例 #3

输入 #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

说明/提示

限制条件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤Ai≤N1 \leq A_i \leq N
  • 1≤ui<vi≤N1 \leq u_i < v_i \leq N
  • 输入保证图为一棵树
  • 输入的所有数均为整数

样例解释 1

满足条件的顶点集合有以下 44 种:

  • {1}\lbrace 1 \rbrace
  • {1,2,3}\lbrace 1, 2, 3 \rbrace
  • {2}\lbrace 2 \rbrace
  • {3}\lbrace 3 \rbrace