D - Coloring Edges on Tree

・問題URL

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

・思考

・各頂点から出てる辺の最大値が使う種類なのはわかる
・問題は各辺の色をどうやって復元するか
・辺に色塗るの初めてでやばい

・キーワード

・DFS

・解法

・答えはiの昇順に出力しなきゃダメだから、隣接リストにつながってる頂点だけでなく辺のindexも入れる。pair使えばいいね
・void dfs(現在の頂点、今禁じられた色now(now=1,2,3...))としてDFSする。スタートは結局貪欲に色を決めていくだけだからどこでもよく禁じられた色もないからdfs(0,0)で始める。
・ある頂点に注目し、そこから伸びている辺(スター的な)について、使った色をsetに入れて、次使う色を決めるときに、色xがsetに所属している限りx++する。んでその頂点を見終わってより深い探索をするときに、xを使えない色としてsetを初期化してxだけ入れる。ついでにxの最大値を更新していく。

・コード

using graph = vector<vector<pair<ll, ll>>>;
graph G(100100);
bool seen[100100];
int ans[100100];
int MaxColor = 0;

void dfs(int v, int now) {
   set<int>color;
   seen[v] = true;
   int count = 1;
   color.insert(now);
   for (auto nv : G[v]) {
       int next, idx;
       tie(next, idx) = nv;
       if (seen[next])continue;
       while (color.count(count)) {
           count++;
       }
       ans[idx] = count;
       color.insert(count);
       MaxColor = MAX(MaxColor, count);
       dfs(next, count);

   }
}

int main() {

   int N;
   cin >> N;
   rep(i, N - 1) {
       int a, b;
       cin >> a >> b;
       a--; b--;
       G[a].push_back({ b,i });
       G[a].push_back({ a,i });
   }

   dfs(0, 0);

   cout << MaxColor << endl;
   rep(i, N - 1)cout << ans[i] << endl;

}