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
公開測資點#0 (100%): 1.0s , <50M

提示：

標籤:

出處:

2019 NCTU PCCA Winter [管理者： emiliaistruelove@gmail.com

qqrainbow (愛蜜莉雅) ]

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