{"problem":{"name":"Leaf Color","description":{"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$.   Find the number, modulo $998","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc340_g"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc340_g","tags":[],"sample_group":[["3\n1 2 1\n1 2\n2 3","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$"],["5\n2 2 1 1 1\n2 5\n3 4\n1 3\n1 5","9"],["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","48"]],"created_at":"2026-03-03 11:01:14"}}