#P17923. Tree and Subgraph Problem

Tree and Subgraph Problem

Tree and Subgraph Problem

题目描述

给定一棵有 nn 个顶点的无根树,顶点 ii 的颜色为 cic_i。

对于非空顶点集合 SS,记 sub⁡(S)\operatorname{sub}(S) 为树中包含 SS 的最小连通子图。称顶点集合的有序对 (S,T)(S,T) 合法,当且仅当:

  • S,TS,T 均非空;
  • SS 内所有顶点颜色相同,TT 内所有顶点颜色相同;两个集合的颜色不要求相同,也不要求不同;
  • sub⁡(S)\operatorname{sub}(S) 与 sub⁡(T)\operatorname{sub}(T) 没有公共顶点或边。

求合法有序对的数量,对 998244353998244353 取模。(S,T)(S,T) 与 (T,S)(T,S) 是不同的有序对。

输入格式

第一行一个整数 TT,表示测试数据组数。每组数据:

第一行一个整数 nn。

第二行 nn 个整数 c1,…,cnc_1,\ldots,c_n。

接下来 n−1n-1 行,每行两个整数 u,vu,v,表示树的一条无向边。

输出格式

每组数据输出一行一个整数,表示答案对 998244353998244353 取模的结果。

数据范围

  • 1≤T≤1041\le T\le10^4,1≤n≤2×1051\le n\le2\times10^5。
  • 1≤ci≤n1\le c_i\le n,1≤u,v≤n1\le u,v\le n,u≠vu\ne v。
  • 输入的边构成一棵树。
  • 所有测试数据的 nn 之和不超过 2×1052\times10^5。

样例

3
2
1 1
1 2
5
1 1 1 2 2
1 2
2 3
3 4
4 5
5
1 2 1 2 1
1 2
1 3
2 4
2 5
2
54
42