e296: PC. City Planning(城市規劃)
Tags :
Accepted rate : 4人/4人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-07-01 11:34

Content

有$n$個城市,彼此之間有道路連結,城市之間的道路構成⼀顆樹即為無向無環圖,城市之間的道路初始皆為費⽤皆為$0$現在為了增加收⼊,決定在某些道路加上過路費,現有$k$個花費,需被分配到$k$條「不同」道路。
為了不造成交通費⽤過⾼,此次規劃的⽬標即為讓全點對的最短距離和最⼩,即為所有$dist(i,￿j)$, $1 \leq i < j \leq n$ 之和最⼩

Input

測試輸⼊的第⼀⾏為⼀個整數$t$,代表有多少組測試資料。

每組測試資料第⼀⾏為兩個正整數$n$跟$m$,代表有$n$個點和$m$個待分配花費。

接下來$n - 1$ ⾏各有2 整數$u_i$、$v_i$, 代表兩個城市間有道路連結,接下來⼀⾏有$a_1~a_m$ 為待選定位置的花費

Output

輸出⼀個數最⼩的全點對最短距離和,答案可能很⼤,所以請輸出答案modulo 998244353

Sample Input
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
Sample Output
66
444
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <50M
Hint :
Tags:
出處:
2019 NCTU PCCA Winter [管理者:
qqrainbow (愛蜜莉雅)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」