ホームに戻る
全方位木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;
}

inserted by FC2 system