T416546 [THUWC2018]城市规划

## THUWC2018 D1T2 ### 根据参加相关考试的考生回忆，题意经过化简的题目，不保证题目完全和当年的题目一致，数据为民间数据

有一棵$n$个结点的树，每个点都有颜色，求联通块内的颜色数不超过$2$的联通块个数 两种方案不同当且仅当存在一个点在一种方案的联通块中但不在另一种方案的联通块中 答案**对$998244353$取模**

第一行一个正整数$n$ 第二行$n$个正整数，$a_1,a_2,a_3…,a_n$ ，依次代表每个结点的颜色 接下来$n-1$行，每行两个正整数$u_i$和$v_i$，代表编号为$u$和$v$的两个结点之间有一条边

一行一个整数，代表方案数**对$998244353$取模**后的值

| 子任务编号 | $n\le$ | 特殊限制 | 分值 | 时间限制 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | 无 | $10$ | $1s$ | | $2$ | $100$ | 无 | $10$ | $1s$ | | $3$ | $1000$ | 无 | $10$ | $1s$ | | $4$ | $10^5$ | $\forall 1\le i \le n,a_i\le 2$ | $10$ | $1.5s$ | | $5$ | $10^5$ | $\forall 1\le i \le n,a_i\le 10$ | $15$ | $1.5s$ | | $6$ | $10^5$ | $\forall 1\le i \le n,a_i\le 100$ | $15$ | $1.5s$ | | $7$ | $10^5$ | 无 | $30$ | $1.5s$ | 对于 $100\%$ 的数据，$1\le a_i,u_i,v_i\le n\le 10^5$