>440
D問題なら、グラフの基本的な性質についての知識がつくと、見通し良くなるのでは。
今回の問題だと、
「グラフが木なら、2点間を結ぶパスはただ1つしかない。」
ことを知っていると（思い出せると）、塗り方の最適な戦略に気付くことが出来る。
そのパス上で貪欲に交互に色を塗っていき、パス上を塗り終えたら、両者の陣地が決まる。あとは、パスの衝突した点でグラフを2つに分けて、頂点を数えればいい。