Problem:

Rooted Trees

A graph G = (V, E) is a data structure where V is a finite set of vertices and E is a binary relation on V represented by a set of edges. Fig. 1 illustrates an example of a graph (or graphs).

Fig. 1

A free tree is a connnected, acyclic, undirected graph. A rooted tree is a free tree in which one of the vertices is distinguished from the others. A vertex of a rooted tree is called "node."

Your task is to write a program which reports the following information for each node u of a given rooted tree T:

node ID of u

parent of u

depth of u

node type (root, internal node or leaf)

a list of chidlren of u

If the last edge on the path from the root r of a tree T to a node x is (p, x), then p is the parent of x, and x is a child of p. The root is the only node in T with no parent.

siblings.

-->

A node with no children is an external node or leaf. A nonleaf node is an internal node

The number of children of a node x in a rooted tree T is called the degree of x.

The length of the path from the root r to a node x is the depth of x in T.

Here, the given tree consists of n nodes and evey node has a unique ID from 0 to n-1.

Fig. 2 shows an example of rooted trees where ID of each node is indicated by a number in a circle (node). The example corresponds to the first sample input.

Fig. 2

Input

The first line of the input includes an integer n, the number of nodes of the tree.

In the next n lines, the information of each node u is given in the following format:

id k c1 c2 ... ck

where id is the node ID of u, k is the degree of u, c1 ... ck are node IDs of 1st, ... kth child of u. If the node does not have a child, the k is 0.

Output

Print the information of each node in the following format ordered by IDs:

node id: parent = p, depth = d, type, [c1...ck]

p is ID of its parent. If the node does not have a parent, print -1.

d is depth of the node.

type is a type of nodes represented by a string (root, internal node or leaf). If the root can be considered as a leaf or an internal node, print root.

c1...ck is the list of children as a ordered tree.

Please follow the format presented in a sample output below.

Constraints

1 ≤ n ≤ 100000

Sample Input 1

13
0 3 1 4 10
1 2 2 3
2 0
3 0
4 3 5 6 7
5 0
6 0
7 2 8 9
8 0
9 0
10 2 11 12
11 0
12 0

Sample Output 1

node 0: parent = -1, depth = 0, root, [1, 4, 10]
node 1: parent = 0, depth = 1, internal node, [2, 3]
node 2: parent = 1, depth = 2, leaf, []
node 3: parent = 1, depth = 2, leaf, []
node 4: parent = 0, depth = 1, internal node, [5, 6, 7]
node 5: parent = 4, depth = 2, leaf, []
node 6: parent = 4, depth = 2, leaf, []
node 7: parent = 4, depth = 2, internal node, [8, 9]
node 8: parent = 7, depth = 3, leaf, []
node 9: parent = 7, depth = 3, leaf, []
node 10: parent = 0, depth = 1, internal node, [11, 12]
node 11: parent = 10, depth = 2, leaf, []
node 12: parent = 10, depth = 2, leaf, []

Sample Input 2

4
1 3 3 2 0
0 0
3 0
2 0

Sample Output 2

node 0: parent = 1, depth = 1, leaf, []
node 1: parent = -1, depth = 0, root, [3, 2, 0]
node 2: parent = 1, depth = 1, leaf, []
node 3: parent = 1, depth = 1, leaf, []

Note

You can use a left-child, right-sibling representation to implement a tree which has the following data:

the parent of u

the leftmost child of u

the immediate right sibling of u

Template in C

-->

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.



Sample input:
13
0 3 1 4 10
1 2 2 3
2 0
3 0
4 3 5 6 7
5 0
6 0
7 2 8 9
8 0
9 0
10 2 11 12
11 0
12 0


