CFR 781 A. Andryusha and Colored Balloons ( Greedy, DFS )

Problem - A - Codeforces

題意：
給一棵 N 個節點的樹，要求給每個節點著色，滿足所有長度為 2 的路徑裡的三個節點都異色。問最少顏色數量。

資料規模：
N ≤ 2e5

解法：
隨便找一個節點當作根，轉為有根樹上的問題。遞迴拜訪一個節點之前先為該節點著色。在當前的子樹問題中，只需考慮父節點的顏色和自身的顏色，以及深度差唯一的子節點，只要貪心總是分配最小的，無關順序分給子節點後繼續遞迴就可以。

時間 / 空間複雜度：
O( N lg N ) / O( N )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 2e5;

int N;
vector< int > G[ MAXN ];
int ans[ MAXN ];
int max_col = 1;

void dfs( int u, int fa ){
  int c = 1;
  set< int > ban;
  if( fa != - 1 ) ban.emplace( ans[ fa ] );
  ban.emplace( ans[ u ] );
  for( int v : G[ u ] ){
    if( v == fa ) continue;
    while( ban.count( c ) ) ++c;
    ans[ v ] = c;
    ban.emplace( c );
    max_col = max( max_col, c );
    ++c;
    dfs( v, u );
  }
}

signed main(){
  ios::sync_with_stdio( 0 );
  {
    cin >> N;
    for( int i = 0; i < N - 1; ++i ){
      int u, v;
      cin >> u >> v;
      --u, --v;
      G[ u ].emplace_back( v );
      G[ v ].emplace_back( u );
    }
  }
  {
    ans[ 0 ] = 1;
    dfs( 0, -1 );
  }
  {
    cout << max_col << "\n";
    for( int i = 0; i < N; ++i ){
      cout << ans[ i ] << " \n"[ i + 1 == N ];
    }
  }
  return 0;
}