h559. pC. 共享自行車 (bike)
Tags : DP Tree dfs
Accepted rate : 55人/60人 ( 92% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-03-08 21:50

Content

完整題目:https://drive.google.com/file/d/1RSq17g00V-ygkC8x37iLhtNteoqLAwZg/view?usp=sharing

給你一個有 $n-1$ 個邊 $n$ 點的簡單無向圖,其中每個節點都可互通。

首先每個邊有距離也就是邊權,接著告訴你每個點有幾輛腳踏車(點權),總共的腳踏車數為 $n \times k$,你的目標是讓每個點的腳踏車數量一樣,你可以把 $a$ 輛腳踏車從一個點移到跟它相鄰的點(調度),花費是 $a \times$ 距離。問最少花費多少?

 

限制:

$1 ≤ n ≤ 10^5$

$1 ≤ k ≤ 10$

點權總和 $=n \times k$

$1 ≤$ 邊權 $≤ 10^3$

$0 ≤$ 點權 $≤ n \times k$

Input

首先第一行有兩個數 $n, k$。

接著一行有 $n$ 個數,分別代表目前點權,也就是一開始各點的腳踏車數量。

最後有$n-1$行,每行三個數 $u$ 、 $v$ 、 $w$ ,代表有一個權重為 $w$ 且連接 $u$、$v$ 的雙向邊。

Output

輸出最小花費成本。

Sample Input #1
8 2
4 2 2 1 3 3 0 1
1 2 3
2 3 1
3 4 2
5 6 2
6 7 3
6 8 1
2 6 3
Sample Output #1
21
Sample Input #2
4 3
1 10 0 1
1 4 3
3 2 2
4 2 1
Sample Output #2
16
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <10M
公開 測資點#3 (10%): 1.0s , <10M
公開 測資點#4 (10%): 1.0s , <10M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
Hint :

題目和測資來源:twpca

另外抱歉這裡沒有分subtasks。

如果題目有問題歡迎來信詢問!

Tags:
DP Tree dfs
出處:
TOI入營考2022 [管理者: r1cky (hehe) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
34837 mushroom.cs9 ... (mushroom) h559
題解
215 2023-04-19 22:25