Sample output:
node 0: parent = -1, depth = 0, root, [1, 4, 10]
node 1: parent = 0, depth = 1, internal node, [2, 3]
node 2: parent = 1, depth = 2, leaf, []
node 3: parent = 1, depth = 2, leaf, []
node 4: parent = 0, depth = 1, internal node, [5, 6, 7]
node 5: parent = 4, depth = 2, leaf, []
node 6: parent = 4, depth = 2, leaf, []
node 7: parent = 4, depth = 2, internal node, [8, 9]
node 8: parent = 7, depth = 3, leaf, []
node 9: parent = 7, depth = 3, leaf, []
node 10: parent = 0, depth = 1, internal node, [11, 12]
node 11: parent = 10, depth = 2, leaf, []
node 12: parent = 10, depth = 2, leaf, []

Submission status: Accepted

Solution code:
class Trees():
    def __init__(self):
        self.nodes = {}
    def add_nodes(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)
    def add_child(self, id, child_id):
        self.add_nodes(child_id)
        self.nodes[id].add_child_id(self.nodes[child_id])
        
class Node():
    def __init__(self, id):
        self.node = id
        self.parent = None
        self.depth = 0
        self.nodetype = 'root'
        self.children = []
    
    def add_child_id(self, child):
        child.parent = self
        self.children.append(child)
        child.update_depth()
        self.update_nodetype()
        child.update_nodetype()
    
    def update_depth(self):
        depth = self.depth
        if self.parent:
            self.depth = self.parent.depth + 1
        if depth != self.depth:
            for child in self.children:
                child.update_depth()

    
    def update_nodetype(self):
        if self.depth == 0:
            self.nodetype = 'root'
        elif len(self.children) > 0:
            self.nodetype = 'internal node'
        else:
            self.nodetype = 'leaf'
    
    def __str__(self):
        parent = self.parent.node if self.parent else -1
        children = ', '.join([str(node.node) for node in self.children])
        return 'node {}: parent = {}, depth = {}, {}, [{}]'.format(self.node, parent, 
                                                                   self.depth, self.nodetype, children)
    

tree = Trees()

n = int(input())

for i in range(n):
    a = list(map(int,input().split()))
    tree.add_nodes(a[0])
    for child in a[2:]:
        tree.add_child(id=a[0], child_id=child)

for id in range(n):
    print(f"{tree.nodes[id]}")

Submission status: Accepted

Solution code:
class Node:
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.children=[]
        self.degree=0
        self.depth=-1
        self.state="leaf"




def get_depth(Tree,node,depth):
    for child in node.children:
        Tree[child].depth=depth+1
        get_depth(Tree,Tree[child],depth+1)



Tree=[]
n=int(input())
for i in range(n):
    Tree.append(Node())
for loop in range(n):
    info=list(map(int,input().split()))
    i=info[0]
    Tree[i].name=info[0]
    Tree[i].degree=info[1]
    for j in range(2,len(info)):
        (Tree[i].children).append(info[j])
        Tree[i].state="internal node"
        Tree[info[j]].parent=i


for node in Tree:
    if(node.parent==-1):
        node.state="root"
        node.depth=0
        get_depth(Tree,node,0)



        


for node in Tree:
    print(f"node {node.name}: parent = {node.parent}, depth = {node.depth}, {node.state}, {node.children}")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
writelines = sys.stdout.writelines
N = int(readline())
depth = [0]*N
PR = [-1]*N
G = [None]*N
for i in range(N):
    i, _, *cs, = map(int, readline().split())
    G[i] = cs
    for v in G[i]:
        PR[v] = i
def dfs(v, d):
    depth[v] = d
    for w in G[v]:
        dfs(w, d+1)
dfs(PR.index(-1), 0)
writelines(["node %d: parent = %d, depth = %d, %s, %s\n" % (i, PR[i], depth[i], ('root' if PR[i] == -1 else 'leaf' if len(G[i]) == 0 else 'internal node'), G[i]) for i in range(N)])

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline())
parent = [-1 for _ in range(n)]
children = [[] for _ in range(n)]
nodes = []
for _ in range(n):
    ll = list(map(int, sys.stdin.readline().split()))
    nodes.append(ll[0])
    children[ll[0]] = ll[2:]
    for i in range(ll[1]):
        parent[ll[2+i]] = ll[0]

