{"problem":{"name":"Components","description":{"content":"You are given a tree with $N$ vertices. The vertices are numbered $1$ through $N$, and the $i$\\-th edge connects vertex $a_i$ and vertex $b_i$. Solve the following problem for each $x=1,2,\\ldots,N$: ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc287_f"},"statements":[{"statement_type":"Markdown","content":"You are given a tree with $N$ vertices. The vertices are numbered $1$ through $N$, and the $i$\\-th edge connects vertex $a_i$ and vertex $b_i$.\nSolve the following problem for each $x=1,2,\\ldots,N$:\n\n*   There are $(2^N-1)$ non-empty subsets $V$ of the tree's vertices. Find the number, modulo $998244353$, of such $V$ that the subgraph induced by $V$ has exactly $x$ connected components.\n\nWhat is an induced subgraph? Let $S$ be the subset of the vertices of a graph $G$; then the subgraph of $G$ induced by $S$ is a graph whose vertex set is $S$ and whose edge set consists of all edges of $G$ whose both ends are contained in $S$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 5000$\n*   $1 \\leq a_i \\lt b_i \\leq N$\n*   The given graph is a tree.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$\\vdots$\n$a_{N-1}$ $b_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc287_f","tags":[],"sample_group":[["4\n1 2\n2 3\n3 4","10\n5\n0\n0\n\nThe induced subgraph will have two connected components in the following five cases and one in the others.\n\n*   $V = {1,2,4}$\n*   $V = {1,3}$\n*   $V = {1,3,4}$\n*   $V = {1,4}$\n*   $V = {2,4}$"],["2\n1 2","3\n0"],["10\n3 4\n3 6\n6 9\n1 3\n2 4\n5 6\n6 10\n1 8\n5 7","140\n281\n352\n195\n52\n3\n0\n0\n0\n0"]],"created_at":"2026-03-03 11:01:14"}}