hitoare https://blog.hatena.ne.jp/hitoare/ hitoare日記 https://hitoare.hatenablog.com/ 競技プログラミング AtCoder ABC 問題リンク atcoder.jp 問題概要 \(N\)頂点の木が与えられる。\(N-1\)本の辺を白または黒に塗り分ける方法であって、次の\(M\)個の条件全てを満たすものはいくつあるか。 条件\(i(1≦i≦M) \) : \(u_i\)と\(v_i\)を結ぶパスの間に、黒い辺が少なくとも1つ存在する 解法 条件\(1…M\)を1つでも満たさない物の個数を数え、最後に\(2^{N-1}\)から引いて答えを求める。 各辺に適当に番号を振っておく。 点\(u_i\)と\(v_i\)を結ぶパスに含まれる辺の集合を\(P_i\)とすると、条件iを満たさないことと\(P_i\)に含まれる辺が全て白く塗… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fhitoare.hatenablog.com%2Fentry%2F2020%2F01%2F19%2F224145" title="F - Tree and Constraints (AtCoder Beginner Contest 152) - hitoare日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-01-19 22:41:45 rich https://hitoare.hatenablog.com/entry/2020/01/19/224145 1.0 100%