結果
問題 | No.277 根掘り葉掘り |
ユーザー |
|
提出日時 | 2015-09-04 22:42:45 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 204 ms / 3,000 ms |
コード長 | 1,113 bytes |
コンパイル時間 | 1,739 ms |
コンパイル使用メモリ | 161,764 KB |
実行使用メモリ | 15,872 KB |
最終ジャッジ日時 | 2024-07-19 01:20:17 |
合計ジャッジ時間 | 4,779 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>#define rep(i, a) for (int i = 0; i < (a); i++)#define rep2(i, a, b) for (int i = (a); i < (b); i++)#define repr(i, a) for (int i = (a) - 1; i >= 0; i--)#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)using namespace std;typedef long long ll;const int inf = 1e9;int N;vector<int> G[101010];int R[101010];int L[101010];void dfs(int curr, int prev) {for (int next : G[curr]) if (next != prev) {R[next] = R[curr] + 1;dfs(next, curr);}}int dfs2(int curr, int prev) {int res = inf;bool leaf = true;for (int next : G[curr]) if (next != prev) {int d = dfs2(next, curr);res = min(res, d + 1);leaf = false;}if (leaf) return L[curr] = 0;return L[curr] = res;}void dfs3(int curr, int prev) {for (int next : G[curr]) if (next != prev) {L[next] = min(L[next], L[curr] + 1);dfs3(next, curr);}}int main() {cin >> N;rep (i, N - 1) {int x, y;cin >> x >> y;x--; y--;G[x].push_back(y);G[y].push_back(x);}dfs(0, -1);dfs2(0, -1);dfs3(0, -1);rep (i, N) {cout << min(R[i], L[i]) << endl;}return 0;}