ABC146 D - Coloring Edges on Tree

問題原文

D - Coloring Edges on Tree

問題要旨

頂点の木の各辺を塗り分けることを考えます。このとき、各頂点について、その頂点から伸びる辺の色がすべて異なるようにしたいです。 この条件を満たす塗り分けの中で、使用する色の数が最小であるようなものをつ構築してください。

考えたこと

• 最大次数がそのまま必要な最小の色数になる。
• ある辺を塗ろうとした時に気になるのは、その親から根に向かって伸びる辺が何色で塗られているかということ。

難しいと感じたこと

実装が難しいと感じた。

1. 答えは入力される辺の順番通りに出力する必要がある → どうやってindexを覚えておこう？
2. 親から根に向かって伸びる辺（直前の辺の色）をどうやって記録しよう？
3. 「次に何色で塗るべきか」を毎回1からforで回すわけにはいかない

考えたかったこと

1. 各辺のindex情報はそのまま木に持たせる
2. 直前の辺の色はdfsの情報として持てば良い。
3. ある頂点からいける頂点を探索する時に、1から塗っていこうとすれば良い。
4. 3の過程で、「直前の辺の色」とバッティングする場合、その色を飛ばして次の色に変えれば良い。

実装

from collections import defaultdict
N = int(input())
tree = [[] for i in range(N)]  # 入力で与えられる木: [[to, 辺のindex],]
degrees = defaultdict(int)  # 各頂点の次数を記録

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


# 最大次数色使えば必ず塗り分けられる
ans_K = max(degrees.values())
ans_c = [-1] * (N - 1)


# dfs
stack = [[0, -1]]  # [現在見ている頂点, 直前を何色で塗ったか]
visited = [False] * N
while stack:
    fr, pre_color = stack.pop()
    visited[fr] = True
    painting = 1  # これから何色で塗ろうとするか

    for to, index in tree[fr]:
        if visited[to]:
            continue

        if painting == pre_color:
            painting += 1

        ans_c[index] = painting
        stack.append([to, painting])

        # 塗ったら違う色に変える
        painting += 1


# 出力
print(ans_K)
print(*ans_c, sep='\n')