e296.
PC. City Planning(城市規劃)
內容
有$n$個城市，彼此之間有道路連結，城市之間的道路構成⼀顆樹即為無向無環圖，城市之間的道路初始皆為費⽤皆為$0$現在為了增加收⼊，決定在某些道路加上過路費，現有$k$個花費，需被分配到$k$條「不同」道路。
為了不造成交通費⽤過⾼，此次規劃的⽬標即為讓全點對的最短距離和最⼩，即為所有$dist(i,j)$, $1 \leq i < j \leq n$ 之和最⼩。
輸入說明
測試輸⼊的第⼀⾏為⼀個整數$t$，代表有多少組測試資料。
每組測試資料第⼀⾏為兩個正整數$n$跟$m$，代表有$n$個點和$m$個待分配花費。
接下來$n - 1$ ⾏各有2 整數$u_i$、$v_i$, 代表兩個城市間有道路連結，接下來⼀⾏有$a_1$~$a_m$ 為待選定位置的花費
$2 < m < n \leq 100000$
$t \leq 20$
$a_i \leq 100000$
輸出說明
輸出⼀個數最⼩的全點對最短距離和，答案可能很⼤，所以請輸出答案modulo 998244353
範例輸入
#1
2 6 4 4 3 2 1 6 4 5 3 1 3 2 4 4 2 9 8 9 8 5 8 2 6 7 5 1 3 4 5 2 1 1 4 7 7 1 5 7 3 5 7
範例輸出
#1
66 444
測資資訊：
記憶體限制：
512
MB
提示 ：
標籤:
出處:
2019 NCTU PCCA Winter
[管理者：
qqrainbow
(愛蜜莉雅)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||