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

2 secs 1024 MB
Tonegawac's icon Tonegawac

問題文

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

  • 圧縮後の木の頂点の集合を VV^{\prime}、辺の集合を EE^{\prime} とする。
  • V:={lca(x,y)x,yV}V^{\prime} := \lbrace lca(x, y) | x, y \in V\rbrace
  • E:={{x,y}x,yV,xy,Tのパス(x,y)x,y以外のVに含まれる頂点が現れない}E^{\prime} := \lbrace \lbrace x, y\rbrace | x, y \in V^{\prime}, x \neq y, Tのパス(x, y)にx, y以外のV^{\prime}に含まれる頂点が現れない\rbrace

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

制約

  • 1N1051 \leq N \leq 10^5
  • 1VN1 \leq |V| \leq N
  • 0xi,yi,ai<N0 \leq x_i, y_i, a_i < N

入力

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

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行目に VV^{\prime} の要素数、2行目にVV^{\prime} の要素を頂点番号順にソートしたものを、3行目以降に EE^{\prime} の要素をソートしたものを出力してください。
辺のソートについて、{xi,yi}\lbrace x_i, y_i\rbrace{xi+1,yi+1}\lbrace x_{i+1}, y_{i+1}\rbrace(xi<yi)(xi+1<yi+1)(xi<xi+1(xi=xi+1yi<yi+1))(x_i < y_i)\land (x_{i+1} < y_{i+1})\land(x_i < x_{i+1} \lor (x_i = x_{i+1} \land y_i < y_{i+1}))
を満たすようにソートしてください。

サンプル

入力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

Submit


Go (1.21)