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)

]

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