AT_abc340_g [ABC340G] Leaf Color

[problemUrl]: https://atcoder.jp/contests/abc340/tasks/abc340_g 頂点に $ 1 $ から $ N $ までの番号がついた $ N $ 頂点の木 $ T $ があります。$ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結んでいます。また、頂点 $ i $ は色 $ A_i $ で塗られています。 $ T $ の頂点集合の(非空な)部分集合 $ S $ のうち、次の条件を満たすものの個数を $ 998244353 $ で割った余りを求めてください。 - $ T $ の $ S $ による誘導部分グラフ $ G $ は次の条件を全て満たす。 - $ G $ は木である。 - 次数 $ 1 $ の頂点に塗られた色が全て一致している。 誘導部分グラフとは $ S $ をグラフ $ G $ の頂点の部分集合とします。このとき、$ G $ の $ S $ による誘導部分グラフとは、頂点集合が $ S $ で、辺集合が「$ G $ の辺であって両端が $ S $ に含まれるもの全て」であるようなグラフです。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $

問題文の条件を満たす頂点集合の(非空な)部分集合 $ S $ の個数を $ 998244353 $ で割った余りを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ N $ - $ 1\ \leq\ u_i\ \lt\ v_i\ \leq\ N $ - 入力で与えられるグラフは木 - 入力される値は全て整数 ### Sample Explanation 1 条件を満たす頂点の集合は次の $ 4 $ 通りです。 - $ \lbrace\ 1\ \rbrace $ - $ \lbrace\ 1,\ 2,\ 3\ \rbrace $ - $ \lbrace\ 2\ \rbrace $ - $ \lbrace\ 3\ \rbrace $