Cho đồ thị vô hướng
liên thông có trọng số G=(VG, EG), trong đó VG
là tập các đỉnh của G, EG là tập các cạnh của G. Đồ thị G có n đỉnh
và n-1 cạnh, các đỉnh được đánh số từ 1 đến n
Một đồ thị G’=(VG’,
EG’) được gọi là đồ thị con của G khi VG’⊆VG
và EG’ ⊆ EG.
Giá trị của một đồ thị
là tổng trọng số các cạnh trong đồ thị đó.
Cho tập X (X⊆VG)
gồm k
đỉnh. Gọi G’ (đồ thị con của G) là đồ thị liên thông có giá trị nhỏ nhất chứa tập
X
Hãy xác định khoảng
cách lớn nhất từ đỉnh u (1≤u≤n) đến một đỉnh t ∈ G’
Quy ước rằng nếu u∉G’
thì khoảng cách là 0.
Dữ liệu vào: Từ tệp văn bản KAMP03.INP
+ Dòng đầu tiên ghi 2
số nguyên dương n và k (1≤K≤N≤500000)
+ n-1
dòng tiếp theo, mỗi dòng 3 số nguyên u, v, c cho biết c là trọng số của cạnh (u,v). (1≤u, v≤n; 1≤c≤106)
+ Tiếp theo gồm k
dòng, mỗi dòng ghi 1 số nguyên là số hiệu của đỉnh thuộc tập X
Dữ liệu ra: ghi vào tệp văn bản KAMP03.OUT
+ Gồm n dòng, dòng thứ
i ghi khoảng cách lớn nhất của đỉnh u đến đỉnh t ∈ G’
Ví dụ:
|
KAMP03.INP
|
KAMP03.OUT
|
|
KAMP03.INP
|
KAMP03.OUT
|
|
5 2
2 5 1
2 4 1
1 2 2
1 3 2
4
5
|
0
1
0
2
2
|
|
7
2
1
2 4
1
3 1
2 5
1
2
4 2
4
7 3
4
6 2
3
7
|
9
5
10
7
0
0
10
|
