/*
AOJ Algorithms and Data Structures I - Tree - Binary Trees

rooted tree と大体同じ。

まずは、木クラスを作っておく。

入力されたｎを一周回れば、parentは全部埋まる。
そっからroot見つけて、それ使って再帰で子を辿って行ってdepthを埋めていく。

heightは再帰関数に返り値つけて戻して使う。


nodeは初期値に、?１とか入れて埋めておく。

new: inputのとこで、順番に入れてって、後でソートするのではなく、
最初にIDを添え字にして、目当てのところに入れる。

(
子の数が２以下なので、　子が一つの時もありうる。
left rightなど決めてかからず rooted tree と同じように
degreeでやっていったほうがいい。
子が一つの時は、右も左もなく、degree=1 c配列の要素も１個
)
*/


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>


using namespace std;

class Rooted_Tree
{

public:
	int id;  //idはなくす。　全部添え字で管理　そうしないと配列内でidに対してfindしないといけなくなり、実行時間増えるので
	int parent;
	int sibling;
	int depth;
	int height;
	string type;
	int degree;
	vector<int> c;

	Rooted_Tree()
    {
        id = parent = sibling = depth = height = degree = -1;
		type = "non";
    }

};


//再帰で木をたどって行って、[深さ]を埋める
//再帰で戻ってきた　高さ(height) の中で最大のものを使う
int fill_depth(vector<Rooted_Tree> &rt, int id, int depth){
	int i, buf=-1;

	rt[id].depth=depth;
	rt[id].height=0;
	for(i=0;i<rt[id].degree;i++){
		buf = fill_depth(rt, rt[id].c[i], depth+1);
		if(buf>rt[id].height) rt[id].height=buf; 
	}
	return rt[id].height+1;
}

//vector内のidでのソート用　引数内で無名関数？クラス？　を宣言するのはレベル高くて意味不なのでやめとこう。
//　なんで動いてるのか意味不明の参考URL  http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=714973
//引数にconst 入れてないと動かない　なぜだ？
bool asc(const Rooted_Tree &right, const Rooted_Tree &left){ return right.id < left.id;}

int main() {
	int i,j,i_buf;
	int n;
	// id == 添え字　にするので　mapとかでもいいが、添え字をそのまま使痛いのでvector
	vector<Rooted_Tree> rt;

	//input
	// 標準入出力をファイルに変更////////////////////////////////////////////////////////
    //FILE* fp_in = freopen("\\\\k1300\\k1300\\s1350010\\.windows\\Desktop\\input_data.txt", "r", stdin);
	/////////////////////////////////////////////////////////////////////////////////////
	cin >> n;
	//rt.reserve(n); //メモリ変わらないようにしてくれるだけで、実体はないので[]演算子でのアクセスは出来る様にならない
	for(i=0; i<n; i++){
		Rooted_Tree buf;
		cin >> buf.id;
		buf.degree=0;
		for(j=0;j<2;j++){ //子は最大で２個
			cin >> i_buf;
			if(i_buf!=-1){ 
				buf.degree++; 
				buf.c.push_back(i_buf);
			}
		}
		rt.push_back(buf);
	}
	// ファイルを閉じる//////////////////////////////////////////////////////////////////
    //fclose(fp_in);
	/////////////////////////////////////////////////////////////////////////////////////
	

	//id==添え字　にする
	sort(rt.begin(), rt.end(), asc);
	
	// fill parent & sibling
	//ID==iのnodeが持っている子のnodeを埋めていく。
	//子が　(いない場合)、一人の場合、二人の場合の三つで場合分け。
	for(i=0; i<n; i++){
		if(rt[i].degree==1){ //一人の場合
			rt[ rt[i].c[0] ].parent=rt[i].id;
		}
		else if(rt[i].degree==2){ //二人の場合
			rt[ rt[i].c[0] ].parent=rt[i].id;
			rt[ rt[i].c[0] ].sibling=rt[i].c[1];

			rt[ rt[i].c[1] ].parent=rt[i].id;
			rt[ rt[i].c[1] ].sibling=rt[i].c[0];
		}
	}

	//fill type and depth and height
	for(i=0; i<n; i++){
		if(rt[i].parent==-1){
			rt[i].type = "root";
			i_buf = fill_depth(rt, i, 0); //rootから再帰させてすべてのdepth,heightを埋めていく //返り値 i_bufは特に何にも使わない
		}
		else{
			if(rt[i].degree!=0) rt[i].type = "internal node";
			else rt[i].type = "leaf";
		}
	}

	//出力
	for(i=0; i<n; i++){
		printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s\n", rt[i].id, rt[i].parent, rt[i].sibling, rt[i].degree, rt[i].depth, rt[i].height, rt[i].type.c_str());
	}
	
	
	return 0;
}

Measured memory_bytes: 1244