指定された頂点たちの最小共通祖先関係を保って木を圧縮してできる補助的な木

2 secs 1024 MB
Tonegawac
Tweet
問題
提出
テストケース
解説

問題文

頂点 辺からなる根付き木 と、頂点の部分集合 に対して、木の圧縮を以下のように定義します。

  • 圧縮後の木の頂点の集合を 、辺の集合を とする。

頂点 を根とする根付き木 と頂点の部分集合 が与えられるので、これを圧縮してください。

制約

入力

入力はすべて整数である。

N
x_1 y_1
x_2 y_2
.
.
.
x_N-1 y_N-1
|V|
a_1 a_2 a_3 ... a_|V|

出力

|V'|
a_1 a_2 a_3 ... a_|V'|
x_1 y_1
x_2 y_2
.
.
.
x_|V'|-1 y_|V'|-1

1行目に の要素数、2行目に の要素を頂点番号順にソートしたものを、3行目以降に の要素をソートしたものを出力してください。
辺のソートについて、とが
を満たすようにソートしてください。

サンプル

入力1
10
1 5
1 0
0 3
1 7
7 2
5 6
2 4
7 9
9 8
4
0 2 4 5
出力1
5
0 1 2 4 5
0 1
1 2
1 5
2 4
入力2
10
4 5
4 6
6 0
0 1
6 9
5 3
4 8
1 2
5 7
4
2 5 7 9
出力2
6
0 2 5 6 7 9
0 2
0 6
5 6
5 7
6 9

提出

Go (1.14)