betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ Codeforces プログラミング 競技プログラミング Problem - C - Codeforces 考察が重かったけど、面白い問題。 問題概要 頂点の木が与えられる。この木の辺それぞれについて辺を取り除くかどうかを考えると、その場合の数は全部で 通りある。そのうち「辺を取り除いた後のグラフにおいて、最大マッチングが一意に定まる」という条件を満たす場合の数を数え、 で割った余りを出力せよ。 制約 与えられるグラフは木 解法 木の最大マッチングが一意に定まる条件 辺を取り除いたあとのグラフはいくつかの部分木になる。そのため、まずは木の最大マッチングが一意に定まる条件を考える。部分木全てがその条件を満たしているとき、その辺の取り除き方は問題の条件を… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2018%2F11%2F20%2F004647" title="Codeforces Round #522 C. Vasya and Maximum Matching - ARMERIA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/b/betrue12/20181119/20181119234315.png Hatena Blog https://hatena.blog 2018-11-20 00:46:47 rich https://betrue12.hateblo.jp/entry/2018/11/20/004647 1.0 100%