HL分解

// HL分解ではDAGのいくつかのノードを1つにまとめることができます。
// 特徴はノードをまとめることで深さがたかだかlogNになること。(個数ではない！)
// まとめるノードには分岐がないのでセグメント木やBITにのせることができること。

// 問題例(セグメント木)
// 100000のノードからなるDAGで各ノードは値を持つ。
// あるノードからあるノードまでの間のノードのうち最小の値を求めよというクエリが与えられる。
// 1つのクエリの処理がO((logN)^2)なので100000個のクエリの処理が可能。

// 問題例(BIT)
// 100000のノードからなるDAGで各ノードは値を持つ。
// あるノードからあるノードまでの間のノードの値の合計を求めよというクエリが与えられる。
// またあるノードの値を変更するクエリも与えられる。
// この場合も100000個のクエリの処理が可能。

// 赤ラインで繋がったノードをまとめたものをheavy_node(緑枠)とする。
// 水色ラインをlight_nodeと呼ぶ。
// ncはheavy_nodeの数。
// h_sizはheavy_nodeに含まれるノードの個数。
// p_nodeは現在のノードの親heavy_nodeの通し番号。(最上位ノードの親番号は-1)
// p_indexは現在のノードが所属するheavy_nodeが親ノードの何番目のノードに繋がっているか。
// h_nodeは現在のノードが所属するheavy_nodeの通し番号。
// h_indexは現在のノードが所属するheavy_nodeの何番目のノードか。



#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-1LL;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

#define MAX_N 100100

vector<vector<ll> > vv;

ll nc;
ll siz[MAX_N];
ll h_siz[MAX_N];
ll p_node[MAX_N];
ll p_index[MAX_N];
ll h_node[MAX_N];
ll h_index[MAX_N];

ll dfs_hld(ll a, ll p){
  ll ret = 1;
  if(vv[a].sz==1&&p!=-1){
    return 1;
  }
  rep(i,0,vv[a].sz){
    if(vv[a][i]==p)continue;
    ret += dfs_hld(vv[a][i],a);
  }
  siz[a] = ret;
  return ret;
}

void build_hld(ll a, ll p, ll n, ll index, ll parent, ll parent_index){
  p_node[a] = parent;
  p_index[a] = parent_index;
  h_node[a] = n;
  h_index[a] = index;
  if(vv[a].sz==1&&p!=-1){
    return;
  }
  rep(i,0,vv[a].sz){
    if(vv[a][i]==p)continue;
    if(siz[vv[a][i]]*2>=siz[a]){
      h_siz[n]++;
      build_hld(vv[a][i],a,n,index+1,parent,parent_index);
    }
    else{
      nc++;
      h_siz[nc]++;
      build_hld(vv[a][i],a,nc,0,n,index);
    }
  }
  return;
}

void const_hld(ll root){
  nc = 0;
  clr(siz,0);
  clr(h_siz,0);
  clr(p_node,0);
  clr(p_index,0);
  clr(h_node,0);
  clr(h_index,0);
  dfs_hld(root,-1);
  build_hld(root,-1,nc,0,-1,0);
}

int main() {
  ll n;
  cin>>n;
  vector<vector<ll> > vv_(n,vector<ll>());
  vv = vv_;
  rep(i,0,n-1){
    ll a,b;
    cin>>a>>b;
    a--;b--;
    vv[a].pb(b);
    vv[b].pb(a);
  }
  const_hld(0);
  rep(i,0,n){
    cout << h_node[i] << " " << h_index[i] << " " << p_node[i] << " " << p_index[i] << endl;
  }
  return 0;
}