結果

問題 No.277 根掘り葉掘り
ユーザー koba-e964
提出日時 2015-09-10 10:44:10
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 206 ms / 3,000 ms
コード長 1,235 bytes
コンパイル時間 515 ms
コンパイル使用メモリ 67,840 KB
実行使用メモリ 17,280 KB
最終ジャッジ日時 2024-07-19 05:12:11
合計ジャッジ時間 3,687 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <queue>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef pair<int, int> PI;

const int N = 100100;

VI edges[N];

int rd[N], ld[N];

VI leaves;

void dfs(int v, int par = -1) {
  if (par == -1) {
    rd[v] = 0;
  } else {
    rd[v] = rd[par] + 1;
  }
  int child = 0;
  REP(i, 0, edges[v].size()) {
    int w = edges[v][i];
    if (w == par) { continue; }
    dfs(w, v);
    child++;
  }
  if (child == 0) {
    leaves.push_back(v);
  }
}


void bfs(void) {
  queue<PI> que;
  REP(i, 0, leaves.size()) {
    que.push(PI(leaves[i], 0));
  }
  while (!que.empty()) {
    PI t = que.front(); que.pop();
    int x = t.first;
    int d = t.second;
    if (ld[x] >= 0) {
      continue;
    }
    REP(i, 0, edges[x].size()) {
      int y = edges[x][i];
      que.push(PI(y, d + 1));
    }
    ld[x] = d;
  }
}

int main(void){
  int n;
  cin >> n;
  REP(i, 0, n - 1) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    edges[x].push_back(y);
    edges[y].push_back(x);
  }
  REP(i, 0, n) {
    rd[i] = -1;
    ld[i] = -1;
  }
  dfs(0);
  bfs();
  REP(i, 0, n) {
    cout << min(rd[i], ld[i]) << endl;
  }
}
0