a621. D. 樹的分數 - 旦旦解題農場

內容

給一棵 $n$ 個節點的樹，節點編號為 $1 \sim n$ ，我們知道對於樹上的任意兩個相異節點 $x, y$ ，存在唯一一條 $x$ 到 $y$ 的簡單路徑。

假設這條路徑上有 $k$ 個節點(包含 $x, y$ )，節點編號為 $v_1, v_2, ..., v_k$ ，我們定義這條路徑的分數 $f(x, y) = \sum_{i=1}^{k} v_i \qquad$ 。

而整棵樹的分數就是樹上所有路徑的分數總合，即 $\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} f(i, j) \qquad \qquad$ 。

現在想要對 $n$ 個節點重新編號，使整棵樹的分數越大越好，試求有多少種重新編號的方法使樹的分數有最大值。

由於答案可能很大，請輸出方法數對 $998244353$ 取模後的結果。

輸入說明

輸入共 $n$ 行

第一行一個正整數 $n$ 代表樹上有 $n$ 個節點

接下來 $n-1$ 行，每行有兩個正整數 $a, b$ ，代表編號為 $a$ 的節點到編號為 $b$ 的節點之間有一條邊

其中 $1 \le a, b \le n , a \ne b$ 且保證圖為一棵樹

對於 $15 \%$ 的測資有 $1 \le n \le 100$ ，且圖形為一條鏈
對於 $25 \%$ 的測資有 $1 \le n \le 5000$
對於 $60 \%$ 的測資有 $1 \le n \le 2 \times 10^5$

輸出說明

輸出一個整數，答案對 $998244353$ 取模

範例輸入

範例輸出

測資資訊：

記憶體限制： 32 MB
不公開測資點#0 (4%): 1.0s , <1K
不公開測資點#1 (4%): 1.0s , <1K
不公開測資點#2 (4%): 1.0s , <1K
不公開測資點#3 (3%): 1.0s , <1K
不公開測資點#4 (5%): 1.0s , <1M
不公開測資點#5 (5%): 1.0s , <1M
不公開測資點#6 (5%): 1.0s , <1M
不公開測資點#7 (5%): 1.0s , <1M
不公開測資點#8 (5%): 1.0s , <1M
不公開測資點#9 (5%): 1.0s , <10M
不公開測資點#10 (5%): 1.0s , <10M
不公開測資點#11 (5%): 1.0s , <10M
不公開測資點#12 (5%): 1.0s , <10M
不公開測資點#13 (5%): 1.0s , <10M
不公開測資點#14 (5%): 1.0s , <10M
不公開測資點#15 (6%): 1.0s , <10M
不公開測資點#16 (6%): 1.0s , <10M
不公開測資點#17 (6%): 1.0s , <10M
不公開測資點#18 (6%): 1.0s , <10M
不公開測資點#19 (6%): 1.0s , <10M

提示：

範例解釋:

$5$ 個節點共有 $5! = 120$ 種編號方式，其中下面 $6$ 種都可以使樹的分數有最大值 $97$ 。

標籤:

出處:

DDJ Regular Contest Round#5 [管理者：

warner1129 (unknown)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」