ABC146D - Coloring Edges on Tree - 競プロはじめました

考え方
回答例
注

考え方

任意の頂点を根として考えて良い．

根から順番に深さ方向に辺の色を決めていけば，まだ見ていない辺の色を決めるときに常に始点の色が定まった状態になっている．

そこで，根から順番に，子ノードに辺を伸ばしていくことを考える．始点の色が決まっているので

始点の色でない，最小の色cを選び，
終点（子ノード）と，今張った辺の色をcに確定する

という操作を繰り返せば答えが求まる（BFS）．

$K$は，使った色の最大数に一致する．

回答例

N = int(input())
G = [[] for _ in range(N)]
for i in range(N - 1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  G[a].append((b, i))
  G[b].append((a, i))

K = 0
color_e = [-1] * (N - 1)
color_v = [0] * N
que = [(-1, 0)]  # par, cur
while que:
  par_v, cur_v = que.pop()
  c = 1
  for chi_v, chi_e in G[cur_v]:
    if chi_v == par_v:
      continue
    if c == color_v[cur_v]:
      c += 1
    color_e[chi_e] = c
    color_v[chi_v] = c
    que.append((cur_v, chi_v))
    K = max(K, c)
    c += 1

print(K)
print(*color_e, sep = '\n')

注

定義などから当たり前であれば教えて下さい．

問題文から読み取れないが，頂点$v_{1}, v_{2}$に対し，「$v_{1} < v_{2}$」ならば「$v_{1}$の深さ < $v_{2}$の深さ」となっているらしい．

これを前提にしているものは，ACしているコードでも，例えば

という入力だと1色で塗り分けられるという結果が返ってくる．

例：Submission #8618162 - AtCoder Beginner Contest 146