for n in sorted(nodes):
    p = parent[n]
    if p==-1:
        type='root'
    else:
        if len(children[n])==0:
            type='leaf'
        else:
            type='internal node'
        
    depth = 0
    k=n
    while parent[k]>=0:
        k = parent[k]
        depth+=1
        
    print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(n, p, depth, type, children[n]))

Submission status: Accepted

Solution code:
def getDepth(u):
    d = 0
    while node_list[u].parent != -1:
        u = node_list[u].parent
        d += 1
    return d
def getChildren(u):
    c = node_list[u].left
    child_list = []
    while c != -1:
        child_list.append(c)
        c = node_list[c].right
    return child_list

def getType(u):
    if node_list[u].parent == -1:
        return "root"
    if node_list[u].left == -1:
        return "leaf"
    return "internal node"
max_value = 10 ** 10
nil = -1

class Node():
    " node of the tree structure"
    def __init__(self, name = -1, parent = -1, left = -1, right = -1):
        self.name = name
        self.parent = parent
        self.left = left
        self.right = right
node_list = []
n = int(input())
for i in range(n):
    node = Node()
    node_list.append(node)

for i in range(n):
    a,b,*args = map(int, input().split())
    for j in range(b):
        if j == 0:
            node_list[a].left = args[j]
        else:
            node_list[l].right = args[j]
        l = args[j]
        node_list[args[j]].parent = a


#for i in range(n):

for i in range(n):
    print("node", str(i) + ":" , "parent =", str(node_list[i].parent) + ",", "depth =", str(getDepth(i)) + ",", getType(i) + ",", getChildren(i))

Submission status: Accepted

Solution code:
from collections import deque
from enum import Enum
import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

class Node:
    def __init__(self):
        self.parent_id = -1
        self.depth = 0
        self.children = []

global nodes

def calc_depth(node_id,arg_depth):

    nodes[node_id].depth = arg_depth
    for child in nodes[node_id].children:
        calc_depth(child, arg_depth+1)


V = int(input())

nodes = []
#あらかじめ、V個のノードを用意しておく
for loop in range(V):
    node = Node()
    nodes.append(node)

#親子関係の取得
for loop in range(V):

    table = list(map(int,input().split()))
    node_id = table[0]
    num = table[1]

    for i in range(num):
        child_id = table[2+i]
        nodes[node_id].children.append(child_id)
        nodes[child_id].parent_id = node_id


#根を探して、深さを計算する
for i in range(V):
    if nodes[i].parent_id == -1:
        calc_depth(i,0)
        break


for i in range(V):

    print("node %d: parent = %d, depth = %d, "%(i,nodes[i].parent_id,nodes[i].depth),end = "")

    if nodes[i].parent_id == -1:
        print("root,",end = "")
    else:
        if len(nodes[i].children) == 0: #葉
            print("leaf,",end = "")
        else: #節
            print("internal node,",end = "")

    print(" [",end = "")
    print(', '.join(map(str,nodes[i].children)),end = "")
    print("]")

Submission status: Accepted

Solution code:
n = int(input())
nodes = []
par_kid = {}
depthnot0 = []
for i in range(n):
    node = list(map(int, input().split()))
    nodes.append(node)
    if (node[1] != 0):
        par_kid[node[0]] = node[2:]
        depthnot0 += node[2:]
for i in range(n):
    if (i not in depthnot0):
        first_node = i
        break
#print(first_node)
##depth만 계산 가능하다면 다 print가능.
par_dep = {first_node:(-1,0)}
def pd(f):
    if (len(par_kid) == 0):
        return 0
    A = par_kid[f]
    c = 0
    for a in A:
        par_dep[a] = (f,par_dep[f][1]+1)
        if (a not in par_kid.keys()):
            c += 1
            continue
        pd(a)
    if (c == len(A)):
        return 0
