Codeforces Round #522 C. Vasya and Maximum Matching

考察が重かったけど、面白い問題。

問題概要

$n$ 頂点の木が与えられる。この木の辺それぞれについて辺を取り除くかどうかを考えると、その場合の数は全部で $2^{n-1}$ 通りある。そのうち「辺を取り除いた後のグラフにおいて、最大マッチングが一意に定まる」という条件を満たす場合の数を数え、 $998244353$ で割った余りを出力せよ。

制約

$1 \le n \le 3\times 10^{5}$
与えられるグラフは木

解法

木の最大マッチングが一意に定まる条件

辺を取り除いたあとのグラフはいくつかの部分木になる。そのため、まずは木の最大マッチングが一意に定まる条件を考える。部分木全てがその条件を満たしているとき、その辺の取り除き方は問題の条件を満たす。

頂点の数が1つであるとき。最大マッチングは当然0個なので条件を満たす。
頂点の数が3以上の奇数であるとき。どれだけマッチングを作っても必ず1つ以上頂点が余ってしまい、余った頂点と隣接する頂点でペアを作り変えることができてしまう。そのため条件を満たさない。
頂点の数が2以上の偶数であるとき。もし完全マッチングが存在するならばこれは一意に定まる。完全マッチングが存在しないならば、余っている頂点があるので前項と同じ理由で条件を満たさない。

ということで、頂点数が偶数のときに完全マッチングが存在するかどうかを考える。例えば、以下のようなグラフは完全マッチングを作れない。

f:id:betrue12:20181119234315p:plain

より一般的に言うと、適当に根を決めて葉からDPをしたときに、途中で「2つ以上の子について、その子以下の部分木の頂点数が奇数である」という頂点が1つでも見つかってしまうとアウトである。

これで木の最大マッチングが一意に定まる条件を洗い出せたので、本題を考えていく。

木DPをする

本題の数え上げでも、適当に根を決めて葉からDPをしていく。

以降、辺を取り除くことによって部分木を確定させることを「完成させる」と呼び、完成された部分木全てについて完全マッチングが一意に定まることを「正当である」と呼ぶことにする。

正当性を保つためにやってはいけないことは2つあり、

頂点数が3以上の奇数の部分木を完成させる。
2つ以上の、子を含む部分木の頂点数が奇数であるような子について、その両方からの辺を残す。

である。こうならないような辺の取り除き方を数えていく。

DPの変数として、ある頂点 $i$ 以下の辺の取り除き方の総数であって、 $i$ 以下のグラフが正当であり、頂点 $i$ を含む部分木の頂点数が

1であるもの： $dp_{1}\lbrack i \rbrack$
2以上の偶数であるもの： $dp_{2}\lbrack i \rbrack$
3以上の奇数であるもの： $dp_{3}\lbrack i \rbrack$

とする。先ほど見たようにこの3パターンで部分木の性質が違うため、分けて数える。

$dp_{1}\lbrack i \rbrack$ を求める

頂点 $i$ と子の辺を全て切るしかない。このとき、子が含まれる部分木の頂点数が3以上の奇数であってはいけないので、

$dp_{1}\lbrack i \rbrack = \Pi_{j} (dp_{1}\lbrack j \rbrack + dp_{2}\lbrack j \rbrack)$

となる。ここで $j$ は $i$ の子を示す（以下も同様）。

$dp_{3}\lbrack i \rbrack$ を求める

そのままでは数えづらいので、 $dp_{1}\lbrack i \rbrack$ と合わせて部分木の頂点の個数が奇数個になる場合を考える。

複数の子から奇数個の頂点を繋いでくることはできないため、子からは偶数個の頂点を繋ぐかまたは辺を切り、頂点 $i$ 自身と合わせて奇数個になるというパターンしかない。つまり各子について、

子が含まれる部分木の頂点数は偶数個であり、頂点 $i$ と辺を繋ぐ。
子が含まれる部分木の頂点数は偶数個であり、頂点 $i$ と辺を繋がない。
子が含まれる部分木の頂点数は1個であり、頂点 $i$ と辺を繋がない。

の3パターンのどれかを採用することができる。数式は

$dp_{1}\lbrack i \rbrack + dp_{3}\lbrack i \rbrack = \Pi_{j} (dp_{1}\lbrack j \rbrack + 2\times dp_{2}\lbrack j \rbrack)$

となる。先ほど $dp_{1}\lbrack i \rbrack$ は求めたので、 $dp_{3}\lbrack i \rbrack$ を求めることができる。

$dp_{2}\lbrack i \rbrack$ を求める

これが少し厄介。子のうちどれか1つから奇数個の頂点を繋ぎ、残りの子は繋がないか偶数個の頂点を繋ぎ、頂点 $i$ 自身と合わせて頂点数が偶数個になるパターンである。

どの子から奇数個の頂点を繋ぐかを全部考えるため、

$dp_{2} \lbrack i \rbrack = \sum_{j}\left((dp_{1}\lbrack j \rbrack + dp_{3}\lbrack j \rbrack) \times \Pi_{k\ne j}(dp_{1}\lbrack k \rbrack + 2\times dp_{2}\lbrack k \rbrack)\right)$