{"raw_statement":[{"iden":"problem statement","content":"There is a tree $T$ with $N$ vertices numbered from $1$ to $N$. The $i$\\-th edge connects vertices $u_i$ and $v_i$. Additionally, vertex $i$ is painted with color $A_i$.  \nFind the number, modulo $998244353$, of (non-empty) subsets $S$ of the vertex set of $T$ that satisfy the following condition:\n\n*   The induced subgraph $G$ of $T$ by $S$ satisfies all of the following conditions:\n    *   $G$ is a tree.\n    *   All vertices with degree $1$ have the same color.\n\nWhat is an induced subgraph? Let $S$ be a subset of the vertices of a graph $G$. The induced subgraph of $G$ by $S$ is a graph whose vertex set is $S$ and whose edge set consists of all edges in $G$ that have both endpoints in $S$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq A_i \\leq N$\n*   $1 \\leq u_i \\lt v_i \\leq N$\n*   The graph given in the input is a tree.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\dots$ $A_N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$"},{"iden":"sample input 1","content":"3\n1 2 1\n1 2\n2 3"},{"iden":"sample output 1","content":"4\n\nThe following four sets of vertices satisfy the condition.\n\n*   $\\lbrace 1 \\rbrace$\n*   $\\lbrace 1, 2, 3 \\rbrace$\n*   $\\lbrace 2 \\rbrace$\n*   $\\lbrace 3 \\rbrace$"},{"iden":"sample input 2","content":"5\n2 2 1 1 1\n2 5\n3 4\n1 3\n1 5"},{"iden":"sample output 2","content":"9"},{"iden":"sample input 3","content":"15\n5 3 5 1 1 4 4 4 2 5 5 4 4 2 5\n3 13\n4 10\n7 11\n8 9\n2 10\n2 14\n5 11\n5 6\n6 13\n12 13\n9 14\n9 13\n1 13\n1 15"},{"iden":"sample output 3","content":"48"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}