s = pd(first_node)
    
for i in range(n):
    parent = par_dep[i][0]
    depth = par_dep[i][1]
    if (n == 1):
        print('node 0: parent = -1, depth = 0, root, []')
    elif (i == first_node):
        print('node {}: parent = {}, depth = {}, root,'.format(i,parent,depth), par_kid[i])
    elif (i in par_kid.keys()):
        print('node {}: parent = {}, depth = {}, internal node,'.format(i,parent,depth), par_kid[i])
    else:
        print('node {}: parent = {}, depth = {}, leaf, []'.format(i,parent,depth))

Submission status: Accepted

Solution code:
n = int(input())

class Node():
    def __init__(self):
        self.parent = None
        self.left_child = None
        self.right_sibling = None
        self.type = None

tree = []
for _ in range(n):
    tree.append(Node())

for _ in range(n):
    tmp = list(map(int, input().split()))
    id = tmp[0]
    degree = tmp[1]
    children = tmp[2:]
    if degree > 0:
        tree[id].left_child = children[0]
        for (cnt, child) in enumerate(children):
            tree[child].parent = id
            if cnt < degree - 1:
                tree[child].right_sibling = children[cnt + 1]
    
    
def get_depth(id):
    out = 0
    node = tree[id]
    while node.parent is not None:
        out += 1
        node = tree[node.parent]
    return out

def get_children(id):
    left_child_id = tree[id].left_child
    if left_child_id is None:
        return []
    node = tree[left_child_id]
    out = [left_child_id]
    while node.right_sibling is not None:
        out.append(node.right_sibling)
        node = tree[node.right_sibling]
    return out

def get_type(id):
    node = tree[id]
    if node.parent is None:
        return 'root'
    elif node.left_child is not None:
        return 'internal node'
    else:
        return 'leaf'
    
for id in range(n):
    print(f"node {id}: parent = {-1 if tree[id].parent is None else tree[id].parent}, depth = {get_depth(id)}, {get_type(id)}, {get_children(id)}")

Submission status: Accepted

Solution code:
# copy
class Tree():
    def __init__(self):
        self.nodes = {}

    def add_node(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)

    def add_child(self, parent_id, child_id):
        self.add_node(parent_id)
        self.add_node(child_id)
        self.nodes[parent_id].add_child(self.nodes[child_id])


class Node():
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.children = []
        self.depth = 0
        self.nodetype = 'root'

    def add_child(self, child):
        self.children.append(child)
        child.parent = self
        child.update_depth()
        child.update_nodetype()
        self.update_nodetype()
        if self.parent:
            self.parent.update_nodetype()

    def update_depth(self):
        depth = self.depth
        if self.parent:
            self.depth = self.parent.depth + 1
        if depth != self.depth:
            for child in self.children:
                child.update_depth()

    def update_nodetype(self):
        if self.parent:
            if len(self.children):
                self.nodetype = 'internal node'
            else:
                self.nodetype = 'leaf'
        else:
            self.nodetype = 'root'

    def walk(self):
        yield self
        for child in self.children:
            for node in child.walk():
                yield node

    def __str__(self):
        parent = self.parent.id if self.parent else -1
        children = ', '.join([str(node.id) for node in self.children])
        return 'node {}: parent = {}, depth = {}, {}, [{}]'.format(self.id,
                                                                   parent,
                                                                   self.depth,
                                                                   self.nodetype,
                                                                   children)


tree = Tree()

n = int(input())
for i in range(n):
    line = input().split()
    id = int(line[0])
    tree.add_node(id)
    for ci in map(int, line[2:]):
        tree.add_child(id, ci)

