ホームに戻る
全方位木DP
// 全方位木DPとは2回のDFSを行うことによって、
// すべてのノードについて目的の値を求めることができる。
// 例えば、あるノードを通るパスの最長の長さをすべてのノードについて行うことができる。
// DFSが2回なのでノードがN個あっても計算量はO(N)である。
// 以下のコードはあるノードを通るパスの最長の長さをすべてのノードについて行う
// vは子ノード情報、vvは枝情報を持つ。
// なお、子を持つノードは番兵を入れて必ず2つ以上の子ノードを持つようにする。
// dfs2内のbは親ノードからの距離であり、cは他の子ノードからの距離である。
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
#define MOD 1000000007
vector<vector<pair<ll,ll> > > v;
vector<vector<ll> > vv;
ll d[100100];
ll dfs1(ll a, ll p){
if(vv[a].sz==1&&p!=-1){
return 1;
}
v[a].pb(mp(0,-1)); // 番兵
rep(i,0,vv[a].sz){
if(vv[a][i]==p)continue;
v[a].pb(mp(dfs1(vv[a][i],a),vv[a][i]));
}
sort(all(v[a]));
reverse(all(v[a]));
return v[a][0].fi+1;
}
void dfs2(ll a, ll p, ll b){
if(vv[a].sz==1&&p!=-1){
d[a] = b;
return;
}
d[a] = v[a][0].fi + max(b,v[a][1].fi);
rep(i,0,vv[a].sz){
if(vv[a][i]==p)continue;
ll c = v[a][0].fi;
if(v[a][0].se==vv[a][i]){
c = v[a][1].fi;
}
dfs2(vv[a][i],a,max(b+1,c+1));
}
return;
}
int main() {
ll n;
cin>>n;
vector<vector<pair<ll,ll> > > v_(n,vector<pair<ll,ll> >());
vector<vector<ll> > vv_(n,vector<ll>());
v = v_;
vv = vv_;
rep(i,0,n-1){
ll a,b;
cin>>a>>b;
vv[a].pb(b);
vv[b].pb(a);
}
clr(d,0);
dfs1(0,-1);
dfs2(0,-1,0);
rep(i,0,n){
cout << d[i] << endl;
}
return 0;
}