結果
問題 | No.277 根掘り葉掘り |
ユーザー |
|
提出日時 | 2021-07-18 23:45:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 84 ms / 3,000 ms |
コード長 | 1,304 bytes |
コンパイル時間 | 1,932 ms |
コンパイル使用メモリ | 201,076 KB |
最終ジャッジ日時 | 2025-01-23 03:15:38 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;int R[100005];int L[100005];vector <int> adj[100005];int n, x, y;void dfs(int now,int prev){for (auto next : adj[now]){if (prev == next) continue;R[next] = R[now] + 1;dfs(next, now);}}int solve(int now, int prev){if (L[now] != -1){return L[now];}int res = 1e9;for (auto next : adj[now]){if (prev == next){continue;}res = min(res, solve(next, now) + 1);}if (res >= 1e9){res = 0;}L[now] = res;return L[now];}void dfs2(int now, int prev, int U){multiset <int> S;L[now] = min(L[now], U);for (auto next : adj[now]){if (next == prev) continue;S.insert(L[next] + 1);}for (auto next : adj[now]){if (prev == next) continue;S.erase(L[next] + 1);if (!S.empty()){int MIN = *S.begin();MIN = min(MIN, U);dfs2(next, now, MIN + 1);}else{dfs2(next, now, U + 1);}S.insert(L[next] + 1);}}int main(void){cin.tie(0);ios::sync_with_stdio(false);cin >> n;for (int i = 0; i < n - 1; i++){cin >> x >> y;adj[x].push_back(y);adj[y].push_back(x);}memset(L, -1, sizeof(L));R[1] = 0;dfs(1, 0);solve(1, 0);dfs2(1, 0, 1e9);for (int i = 1; i <= n; i++){cout << min(L[i], R[i]) << '\n';}return 0;}