for id in sorted(tree.nodes):
    print(tree.nodes[id])

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, nid, k, c):
        self.nid = nid
        self.parent = -1
        self.depth = 0
        if k == 0:
            self.type = "leaf"
        else:
            self.type = "internal node"
        self.c = c
    
    def dump(self):
        print("node {}: parent = {}, depth = {}, {}, {}".format(self.nid,self.parent,self.depth,self.type,self.c))
from collections import deque
n = int(input())
T = [[int(j) for j in i] for i in [input().split() for i in range(n)]]
D = {}
for i in T:
    D[i[0]] = Node(i[0],i[1],i[2:])
    
for i in range(n):
    for j in D[i].c:
        D[j].parent = D[i].nid
rootid = 0
while(True):
    if D[rootid].parent == -1:
        break
    else:
        rootid = D[rootid].parent
D[rootid].type = "root"
d = deque()
d.append(D[rootid])
while(len(d)>0):
    tmp = d.pop()
    if tmp.parent == -1:
        pass
    else:
        tmp.depth = D[tmp.parent].depth + 1
    for i in tmp.c:
        d.appendleft(D[i])
for i in range(n):
    D[i].dump()

Submission status: Accepted

Solution code:
# Tree - Rooted Trees
class Node:
    def __init__(self, idnty):
        self.id = idnty
        self.parent = None
        self.children = []
        self.depth = 0
    def __str__(self):
        prnt = self.parent.id if self.parent else -1
        typ = 'root'
        if self.depth > 0: typ = 'internal node'
        if self.depth > 0 and not self.children: typ = 'leaf'
        cld = [n.id for n in self.children]
        return 'node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(self.id, prnt, self.depth, typ, cld)

n = int(input())
tr = [Node(i) for i in range(n)]
for _ in range(n):
    rl = list(map(int, input().split()))
    id, k = rl[0],rl[1]
    if k > 0:
        for i in rl[2:]:
            c = tr[i]
            c.parent = tr[id]
            c.depth += tr[id].depth + 1
            tr[id].children.append(c)
    else:
        p = tr[id].parent
        if p:
            tr[id].depth = p.depth + 1
for t in tr: print(t)

Submission status: Runtime Error

Solution code:
N = int(input())

def get_parent(node):
    parent = -1
    if "parent" in node:
        parent = node["parent"]
    return parent

def get_depth(node):
    depth = 0
    while "parent" not in node:
        depth += 1
        parent = node["parent"]
        node = rooted_tree[parent]
    return depth

def get_node_type(node):
    if "parent" in node:
        return "root"
    if "left" in node:
        return "leaf"
    return "internal node"

def get_children(node):
    if "left" not in node:
        return "[]"
    left = node["left"]
    siblings = []
    siblings.append(str(left))
    while rooted_tree[left]["right"] > -1:
        right = rooted_tree[left]["right"]
        siblings.append(str(right))
        left = right
    return "[{}]".format(", ".join(siblings))

rooted_tree = [{} for i in range(N)]
for id in range(N):
    row = input()
    _, degree, *children = list(map(int, row.split()))
    if degree > 0:
        rooted_tree[id]["left"] = children[0]
        for i in range(len(children)):
            child_id = children[i]
            right = -1
            if i < len(children)-1:
                right = children[i+1]
            rooted_tree[child_id]["right"] = right
            rooted_tree[child_id]["parent"] = id

for id in range(N):
    node = rooted_tree[id]
    parent = get_parent(node)
    depth = get_depth(node)
    node_type = get_node_type(node)
    children = get_children(node)
    print("node {}: parent = {}, depth = {}, {}, {}".format(id, parent, depth, node_type, children))

Submission status: Runtime Error

Solution code:
N = int(input())

def get_parent(node):
    parent = -1
    if "parent" in node:
        parent = node["parent"]
    return parent

def get_node_type(node):
    if "parent" not in node:
        return "root"
    if "left" not in node:
        return "leaf"
    return "internal node"

