第三回日本最強プログラマー学生選手権-予選- (AtCoder Beginner Contest 262) E - Red and Blue Graph (500)
解説の解法
赤く塗った頂点に繋がっている辺の数を数えると、赤同士の辺は2回、赤と青の辺は1回数えられる
ここから異なる色同士の辺が偶数であることと赤で奇数頂点の数が偶数であることが同値であることが分かる
偶数の赤い奇数頂点の個数の場合でそれぞれ調べた場合の数の和が答え
奇数頂点と遇す有頂天の個数をそれぞれ事前に求めておく
奇数頂点から$ i個選んだ場合と偶数頂点から$ K-i個選んだ場合の席を加える