AtCoder Beginner Contest 126

C問題

問題文読んでそのまま書いたらACだった

D問題

問題文読んでそのまま書いたらTLEだった。

親の頂点からの距離が偶数か奇数で子の頂点の色が決まることはわかったが、親から順番に子を辿っていって色判定しているとTLEになる。 原因は辺の情報を[1, 2] のようなリストのまま持っていて、親が決まったと時に、子を探すのにリストの1,2つめの要素を両方見ていかないと行けなくて、根から頂点を辿っていくときの効率が悪かった。

children_of = [[] for _ in range(N)]
children_of[1].append(2)
children_of[2].append(1)

のように、双方向で辺の情報を持っておいて、ある頂点につながっている頂点をO(1)で出せる状態にしたらACした。