def get_children(node):
    if "left" not in node:
        return "[]"
    left = node["left"]
    siblings = []
    siblings.append(str(left))
    while rooted_tree[left]["right"] > -1:
        right = rooted_tree[left]["right"]
        siblings.append(str(right))
        left = right
    return "[{}]".format(", ".join(siblings))

def rec(node_id, depth):
    Depth[node_id] = str(depth)
    if "right" in rooted_tree[node_id]:
        rec(rooted_tree[node_id]["right"], depth)
    if "left" in rooted_tree[node_id]:
        rec(rooted_tree[node_id]["left"], depth+1)


rooted_tree = [{} for i in range(N)]
for _ in range(N):
    row = input()
    id, degree, *children = list(map(int, row.split()))
    if degree > 0:
        rooted_tree[id]["left"] = children[0]
        for i in range(len(children)):
            child_id = children[i]
            right = -1
            if i < len(children)-1:
                right = children[i+1]
            rooted_tree[child_id]["right"] = right
            rooted_tree[child_id]["parent"] = id

root = 0
for i in range(N):
    if "parent" not in rooted_tree[i]:
        root == i
        break
Depth = {}
rec(root, 0)

for id in range(N):
    node = rooted_tree[id]
    parent = get_parent(node)
    node_type = get_node_type(node)
    children = get_children(node)
    print("node {}: parent = {}, depth = {}, {}, {}".format(id, parent, Depth[id], node_type, children))

Submission status: Runtime Error

Solution code:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static class Node {
		int id;
		int parentId;
		int depth;
		int[] children;
		public Node(int id, int parentId) {
			this.id = id;
			this.parentId = parentId;
			this.children = null;
			this.depth = 0;
		}
		public void setChildlen(int[] childlen) {
			this.children = childlen;
		}
		public void setParentId(int parentId) {
			this.parentId = parentId;
		}
		public void setDepth(int depth) {
			this.depth = depth;
		}
		private String getType() {
			if (depth == 0) {
				return "root";
			}
			if (children == null || children.length == 0) {
				return "leaf";
			}
			return "internal node";
		}		
		public String toString() {
			StringBuilder sb = new StringBuilder();
			sb.append("node " + id + ": ");
			sb.append("parent = " + parentId + ", ");
			sb.append("depth = " + depth + ", ");
			sb.append(getType() + ", ");
			sb.append(Arrays.toString(children));
			return sb.toString();
		}
	}
		
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(reader.readLine());
		Node[] nodes = new Node[n];

		for (int i = 0; i < n; i++) {
			
			StringTokenizer st = new StringTokenizer(reader.readLine());
			
			int id = Integer.parseInt(st.nextToken());
			if (nodes[id] == null) {
				nodes[id] = new Node(id, -1);
			}
			
			int m = Integer.parseInt(st.nextToken());
			int[] children = new int[m];
			for (int j = 0; j < m; j++) {
				int childId = Integer.parseInt(st.nextToken());
				children[j] = childId;
				if (nodes[childId] == null) {
					nodes[childId] = new Node(childId, id);
				} else {
					nodes[childId].setParentId(id);
				}
				nodes[childId].setDepth(nodes[id].depth + 1);
			}
			nodes[id].setChildlen(children);
		}
		
		for (Node node : nodes) {
			System.out.println(node);
		}
	}
}

Submission status: Runtime Error

Solution code:
class Node:
	def __init__(self, id):
		self.id = id
		self.parent_id = -1
		self.depth = -1
		self.children = None
	def get_type(self):
		if self.parent_id == -1:
			return 'root'
		elif self.children == None or len(self.children) == 0:
			return 'leaf'
		return 'internal node'
	def __str__(self):
		strNode = 'node ' + str(self.id) + ': '
		strNode += 'parent = ' + str(self.parent_id) + ', '
		strNode += 'depth = ' + str(self.depth) + ', '
		strNode += self.get_type() + ', ['
		if len(self.children) > 0:
			strNode += str(self.children[0])
			for i in range(1, len(self.children)):
				strNode +=  ', ' + str(self.children[i])
		strNode += ']'
		return strNode

