結果

問題 No.277 根掘り葉掘り
コンテスト
ユーザー たこし
提出日時 2015-11-03 23:48:40
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 237 ms / 3,000 ms
コード長 2,128 bytes
コンパイル時間 1,077 ms
コンパイル使用メモリ 99,624 KB
実行使用メモリ 17,864 KB
最終ジャッジ日時 2024-09-13 12:20:57
合計ジャッジ時間 5,539 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>

#define INF 100000000
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long

using namespace std;

#define MAX_N 100005

int N;
vector<int> Edge[MAX_N];

class cNode{
public:
	int RootLength;
	int LeafLength;
	bool LeafFlag;

	cNode(){
		RootLength = 0;
		LeafLength = -1;
		LeafFlag = false;
	}

}Node[MAX_N];

void Input(){

	cin >> N;
	for (int i = 0; i < N - 1; i++){
		int x, y;
		cin >> x >> y;
		Edge[x].push_back(y);
		Edge[y].push_back(x);
	}

}

void RootToLeaf(int pos, int pre, int len){

	Node[pos].RootLength = len;
	bool leafFlag = true;
	
	for (int i = 0; i < Edge[pos].size(); i++){
		if (Edge[pos][i] == pre)
			continue;
		leafFlag = false;
		RootToLeaf(Edge[pos][i], pos, len + 1);
	}

	if (leafFlag){
		Node[pos].LeafFlag = true;
	}

}

void Calc(){

	//各ノードについて根からの距離を求める
	//ついでに葉かどうかも調べる
	RootToLeaf(1, -1, 0);

	//直近の葉からの距離を幅優先で調べる
	typedef pair<int, int> II;
	queue<II> que;
	for (int i = 1; i <= N; i++){
		if (Node[i].LeafFlag)
			que.push(II(i, 0));
	}

	while (que.size()){
	
		II p = que.front();
		que.pop();

		int pos = p.first;
		int len = p.second;

		if (Node[pos].LeafLength >= 0)
			continue;

		Node[pos].LeafLength = len;
		
		for (int i = 0; i < Edge[pos].size(); i++){
			if (Node[Edge[pos][i]].LeafLength == -1){
				que.push(II(Edge[pos][i], len + 1));
			}
		}
	
	}

}

void Solve(){

	for (int i = 1; i <= N; i++){
		cout << min(Node[i].RootLength, Node[i].LeafLength) << endl;
	}

}

int main(){

	Input();

	Calc();

	Solve();

	return 0;

}
0