Coloring Edges on Tree [AtCoder Beginner Contest 146 D]

https://atcoder.jp/contests/abc146/tasks/abc146_d

解説

https://atcoder.jp/contests/abc146/submissions/8632543

貪欲に色を決めて塗っていけば達成できそう。
根を1つ決めて貪欲に色を塗っていく。
あとは、実装を頑張る。
各頂点で必要な色は次数と一致するので、次数が最大の所から順番に塗っていくのも手ではある。
（実装は変わらないか）

int N;
vector<pair<int,int>> E[101010];
//---------------------------------------------------------------------------------------------------
int ans[101010];
void dfs(int cu, int pa = -1, int col = 0) {
    set<int> used;
    used.insert(col);
    int c = 1;
    fore(to, E[cu]) if (to.first != pa) {
        while (used.count(c)) c++;
        ans[to.second] = c;
        dfs(to.first, cu, c);
        c++;
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;

        E[a].push_back({ b, i });
        E[b].push_back({ a, i });
    }

    dfs(0);

    int ma = 0;
    rep(i, 0, N) chmax(ma, (int)E[i].size());
    printf("%d\n", ma);
    rep(i, 0, N - 1) printf("%d\n", ans[i]);

}