def calc_depth(nodes):
	stack = []
	for i in range(len(nodes)):
		if nodes[i].parent_id == -1:
			nodes[i].depth = 0
			stack.append(nodes[i].id)
			break
	while len(stack) != 0:
		node = nodes[stack.pop()]
		for i in range(len(node.children)):
			child_id = node.children[i]
			nodes[child_id].depth = node.depth + 1
			stack.append(child_id)

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
	a = list(map(int, input().split()))
	id = a[0]
	m = a[1]
	children = [0] * m
	for j in range(m):
		child_id = a[2 + j]
		child = nodes[child_id]
		child.parent_id = id
		children[j] = child_id
	nodes[id].children = children

calc_depth(nodes)

for i in range(n):

Submission status: Runtime Error

Solution code:
from sys import stdin

class Node(object):
    def __init__(self, parent=None, children=None, name=None, depth=None):
        self.parent = parent
        self.children = children
        self.name = name
        self.depth = depth

def set_depth(nodes, u):
    p = nodes[u].parent
    d = nodes[p].depth
    if d != None and p != -1:
        nodes[u].depth = d + 1

def read_rooted_tree(n, nodes):
    for _ in range(n):
        i = [int(i) for i in stdin.readline().strip().split()]
        c = i[2:len(i)]
        nodes[i[0]].children = c
        if nodes[i[0]].name != "root":
            if c:
                nodes[i[0]].name = "internal node"
            else:
                nodes[i[0]].name = "leaf"
        for j in nodes[i[0]].children:
            nodes[j].parent = i[0]
        set_depth(nodes, i[0])

n = int(input())
nodes = [Node() for _ in range(n)]
nodes[0].parent = -1
nodes[0].depth = 0
nodes[0].name = "root"
read_rooted_tree(n, nodes)
for i in range(n):
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(
           i, nodes[i].parent, nodes[i].depth, nodes[i].name, nodes[i].children))

Submission status: Runtime Error

Solution code:
#! /usr/local/bin/python3
# coding: utf-8


class Node():
    def __init__(self, parent=-1, child=[]):
        self.parent = parent
        self.child = child


def node_depth(u, id):
    if u[id].parent == -1:
        return 0
    else:
        return node_depth(u, u[id].parent) + 1


def node_type(u, id):
    if u[id].parent == -1:
        return "root"
    elif u[id].child == []:
        return "leaf"
    else:
        return "internal node"


def main():
    n = int(input())
    u = [Node() for _ in range(n)]

    for i in range(n):
        _, _, *child = (int(x) for x in input().split())
        u[i].child = child
        for c in child:
            u[c].parent = i

    for i in range(n):
        print("node {}: parent = {}, depth = {}, {}, {}".
              format(i, u[i].parent,
                     node_depth(u, i), node_type(u, i),
                     u[i].child))


main()

Submission status: Runtime Error

Solution code:
#! /usr/local/bin/python3
# coding: utf-8

from sys import setrecursionlimit

setrecursionlimit(21)


class Node():
    def __init__(self, parent=-1, child=[]):
        self.parent = parent
        self.child = child


def node_depth(u, id):
    if u[id].parent == -1:
        return 0
    else:
        return node_depth(u, u[id].parent) + 1


def node_type(u, id):
    if u[id].parent == -1:
        return "root"
    elif u[id].child == []:
        return "leaf"
    else:
        return "internal node"


def main():
    n = int(input())
    u = [Node() for _ in range(n)]

    for i in range(n):
        _, _, *child = (int(x) for x in input().split())
        u[i].child = child
        for c in child:
            u[c].parent = i

    for i in range(n):
        print("node {}: parent = {}, depth = {}, {}, {}".
              format(i, u[i].parent,
                     node_depth(u, i), node_type(u, i),
                     u[i].child))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#! /usr/local/bin/python3
