結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2015-12-18 04:34:44 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 201 ms / 3,000 ms |
コード長 | 2,185 bytes |
コンパイル時間 | 631 ms |
コンパイル使用メモリ | 77,228 KB |
実行使用メモリ | 17,536 KB |
最終ジャッジ日時 | 2024-09-16 08:29:32 |
合計ジャッジ時間 | 3,734 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include<iostream>#include<string>#include<vector>#include<queue>#include<stack>#include<map>#include<set>#include<algorithm>#include<functional>#include<cstdio>#include<cstdlib>#include<cmath>using namespace std;#define mind(a,b) (a>b?b:a)#define maxd(a,b) (a>b?a:b)#define absd(x) (x<0?-(x):x)#define pow2(x) ((x)*(x))#define rep(i,n) for(int i=0; i<n; ++i)#define repr(i,n) for(int i=n-1; i>=0; --i)#define repl(i,s,n) for(int i=s; i<=n; ++i)#define replr(i,s,n) for(int i=n; i>=s; --i)#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)#define repe(e,obj) for(auto e : obj)#define SP << " " <<#define COL << " : " <<#define COM << ", " <<#define ARR << " -> " <<#define PNT(STR) cout << STR << endl#define POS(X,Y) "(" << X << ", " << Y << ")"#define DEB(A) " (" << #A << ") " << A#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl#define ALL(V) (V).begin(), (V).end()#define INF 1000000007#define INFLL 10000000000000000007LL#define EPS 1e-9typedef unsigned int uint;typedef unsigned long ulong;typedef unsigned long long ull;typedef long long ll;typedef long double ld;typedef pair<int, int> P;//typedef pair<ll, ll> P;typedef pair<P, int> PI;typedef pair<int, P> IP;typedef pair<P, P> PP;typedef priority_queue<P, vector<P>, greater<P> > pvqueue;#define N 100007vector<int> g[N];int n;int ans[N];int dist[N];vector<int> le;int dfs(int v, int c, int f) {int ret = N;if(g[v].size()==1 && g[v][0]==f) {le.push_back(v);ans[v] = 0;return 1;}rep(i, g[v].size()) {int t = g[v][i];if(t == f) continue;int r = dfs(t, c+1, v);ret = mind(ret, r);}ans[v] = mind(c, ret);dist[v] = ret;return ret+1;}void d_dfs(int v, int f) {rep(i, g[v].size()) {int t = g[v][i];if(t == f) continue;if(dist[v]+1 < dist[t]) {dist[t] = dist[v]+1;ans[t] = mind(ans[t], dist[t]);}d_dfs(t, v);}}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, 0, -1);d_dfs(0, -1);rep(i, n) {cout << ans[i] << endl;}return 0;}