pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #395 (Div. 1) A. Timofey and a tree

http://codeforces.com/contest/763/problem/A

問題概要

木が与えられる。各頂点には色がついている。頂点をひとつ選び削除したとき、分離されたどの部分木も単色であるような削除の仕方を答えよ。

解法

union find を用いて隣接する同じ色のノードをまとめておく。

ある頂点 u が答えだったとしよう。この頂点と隣接する頂点 v1, v2 ... vm としたとき、root(u), root(v1), root(v2) ... root(vm) のなかに全てのグループが現れるなら全ての部分木は単色である。