Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 240 E問題 Ranges on Tree

AtCoder ABC ABC240 E問題 500 pts

問題

提出解答

問題の概要

頂点 $1$ を根とする根付き木がある. $j$ 番目の辺は頂点 $u_j, v_j$ を結ぶ.

自然数の部分集合 $[x,y]$ を $x$ 以上 $y$ 以下の整数全体の集合とする.

また, 頂点 $v$ に対して, $S_v$ で $v$ の子孫全体の集合とする.

以下を満たす $2N$ 個の整数の組 $(L_1, \dots, L_N, R_1, \dots, R_N)$ の内, $\max (L_1, \dots, L_N, R_1, \dots, R_N)$ を最小にするような一例を挙げよ.

$1 \leq L_i \leq R_i$
頂点について以下が成立する.
- $S_v \subset S_w$ ならば, $[L_v, R_v] \subset [L_w, R_w]$
- $S_v \cap S_w=\emptyset$ ならば, $[L_v, R_v] \cap [L_w, R_w]=\emptyset$

制約

$2 \leq N \leq 2 \times 10^5$
$1 \leq u_j, v_j \leq N$
グラフは木

解法

根付き木における葉の数を $t$ とする. このとき, $\max (L_1, \dots, L_N, R_1, \dots, R_N)=t$ であることを示す. ここで, $I_v:=[L_v, R_v ]$ とし, $t$ 個の葉を $p_1, \dots, p_t$ とする.

$1 \leq i,j \leq t$ において, $S_i=\{p_i \}$ より, $i \neq j$ ならば $S_i \cap S_j =\emptyset$ である. このことから, $I_1 \cup \dots \cup I_t$ は互いに素な集合の直和で, 少なくとも $t$ 個の要素を含む. よって, 最大値は $t$ 以上でなくてはならない.
$p_1, \dots, p_t$ について, ある DFS の行きがけ順に並び替えてもよいとする. 以降ではこれを仮定する. このとき, $k=1,2, \dots, t$ に対して, $L_{p_k}=R_{p_k}=k$ とする. 葉でない頂点 $v$ については, $v$ の子全体の集合を ${\rm ch}(v)$ としたとき,

$\displaystyle L_v=\min_{w \in {\rm ch}(v)} L_w, \quad R_v=\max_{w \in {\rm ch}(v)} R_w$

とすると包含に関する条件を満たし, 最大値も $t$ であることが示せる.

よって, このようにして一例を挙げることができた. 計算量は $O(N)$ である.