【競技プログラミング】AtCoder Beginner Contest 146_D問題

# 問題
https://atcoder.jp/contests/abc146/tasks/abc146_d

## 要約
1. 木Gは、N個の頂点と、N-1本の辺で構成される。
2. 頂点には1からNまでの番号が付いている。
3. i番目の辺は、頂点a_iと頂点b_iを結んでいる。

辺の色分けに関する条件：
1. 各頂点に接続する辺の色はすべて異なる必要がある。
2. 使用する色の数を最小にする必要がある。

上記の条件を満たす塗り分け方のうち、使用する色の数が最小となるものを1つ構築すること。

変数情報：
- N: 木の頂点数
- G: 与えられる木
- a_i, b_i: i番目の辺が結ぶ2つの頂点の番号

# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)


# 独り言
AtCoderでよく見る「彩色問題」なので、流石に慣れました。

# アプローチ

木の辺彩色問題を解くために、深さ優先探索（DFS）を用いて木を走査し、各辺に色を割り当てる。
使用する色の数は、木の最大次数（任意の頂点に接続する辺の最大数）に等しくなる。


# 解法手順

1. 入力から木の構造を隣接リストとして構築する。
2. 木の最大次数を計算し、これを使用する色の数とする。
3. DFSを用いて木を走査し、各辺に色を割り当てる。
4. 親頂点から子頂点への探索時に、使用可能な最小の色を割り当てる。
5. 親頂点に割り当てた色は子頂点では使用しない。
6. 全ての辺に色を割り当てた後、結果を出力する。



# ACコード
```python:ac.py
import sys

def io_func():
    # 再帰の深さ制限を設定
    sys.setrecursionlimit(10**9)
    
    # 頂点数Nを入力から読み取る
    n = int(input())
    
    # N個の空リストを持つ隣接リストgを作成
    g = [[] for _ in range(n)]
    
    # N-1本の辺の情報を入力から読み取り、隣接リストgに追加
    for i in range(n-1):
        a, b = map(int, input().split())
        a -= 1  # 0-indexedに調整
        b -= 1
        g[a].append((b, i))
        g[b].append((a, i))
    
    return n, g

def solve(n, g):
    # 最大次数sizeを計算し、出力
    size = max(len(x) for x in g)
    print(size)
    
    # 辺の色を格納するリストansを初期化
    ans = [0] * (n-1)
    
    # DFSを行う関数fを定義
    def f(cur, par, col):
        x = 0  # 色のカウンター
        
        for to, i in g[cur]:
            if to != par:
                x += 1
                if x == col:  # 親との辺の色は避ける
                    x += 1
                ans[i] = x
                
                f(to, cur, x)
    
    # 根を0として、DFSを開始
    f(0, -1, -1)
    
    # 各辺の色をansから取り出し、出力
    print(*ans, sep='\n')

if __name__=="__main__":
    # メイン処理
    n, g = io_func()
    solve(n, g)

###
# - n: 頂点の数
# - g: 隣接リスト（各頂点に接続する辺と、その辺のインデックスを格納）
# - size: 最大次数（使用する色の数）
# - ans: 各辺に割り当てられた色を格納するリスト
# - cur: 現在の頂点
# - par: 親頂点
# - col: 親との辺の色
# - x: 現在割り当てている色
# - to: 子頂点
# - i: 辺のインデックス

# 1. io_func関数:
#    - 入力処理を行う
#    - 再帰の深さ制限を設定
#    - 頂点数と隣接リストを返す

# 2. solve関数:
#    - 最大次数を計算し出力
#    - DFSを行うf関数を定義
#    - f関数を使って木を走査し、辺に色を割り当てる
#    - 結果を出力

# 3. f関数（DFS）:
#    - 現在の頂点から子頂点へ探索
#    - 使用可能な最小の色を割り当てる
#    - 親との辺の色は避ける

# 4. メイン処理:
#    - io_func関数で入力を処理
#    - solve関数で問題を解く
```


# 思考過程

1. 木の構造を理解し、隣接リストで表現する。
2. 最大次数が必要な色の数と等しいことを認識する。
3. DFSを使って木を効率的に走査する方法を考える。
4. 各辺に色を割り当てる際、親との辺の色を避ける戦略を立てる。


# 計算量の概算

O(N)、ここでNは頂点の数。DFSで各頂点を1回ずつ訪れるため。
O(N)、隣接リストと結果を格納するリストのサイズ。

# その他周辺知識

## 再帰の深さ制限の設定

```python
sys.setrecursionlimit(10**9)
```

## 隣接リストの初期化

```python
g = [[] for _ in range(n)]
```


## 木構造を表現

```python
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))
```

このループは、`n-1`回繰り返される。
各反復で
- 2つの整数`a`と`b`を入力から読み取る。
- `a`と`b`から1を引いて0-indexedに調整する。
- `g[a]`に`(b, i)`のタプルを追加し、`g[b]`に`(a, i)`のタプルを追加する。
  ここで`i`は辺のインデックスを表す。

## 最大値

```python
size = max(len(x) for x in g)
```
隣接リスト`g`の各要素（各頂点の隣接リスト）の長さの最大値を計算する。
この`size`が最大次数、つまり必要な色の数となる。

## 深さ優先探索（DFS）
```python
def f(cur, par, col):
   x = 0
   for to, i in g[cur]:
       if to != par:
           x += 1
           if x == col:
               x += 1
           ans[i] = x
           f(to, cur, x)
```

この関数`f`は深さ優先探索（DFS）を実装している。
`cur`は現在の頂点、`par`は親頂点、`col`は親との辺の色を表す。
- `x`は現在割り当てている色を表す。
- 隣接する各頂点`to`に対して：
  - `to`が親でない場合、新しい色`x`を割り当てる。
  - もし`x`が親との辺の色`col`と同じなら、`x`を1増やす。
  - 辺の色を`ans[i]`に格納する。
  - 再帰的に`f(to, cur, x)`を呼び出す。