D - Minimum Steiner Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

頂点に 1 から N の番号がついた N 頂点の木が与えられます。i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。

このグラフからいくつかの(0 個でもよい)辺と頂点を削除してできる木のうち、指定された K 個の頂点、頂点 V_1,\ldots,V_K を全て含むようなものの頂点数の最小値を求めてください。

制約

  • 1 \leq K \leq N \leq 2\times 10^5
  • 1 \leq A_i,B_i \leq N
  • 1 \leq V_1 < V_2 < \ldots < V_K \leq N
  • 与えられるグラフは木である
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 B_1
\vdots
A_{N-1} B_{N-1}
V_1 \ldots V_K

出力

答えを出力せよ。

入力例 1

7 3
1 2
1 3
2 4
2 5
3 6
3 7
1 3 5

出力例 1

4

与えられた木は下図左の通りであり、そこからいくつかの辺と頂点を削除してできる木のうち頂点 1,3,5 を全て含むような頂点数最小のものは下図右の通りです。

図

入力例 2

4 4
3 1
1 4
2 1
1 2 3 4

出力例 2

4

入力例 3

5 1
1 4
2 3
5 2
1 2
1

出力例 3

1

Score : 425 points

Problem Statement

You are given a tree with N vertices numbered 1 to N. The i-th edge connects vertices A_i and B_i.

Consider a tree that can be obtained by removing some (possibly zero) edges and vertices from this graph. Find the minimum number of vertices in such a tree that includes all of K specified vertices V_1,\ldots,V_K.

Constraints

  • 1 \leq K \leq N \leq 2\times 10^5
  • 1 \leq A_i,B_i \leq N
  • 1 \leq V_1 < V_2 < \ldots < V_K \leq N
  • The given graph is a tree.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
A_1 B_1
\vdots
A_{N-1} B_{N-1}
V_1 \ldots V_K

Output

Print the answer.

Sample Input 1

7 3
1 2
1 3
2 4
2 5
3 6
3 7
1 3 5

Sample Output 1

4

The given tree is shown on the left in the figure below. The tree with the minimum number of vertices that includes all of vertices 1,3,5 is shown on the right.

Figure

Sample Input 2

4 4
3 1
1 4
2 1
1 2 3 4

Sample Output 2

4

Sample Input 3

5 1
1 4
2 3
5 2
1 2
1

Sample Output 3

1