G - Tapu & Tapi 2
Editorial
/
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
N 頂点からなる木があり、頂点には 1 から N までの番号がついています。N-1 本の辺のうち i 番目の辺は頂点 A_i と B_i を重み V_i で双方向に結んでいます。
X 匹の たぴちゃん と Y 匹の たぷちゃん がいます。最初 j 番目の たぴちゃん は頂点 P_j、k 番目の たぷちゃん は頂点 Q_k にいます。同じ頂点に複数の たぴちゃん や たぷちゃん は存在しません。
すべての たぴちゃん は隣接する頂点に移動する操作を繰り返すことができます。しかし たぴちゃん と たぷちゃん は仲が悪いです。たぴちゃん が たぷちゃん のいる頂点に移動すると不快な気持ちになるかもしれません。
そこで、いくつかの辺を削除することですべての たぴちゃん が たぷちゃん のいる頂点に移動できなくしたいです。このとき、削除する辺の重みの総和の最小値を求めてください。
制約
- 2 \leq N \leq 5 \times 10^5
- 1 \leq X, Y \leq N
- 1 \leq A_i \lt B_i \leq N
- 1 \leq V_i \leq 10^9
- 1 \leq P_j, Q_k \leq N
- P_1, P_2, ..., P_X, Q_1, Q_2, ..., Q_Y は相異なる
- 与えられるグラフは木
- 入力は全て整数
部分点
- N \leq 500 を満たすデータセットに正解した場合、40 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
N X Y A_1 B_1 V_1 A_2 B_2 V_2 : A_{N-1} B_{N-1} V_{N-1} P_1 P_2 ... P_X Q_1 Q_2 ... Q_Y
出力
1 行に答えを出力せよ。
入力例 1
5 4 1 1 2 1 2 3 2 3 4 3 4 5 4 1 2 4 5 3
出力例 1
5
2 番目と 3 番目の辺を削除します。このとき、どの たぴちゃん も たぷちゃん がいる頂点 3 には移動できません。
入力例 2
6 2 2 1 2 6 1 3 3 1 4 4 3 5 2 3 6 2 1 2 5 6
出力例 2
3
2 番目の辺を削除します。