{"problem":{"name":"[ICPC 2022 Jinan R] DFS Order 2","description":{"content":"Prof. Pang has a rooted tree that is rooted at vertex $1$ and has $n$ nodes. These $n$ nodes are numbered from $1$ to $n$. Now he wants to start the depth-first search at the root. He wonders for eac","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9669"},"statements":[{"statement_type":"Markdown","content":"Prof. Pang has a rooted tree that is rooted at vertex $1$ and has $n$ nodes. These $n$ nodes are numbered from $1$ to $n$.\n\nNow he wants to start the depth-first search at the root. He wonders for each node $v$, how many ways it can appear in the $j$-th position of $\\textbf{depth-first search order}$. The depth-first search order is the order of nodes visited during the depth-first search. A node appears in the $j$-th ($1\\le j\\le n$) position in this order means it is visited after $j-1$ other nodes. Because sons of a node can be iterated in arbitrary order, multiple possible depth-first orders exist. \n\nProf. Pang wants to know for each node $v$, how many different $\\textbf{depth-first search order}$s such that $v$ appears in the $j$-th position. For each $v, j~(1 \\le v, j \\le n)$, compute the answer. Because the answer can be very large, output it modulo $998244353$.\n\nFollowing is a pseudo-code for the depth-first search on a rooted tree. After calling $\\textbf{main}$(), $\\texttt{dfs\\_order}$ is the depth-first search order.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/l3gjstn0.png)\n\n## Input\n\nThe first line contains one integer $n~(1\\le n \\le 500)$, the number of vertices in the tree.\n\nEach of the next $n-1$ lines describes an edge of the tree. Edge $i$ is denoted by two integers $u_i$ and $v_i$, the labels of vertices it connects $(1\\le u_i,v_i\\le n, u_i\\neq v_i)$.\n\nIt is guaranteed that the given edges form a tree.\n\n## Output\n\nFor each vertex $v$ from $1$ to $n$, output one line containing $n$ integers modulo $998244353$. The $j$-th integer in the $v$-th line should be the number of different depth-first search orders such that $v$ appears in the $j$-th position.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9669","tags":["2022","O2优化","背包 DP","树形 DP","ICPC","济南"],"sample_group":[["5\n1 2\n1 3\n3 4\n3 5","4 0 0 0 0\n0 2 0 0 2\n0 2 2 0 0\n0 0 1 2 1\n0 0 1 2 1"]],"created_at":"2026-03-03 11:09:25"}}