AtCoder Beginner Contest 223 G 問題 Vertex Deletion

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

グラフ $G$ の最大マッチングの大きさを $\mu(G)$ とする. 木 $T$ に対し, $\mu(G)=\mu(G-v)$ を満たす頂点の数を求めよ.

制約

$2 \leq N \leq 2 \times 10^5$
$1 \leq u_i \lt v_i \leq N$
グラフは木

解法1: $\mu(G)$ を求める.

まず, $\mu(G)$ を求めることにする. 木DP で求めることにする. $T$ を適当な頂点 ${\rm root}$ を根とする根付き木とする. 頂点 $v$ に対して, ${\rm DP}[v,T/F]$ で, 「頂点 $v$ を根とする部分木で, 頂点 $v$ をマッチングに含め (る/ない) 場合の最大の大きさ」とする. このとき, ${\rm ch}(v)$ で頂点 $v$ の子全体の集合とすると,

$\displaystyle {\rm DP}[v,F]=\sum_{w \in {\rm ch}(v)} \max ({\rm DP}[w,F], {\rm DP}[w,T])$

$\displaystyle {\rm DP}[v,T]=\begin{cases} \displaystyle \max_{u \in {\rm ch}(v)} \left( {\rm DP}[u,F]-\max({\rm DP}[u,F],{\rm DP}[u,T]) \right)+{\rm DP}[v,F]+1 & ({\rm ch}(v) \neq \emptyset) \\\\ 0 & ({\rm ch}(v)=\emptyset) \end{cases}$

である.

(理由)

${\rm DP}[v,F]$ について, 頂点 $v$ を根とする部分木のうち, 頂点 $v$ を使わないので, 各 $w \in {\rm ch}(v)$ に対して, $w$ を根とする部分木の問題に帰着できる. $w$ を根とする部分木における最大マッチングの大きさは $\max ({\rm DP}[w,F], {\rm DP}[w,T])$ であるので, この総和になる.
${\rm DP}[v,T]$ について, ${\rm ch}(v)=\emptyset$ のとき, $v$ を根とする部分根付き木は $1$ 頂点しかないので, ${\rm DP}[v,T]=0$ である. ${\rm ch}(v) \neq \emptyset$ とする. 頂点 $v$ と $u \in {\rm ch}(v)$ をマッチングさせるとする. $u$ 以外の子を根とする部分木においては上の場合と同様, $u$ を根とする部分木においては, $u$ を使わない最大マッチングを採用することになる. そして, この $u \in {\rm ch}(u)$ は任意に選ぶことができる. よって,

$\begin{align} {\rm DP}[v,T] &=\max_{u \in {\rm ch}(v)} \left(\sum_{\substack{w \in {\rm ch}(v) \\ w \neq u}} \max({\rm DP}[w,F],{\rm DP}[w,T]) )+{\rm DP}[u,F]+1 \right) \\ &=\max_{u \in {\rm ch}(v)} \left( \sum_{w \in {\rm ch}(v)} \max({\rm DP}[w,F],{\rm DP}[w,T]) )- \max({\rm DP}[u,F],{\rm DP}[u,T])+{\rm DP}[u,F]+1 \right) \\ &=\max_{u \in {\rm ch}(v)} \left( {\rm DP}[w,F]-\max({\rm DP}[u,F],{\rm DP}[u,T])+{\rm DP}[u,F]+1 \right)\\ &=\max_{u \in {\rm ch}(v)} \left( {\rm DP}[u,F]-\max({\rm DP}[u,F],{\rm DP}[u,T]) \right)+{\rm DP}[w,F]+1\\ \end{align}$

となる.

このとき, $\mu(G)=\max({\rm DP}[{\rm root},F], {\rm DP}[{\rm root},T])$ である.

解法2: 条件を満たす頂点を求める.

各頂点 $v$ に対して, $\mu(G)=\mu(G-v)$ であることと, ${\rm DP}[v,F]=\mu(G)$ であることは同値になる. 解法1を参考にすることにより, 各頂点を根とする根付き木において, ${\rm DP}_v[v,F$ ] を求められれば良さそうである. ただし, 実際にそうすると, 計算量が $\Theta(N^2)$ となり間に合わない. しかし, 各頂点を根と見なした場合の値がほしいので, 全方位木DPで求めることになる.

全方位木DPで求めるために, $V$ を頂点集合として, 適切な集合 $X$ と, モノイド $(M, \circ)$ 及び, $f:X \times V \times V \to M, g: M \times V \to X$ を構築する.

$X:=\mathbb{N} \times \mathbb{N}$
モノイド
- $M:=\mathbb{N} \times \mathbb{Z}$
- $\langle x,y \rangle \circ \langle x',y' \rangle=\langle x+x', \max(y,y')\rangle$
- 単位元 $e=(0,-\infty)$
$f:X \times V \times V \to M; ( (\alpha, \beta), v,w) \mapsto (\alpha, \beta)$
$g: M \times V \to X; (\langle x,y \rangle,v) \mapsto (x,\max(0,x+y+1)))$