# coding: utf-8

from sys import setrecursionlimit

setrecursionlimit(22)


class Node():
    def __init__(self, parent=-1, child=[]):
        self.parent = parent
        self.child = child


def node_depth(u, id):
    if u[id].parent == -1:
        return 0
    else:
        return node_depth(u, u[id].parent) + 1


def node_type(u, id):
    if u[id].parent == -1:
        return "root"
    elif u[id].child == []:
        return "leaf"
    else:
        return "internal node"


def main():
    n = int(input())
    u = [Node() for _ in range(n)]

    for i in range(n):
        _, _, *child = (int(x) for x in input().split())
        u[i].child = child
        for c in child:
            u[c].parent = i

    for i in range(n):
        print("node {}: parent = {}, depth = {}, {}, {}".
              format(i, u[i].parent,
                     node_depth(u, i), node_type(u, i),
                     u[i].child))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class Node():
    NIL = -1

    def __init__(self, parent=NIL, left=NIL, right=NIL, depth=-1):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth

def read_nodes(T):
    for _ in range(len(T)):
        id, _, *child = [int(x) for x in input().split()]
        for i, c in enumerate(child):
            if i == 0:
                T[id].left = c
            else:
                T[l].right = c
            l = c
            T[c].parent = id

def calc_depth(T):

    def rec(r, p):
        nonlocal T

        T[r].depth = p
        if T[r].right != Node.NIL:
            rec(T[r].right, p)
        if T[r].left != Node.NIL:
            rec(T[r].left, p + 1)

    rec([u.parent for u in T].index(-1), 0)

def node_type(T, id):
    if T[id].parent == Node.NIL:
        return "root"
    elif T[id].left == Node.NIL:
        return "leaf"
    else:
        return "internal node"

def child(T, id):
    c = []
    i = T[id].left
    while i != Node.NIL:
        c.append(i)
        i = T[i].right
    return c

def print_nodes(T):
    for id in range(len(T)):
        print("node {}: parent = {}, depth = {}, {}, {}".
              format(id, T[id].parent, T[id].depth,
                     node_type(T, id), child(T, id)))

def main():
    n = int(input())
    T = [Node() for _ in range(n)]

    read_nodes(T)
    calc_depth(T)
    print_nodes(T)

main()

Submission status: Runtime Error

Solution code:
   from sys import setrecursionlimit
   setrecursionlimit(1000)
   
   class Node():
    NIL = -1

    def __init__(self, parent=NIL, left=NIL, right=NIL, depth=-1):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth

def read_nodes(T):
    for _ in range(len(T)):
        id, _, *child = [int(x) for x in input().split()]
        for i, c in enumerate(child):
            if i == 0:
                T[id].left = c
            else:
                T[l].right = c
            l = c
            T[c].parent = id

def calc_depth(T):

    def rec(r, p):
        nonlocal T

        T[r].depth = p
        if T[r].right != Node.NIL:
            rec(T[r].right, p)
        if T[r].left != Node.NIL:
            rec(T[r].left, p + 1)

    rec([u.parent for u in T].index(-1), 0)

def node_type(T, id):
    if T[id].parent == Node.NIL:
        return "root"
    elif T[id].left == Node.NIL:
        return "leaf"
    else:
        return "internal node"

def child(T, id):
    c = []
    i = T[id].left
    while i != Node.NIL:
        c.append(i)
        i = T[i].right
    return c

def print_nodes(T):
    for id in range(len(T)):
        print("node {}: parent = {}, depth = {}, {}, {}".
              format(id, T[id].parent, T[id].depth,
                     node_type(T, id), child(T, id)))

def main():
    n = int(input())
    T = [Node() for _ in range(n)]

    read_nodes(T)
    calc_depth(T)
    print_nodes(T)

main()