AtCoder Beginner Contest 146：D - Coloring Edges on Tree

問題
解法
解答

問題

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

解法

まず，最も多くの辺が繋がっている頂点がもつ辺の数が必要となる色の数になる．また，ある 1 つの頂点を木の根とし，そこから辺を塗っていく DFS をする．具体的には，(今いる頂点, 親の頂点, 親と今いる頂点間の辺の色) の情報を持っておき，今いる頂点から伸びている辺は，色 (親と今いる頂点間の辺の色 + k (1 <= k <= 今いる頂点から子に伸びている辺の数)) で塗ればよい（色は mod K にする必要がある）．最後に，入力で与えられた辺の順番通りに答えを出力しなければいけないので，DFS で塗っていった順番から変換する必要がある．ここでソートなどを使うと O(NlogN)．