G - Tapu & Tapi 2

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 700

問題文

N 頂点からなる木があり、頂点には 1 から N までの番号がついています。N-1 本の辺のうち i 番目の辺は頂点 A_iB_i を重み V_i で双方向に結んでいます。

X 匹の たぴちゃん と Y 匹の たぷちゃん がいます。最初 j 番目の たぴちゃん は頂点 P_jk 番目の たぷちゃん は頂点 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 番目の辺を削除します。