{"problem":{"name":"Product of Max of Sum of Subtree","description":{"content":"There is a tree with $N$ vertices numbered from $1$ to $N$, where the $i$\\-th edge connects vertices $A_i$ and $B_i$. We will now randomly write real numbers between $-(N-1)$ and $1$ (inclusive) on ea","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc073_c"},"statements":[{"statement_type":"Markdown","content":"There is a tree with $N$ vertices numbered from $1$ to $N$, where the $i$\\-th edge connects vertices $A_i$ and $B_i$.\nWe will now randomly write real numbers between $-(N-1)$ and $1$ (inclusive) on each vertex of this tree. The random number distributions are all independent uniform distributions.\nThen, the **score** of the tree is defined as follows:\n\n*   For each vertex $i$, define $x_i$ as follows:\n    *   The maximum value of the sum of values written on vertices of connected subgraphs that contain vertex $i$\n*   If there exists $i$ that does not satisfy $0 \\leq x_i \\leq 1$, the tree's score is $0$.\n*   Otherwise, the tree's score is $\\prod_{1 \\leq i \\leq N} x_i$.\n\nFind the expected value $\\text{mod }{998244353}$ of the tree's score.\nDefinition of expected value $\\text{mod }{998244353}$It can be proved that the sought expected value is always a rational number. Also, under the constraints of this problem, it can be proved that when the value is expressed as an irreducible fraction $\\frac{P}{Q}$, we have $Q \\neq 0 \\pmod{998244353}$. Therefore, an integer $R$ satisfying $R \\times Q \\equiv P \\pmod{998244353}, 0 \\leq R < 998244353$ is uniquely determined. Answer this $R$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 5000$\n*   $1 \\leq A_i, B_i \\leq N$\n*   The input 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$A_2$ $B_2$\n$\\vdots$\n$A_{N-1}$ $B_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc073_c","tags":[],"sample_group":[["1","499122177\n\nThe expected value of the score is $1/2$."],["2\n1 2","873463809\n\nThe expected value of the score is $1/8$."],["3\n1 2\n2 3","842653798\n\nThe expected value of the score is $13/648$."],["5\n1 2\n2 3\n3 4\n4 5","132050425\n\nThe expected value of the score is $41/187500$."],["8\n1 2\n1 3\n1 4\n1 5\n5 6\n5 7\n5 8","243711918\n\nThe expected value of the score is $2477/30064771072$."]],"created_at":"2026-03-03 11:01:13"}}