{"problem":{"name":"Authentic Tree DP","description":{"content":"For an undirected tree $t$, let us define a rational number $f(t)$ as follows. *   Let $n$ be the number of vertices in $t$. *   If $n=1$: Let $f(t)=1$. *   If $n \\geq 2$:     *   For an edge $e$ in ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc058_f"},"statements":[{"statement_type":"Markdown","content":"For an undirected tree $t$, let us define a rational number $f(t)$ as follows.\n\n*   Let $n$ be the number of vertices in $t$.\n*   If $n=1$: Let $f(t)=1$.\n*   If $n \\geq 2$:\n    *   For an edge $e$ in $t$, we denote by $t_x(e)$ and $t_y(e)$ the two trees that result from deleting $e$ from $t$ (in arbitrary order).\n    *   Let $f(t)=(\\sum_{e \\in t} f(t_x(e)) \\times f(t_y(e)))/n$.\n\nYou are given a tree $T$ with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge connects Vertex $A_i$ and Vertex $B_i$.\nFind the value $f(T)$ $\\text{mod }{998244353}$.\nWhat is a rational number $\\text{mod }{998244353}$?Under the Constraints of this problem, when the sought rational number is represented as $\\frac{P}{Q}$, it can be proved that $Q \\neq 0 \\pmod{998244353}$. Therefore, there is a unique integer $R$ such that $R \\times Q \\equiv P \\pmod{998244353}, 0 \\leq R < 998244353$. Find this $R$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 5000$\n*   $1 \\leq A_i,B_i \\leq N$\n*   The given graph is a tree.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_{N-1}$ $B_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc058_f","tags":[],"sample_group":[["2\n1 2","499122177\n\nWe have $f(T)=1/2$."],["3\n1 2\n2 3","332748118\n\nWe have $f(T)=1/3$."],["4\n1 2\n2 3\n3 4","103983787"],["10\n4 5\n1 9\n6 1\n8 4\n5 9\n4 7\n3 10\n5 2\n4 3","462781191"]],"created_at":"2026-03-03 11:01:14"}}