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 Node:
    def __init__(self, num, parent, children):
        self.id = num
        self.parent = -1
        self.children = children
        self.depth = 0
        
    def show_info(self):
        print('node {0}: '.format(self.id), end = '')
        print('parent = {0}, '.format(self.parent), end = '')
        print('depth = {0}, '.format(self.depth), end = '')
        if self.children and self.parent != -1:
            print('internal node, ', end = '')
        elif self.parent != -1:
            print('leaf, ', end = '')
        else:
            print('root, ', end = '')
        print(self.children)


def set_node(i_s):
    i_l = list(map(int, i_s.split()))
    num = i_l[0]
    children = i_l[2:]
    node = Node(num, -1, children)
    T[num] = node
    for n in children:
        T[-1] -= n

def set_pd(node, parent, depth):
    node.parent = parent
    node.depth = depth
    for n in node.children:
        set_pd(T[n], node.id, depth + 1)


import sys

n = int(sys.stdin.readline())

T = [None for i in range(n)]

T.append(int(n * (n - 1) / 2))

for x in sys.stdin.readlines():
    set_node(x)

set_pd(T[T[-1]], -1, 0)

for n in T[:-1]:
    n.show_info()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, num, parent, children):
        self.id = num
        self.parent = -1
        self.children = children
        self.depth = 0
        
    def show_info(self):
        print('node {0}: '.format(self.id), end = '')
        print('parent = {0}, '.format(self.parent), end = '')
        print('depth = {0}, '.format(self.depth), end = '')
        if self.children and self.parent != -1:
            print('internal node, ', end = '')
        elif self.parent != -1:
            print('leaf, ', end = '')
        else:
            print('root, ', end = '')
        print(self.children)


def set_node(i_s):
    i_l = list(map(int, i_s.split()))
    num = i_l[0]
    children = i_l[2:]
    node = Node(num, -1, children)
    T[num] = node
    for n in children:
        T[-1] -= n

def set_pd(n_i, parent, depth):
    node = T[n_i]
    node.parent = parent
    node.depth = depth
    for n in node.children:
        set_pd(n, n_i, depth + 1)


import sys

n = int(sys.stdin.readline())

T = [None] * n

T.append(int(n * (n - 1) / 2))

for x in sys.stdin.readlines():
    set_node(x)

set_pd(T[-1], -1, 0)

for n in T[:-1]:
    n.show_info()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, num, parent, children):
        self.id = num
        self.parent = -1
        self.depth = 0
        self.type = None
        self.children = children
        
    def show_info(self):
        print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(self.id,
                                                                     self.parent,
                                                                     self.depth,
                                                                     self.type,
                                                                     self.children))


def set_node(i_s):
    i_l = list(map(int, i_s.split()))
    num = i_l[0]
    children = i_l[2:]
    node = Node(num, -1, children)
    T[num] = node
    for n in children:
        T[-1] -= n

def set_pdt(n_i, parent, depth):
    node = T[n_i]
    node.parent = parent
    node.depth = depth
    if node.children:
        node.type = 'internal node'
        for n in node.children:
            set_pdt(n, n_i, depth + 1)
    else:
        node.type = 'leaf'


import sys

n = int(sys.stdin.readline())

T = [None] * n

T.append(int(n * (n - 1) / 2))

for x in sys.stdin.readlines():
    set_node(x)

set_pdt(T[-1], -1, 0)

T[T[-1]].type ='root'

for n in T[:-1]:
    n.show_info()

Submission status: Accepted

Solution code:
from collections import deque, namedtuple

class RootedTree:
    def __init__(self, t, n):
        self.t = t
        self.n = n
        self.d = [-1] * n

    def setDepth(self, u, p):
        self.t[u] = self.t[u]._replace(d = p)
        for i in self.getChildren(u):
            self.setDepth(i, p + 1)

    def getChildren(self, u):
        ret = []
        c = self.t[u].l
        while c != -1:
            ret.append(c)
            c = self.t[c].r
        return(ret)

    def printNode(self, i):
        p_ = self.t[i].p
        d_ = self.t[i].d
        c_ = self.getChildren(i)
        if p_ == -1:
            t_ = "root"
        elif len(c_) == 0:
            t_ = "leaf"
        else:
            t_ = "internal node"
        print("node {}: parent = {}, depth = {}, {}, {}".format(i, p_, d_, t_, c_))

if __name__ == '__main__':
    n = int(input().rstrip())
    Node = namedtuple('Node', ['p', 'l', 'r', 'd'])
    t = [Node(-1, -1, -1, -1)] * n
    r = -1
    for i in range(n):
        tmp = deque([int(i) for i in input().rstrip().split(" ")])
        v = tmp.popleft()
        d = tmp.popleft()
        for j in range(d):
            c = tmp.popleft()
            if j == 0:
                t[v] = t[v]._replace(l = c)
            else:
                t[l] = t[l]._replace(r = c)
            l = c
            t[c] = t[c]._replace(p = v)
    for i in range(n):
        if (t[i].p == -1):
            r = i
    x = RootedTree(t, n)
    x.setDepth(r, 0)
    for i in range(n):
        x.printNode(i)

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self):
        self.parent = -1
        self.depth = 0
        self.child = []

n = int(input())
tree = [Tree() for i in range(n)]
for i in range(n):
    cmd = list(map(int, input().split()))
    node = tree[cmd[0]]
    node.child.extend(cmd[2:])
    for j in cmd[2:]:
        c = tree[j]
        c.parent = cmd[0]
for t in tree:
    d, p = 0, t.parent
    while p != -1:
        d += 1
        p = tree[p].parent
    t.depth = d
for i in range(n):
    t = tree[i]
    if t.parent == -1:
        state = 'root'
    elif t.child:
        state = 'internal node'
    else:
        state = 'leaf'
    print('node {}: parent = {}'.format(i, t.parent),
          'depth = {}'.format(t.depth),
          state,
          '[{}]'.format(', '.join(map(str, t.child))),
          sep=', ')

Submission status: Accepted

Solution code:
class Tree():

    def __init__(self):
        self.parent = -1
        self.depth = 0
        self.child = []

n = int(input())
tree = [Tree() for i in range(n)]
for i in range(n):
    cmd = list(map(int, input().split()))
    node = tree[cmd[0]]
    node.child.extend(cmd[2:])
    for j in cmd[2:]:
        tree[j].parent = cmd[0]

for t in tree:
    d, p = 0, t.parent
    while p != -1:
        d += 1
        p = tree[p].parent
    t.depth = d

for i in range(n):
    t = tree[i]
    if t.parent == -1:
        state = "root"
    elif t.child:
        state = "internal node"
    else:
        state = "leaf"
    print("node {}: parent = {}".format(i, t.parent), "depth = {}".format(
        t.depth), state, "[{}]".format(", ".join(map(str, t.child))), sep=", ")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

class Node_Class():
    def __init__(self, c_list):
        self.c_list = c_list

n = int(raw_input())
node_dic = {}
p_list = [0]*n
d_list = [0]*n
t_list = ['']*n
root = 0
for i in range(n):
    root += i
for i in range(n):
    line = map(str, raw_input().split())
    if int(line[1]) > 0:
        node_dic[int(line[0])] = Node_Class(map(int, line[2:]))
    else:
        node_dic[int(line[0])] = Node_Class([])
#parent
for i in range(n):
    for j in node_dic[i].c_list:
        p_list[j] = i
        root -= j
p_list[root] = -1
#depth
for i in range(n):
    j = i
    while p_list[j] > -1:
        j = p_list[j]
        d_list[i] += 1
#type
for i in range(n):
    if p_list[i] == -1:
        t_list[i] = t_list[i] + "root"
    else:
        if len(node_dic[i].c_list):
            t_list[i] = t_list[i] + "internal node"
        else:
            t_list[i] = t_list[i] + "leaf"
#print
for i in range(n):
    s = "node %d: parent = %d, depth = %d, %s," %(i, p_list[i], d_list[i], t_list[i])
    print s, node_dic[i].c_list

Submission status: Accepted

Solution code:


class Node:
    def __init__(self, num, children):
        self.num = num
        self.children = children
        self.parents = -1
        self.type = None
        self.depth = 0

    def output(self):
        print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(self.num,
                                                                      self.parents,
                                                                      self.depth,
                                                                      self.type,
                                                                      self.children))


def set_node(num, children):
    node = Node(num, children)
    T[num] = node
    for n in children:
        T[-1] -= n  # ?????£???T[-1]???root???????????????????????????


def set_pdt(n_i, parent, depth):
    node = T[n_i]
    node.parents = parent
    node.depth = depth
    if node.children:
        node.type = 'internal node'
        for n in node.children:
            set_pdt(n, n_i, depth + 1)
    else:
        node.type = 'leaf'


n = int(input())
tree = [list(map(int, input().split())) for i in range(n)]
T = [None] * n
T += [n * (n - 1) // 2]
for j in tree:
    set_node(j[0], j[2:])

set_pdt(T[-1], -1, 0)

T[T[-1]].type = 'root'

for n in T[:-1]:
    n.output()

Submission status: Accepted

Solution code:
import sys

class Node:
    def __init__(self):
        self.id = 0
        self.parent = -1
        self.depth = 0
        self.type = "root"
        self.children = []

def addDepth(id, tree):
    tree[id].depth += 1
    for child in tree[id].children:
        addDepth(child, tree)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    N = int(lines[0])
    del lines[0]

    tree = []
    for i in range(N):
        tree.append(Node())

    for line in lines:
        line = map(int, line.split())
        tree[line[0]].id = line[0]
        tree[line[0]].children = line[2:]

    for node in tree:
        for child in node.children:
            tree[child].parent = node.id
            addDepth(child, tree)
            if tree[child].children:
                tree[child].type = "internal node"
            else:
                tree[child].type = "leaf"

    for node in tree:
        print "node {0.id}: parent = {0.parent}, depth = {0.depth}, {0.type}, {0.children}".format(node)

Submission status: Accepted

Solution code:
import sys

class Node:
    def __init__(self):
        self.id = -1
        self.parent = -1
        self.type = "leaf"

    def printInfo(self):
        print "node {0.id}: parent = {0.parent}, depth = {0.depth}, {0.type}, {0.children}".format(self)

def setTree(id, tree, depth):
    tree[id].depth = depth
    if not tree[id].children:
        return

    for child in tree[id].children:
        tree[child].parent = id
        setTree(child, tree, depth + 1)
    tree[id].type = "internal node"

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    N = int(lines[0])
    del lines[0]

    tree = []
    for i in range(N):
        tree.append(Node())

    root = N * (N - 1) / 2
    for line in lines:
        info = map(int, line.split())
        tree[info[0]].children = info[2:]
        tree[info[0]].id = info[0]
        for i in tree[info[0]].children:
            root -= i

    setTree(root, tree, 0)
    tree[root].type = "root"

    for node in tree:
        node.printInfo()

Submission status: Accepted

Solution code:
from collections import namedtuple
Node = namedtuple('Node', ['parent', 'children'])

class my_tree:
    def __init__(self, N=[]):
        self.T = {}
        for ni in N: self.addNode(ni)

    def addNode(self, n):
        p = self.T.get(n[0],Node(-1,[None])).parent
        self.T[n[0]] = Node(p,n[2:])
        for c in n[2:]:
            cc = self.T.get(c,Node(-1,[None])).children
            self.T[c] = Node(n[0],cc)

    def getParent(self, i): return self.T[i].parent

    def getChildren(self, i): return self.T[i].children

    def getDepth(self, i):
        if self.T[i].parent == -1: return 0
        return self.getDepth(self.T[i].parent) + 1

    def getNodeType(self, i):
        if self.T[i].parent == -1: return 'root'
        if self.T[i].children    : return 'internal node'
        return 'leaf'

    def getIdList(self): return sorted(self.T.keys())

 
if __name__=='__main__':
    n = int(input())
    N = [None]*n
    for i in range(n): N[i] = list(map(int,input().split()))
    tree = my_tree(N)
     
    for i in tree.getIdList():        
        print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(\
                i, tree.getParent(i), tree.getDepth(i), tree.getNodeType(i), tree.getChildren(i)))

Submission status: Accepted

Solution code:
def set_info(i, p, d):
    r = T[i]
    r[1], r[2] = p, d
    for c in r[0]:
        set_info(c, i, d+1)

n = int(input())
T = [None] * n
root = set(range(n))

for i in range(n):
    A = list(map(int, input().split()))
    ch = A[2:]
    T[A[0]] = [ch, None, None]
    root -= set(ch)

set_info(root.pop(), -1, 0)

for i,node in enumerate(T):
    ch, p, d = node
    print('node {}: parent = {}, depth = {}, {}, {}'.format(
            i, p, d, 'root' if not d else 'internal node' if ch else 'leaf', ch
        ))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(100000)
class Node(object):
    # left????????¨??????????????????(leaf), right???s?????¨??????????????????????????????
    # ???????????????????????????????????¨???????????´??????parent???-1?????????
    def __init__(self, N):
        self.p = [-1 for i in range(N)]
        self.l = [-1 for i in range(N)]
        self.r = [-1 for i in range(N)]
        self.D = [0 for i in range(N)]

    def set_depth_rec(self, u, p):
        self.D[u] = p
        if self.r[u] is not -1:
            self.set_depth(self.r[u], p)
        if self.l[u] is not -1:
            self.set_depth(self.l[u], p+1)

    def set_depth(self, u):
        d = 0
        pre_u = u
        while self.p[u] is not -1:
            u = self.p[u]
            d += 1
        self.D[pre_u] = d

    def print_children(self, u):
        children = []
        flag = self.l[u]
        while flag is not -1:
            children.append(flag)
            flag = self.r[flag]
            
        return children
        

N = int(input())
T = Node(N)

for j in range(N):
    A = [int(i) for i in input().split()]
    
    # left????±????
    if len(A) > 2:
        T.l[A[0]] = A[2]
    else:
        T.l[A[0]] = -1

    # parent???right????±????
    for index, i in enumerate(A[2:]):
        if(A[-1] == i):
            T.p[i], T.r[i] = A[0], -1
        else:
            T.p[i], T.r[i] = A[0], A[index+3]
    
#T.set_depth_rec(T.p.index(-1), 0)
for i in range(N):
    T.set_depth(i)

for i in range(N):
    if T.p[i] is -1:
        node = "root"
    elif T.l[i] is -1:
        node = "leaf"
    else:
        node = "internal node"
        
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(i, T.p[i], T.D[i], node, T.print_children(i)))

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_A&lang=jp
class RootedTree:
    def __init__(self):
        self.id = None
        self.child = []
        self.parent = -1
        self.node_type = "root"
        self.depth = 0

    def show(self):
        print("node {}: parent = {}, depth = {}, {}, {}".format(self.id, self.parent, self.depth, self.node_type, self.child))

def cal_depth(tree, node, cur_depth):
    node.depth += cur_depth
    #node.show()
    for index in node.child:
        cal_depth(tree, tree[index], cur_depth + 1)
        
def make_tree(tree_data):#?????????,?¨???????n^2
    tree = [RootedTree() for i in range(len(tree_data))]
    
    for data in tree_data:
        focus = tree[data[0]]
        focus.id = data[0]
        
        if data[2:]:
            focus.child = data[2:]
            
            for child_index in data[2:]:
                tree[child_index].parent = data[0]
                
                if tree_data[[a[0] for a in tree_data].index(child_index)][2:]:
                    tree[child_index].node_type = "internal node"
                else:
                    tree[child_index].node_type = "leaf"
            
    root_index = [n.node_type for n in tree].index("root")
    cal_depth(tree, tree[root_index], 0)
    return tree

def set_tree_data(tree, target, parent, depth):
    tree[target]["depth"] += depth
    tree[target]["parent"] = parent

    for c in tree[target]["child"]:
        set_tree_data(tree, c, target, depth + 1)

def make_tree_revision(tree_data, n_tree):
    tree = [{"parent": None, "depth":0, "child" : None} for i in range(n_tree)]
    root = sum(range(n_tree))
    
    for node_data in tree_data:
        tree[node_data[0]]["child"] = node_data[2:]
        root -= sum(node_data[2:])

    set_tree_data(tree, root, -1, 0)
    return tree
def main():
    n_tree = int(input())
    tree_data = [[int(a) for a in input().split()] for i in range(n_tree)]
    
    for i, node in enumerate(make_tree_revision(tree_data, n_tree)):
        category = "root"
        if (not node["parent"] == -1) and node["child"]:
            category = "internal node"
        elif not node["parent"] == -1:
            category = "leaf"

        print("node {}: parent = {}, depth = {}, {}, {}".format(i, node["parent"], node["depth"], category, node["child"]))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_A&lang=jp
"""
class RootedTree:
    def __init__(self):
        self.id = None
        self.child = []
        self.parent = -1
        self.node_type = "root"
        self.depth = 0

    def show(self):
        print("node {}: parent = {}, depth = {}, {}, {}".format(self.id, self.parent, self.depth, self.node_type, self.child))

def cal_depth(tree, node, cur_depth):
    node.depth += cur_depth
    #node.show()
    for index in node.child:
        cal_depth(tree, tree[index], cur_depth + 1)
        
def make_tree(tree_data):#?????????,?¨???????n^2
    tree = [RootedTree() for i in range(len(tree_data))]
    
    for data in tree_data:
        focus = tree[data[0]]
        focus.id = data[0]
        
        if data[2:]:
            focus.child = data[2:]
            
            for child_index in data[2:]:
                tree[child_index].parent = data[0]
                
                if tree_data[[a[0] for a in tree_data].index(child_index)][2:]:
                    tree[child_index].node_type = "internal node"
                else:
                    tree[child_index].node_type = "leaf"
            
    root_index = [n.node_type for n in tree].index("root")
    cal_depth(tree, tree[root_index], 0)
    return tree
"""
def set_tree_data(tree, target, parent, depth):
    tree[target]["depth"] += depth
    tree[target]["parent"] = parent

    for c in tree[target]["child"]:
        set_tree_data(tree, c, target, depth + 1)

def make_tree_revision(tree_data, n_tree):#??????????¨???????n + n?
    tree = [{"parent": None, "depth":0, "child" : None} for i in range(n_tree)]
    root = sum(range(n_tree))
    
    for node_data in tree_data:
        tree[node_data[0]]["child"] = node_data[2:]
        root -= sum(node_data[2:])

    set_tree_data(tree, root, -1, 0)
    return tree

def main():
    n_tree = int(input())
    tree_data = [[int(a) for a in input().split()] for i in range(n_tree)]
    
    for i, node in enumerate(make_tree_revision(tree_data, n_tree)):
        category = "root"
        if (not node["parent"] == -1) and node["child"]:
            category = "internal node"
        elif not node["parent"] == -1:
            category = "leaf"

        print("node {}: parent = {}, depth = {}, {}, {}".format(i, node["parent"], node["depth"], category, node["child"]))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


import sys


class Node(object):
    __slots__ = ('parent', 'depth', 'type', 'children')

    def __init__(self):
        self.parent = -1
        self.type = ''
        self.depth = 0
        self.children = []


def dfs(node_idx, node_list, d=0):
    node_list[node_idx].depth = d
    for child in node_list[node_idx].children:
        dfs(child, node_list, d=d + 1)
    return None


def print_result(_node):
    print('parent = ' + str(_node.parent) + ',', end=' ')
    print('depth = ' + str(_node.depth) + ',', end=' ')
    print(_node.type + ',', end=' ')
    print(_node.children)
    return None


def generate_tree(_array, node_list):
    for each in _array:
        idx, k, *children = [x for x in each]
        node_list[idx].children = children
        if k:
            node_list[idx].type = 'internal node'
        else:
            node_list[idx].type = 'leaf'
        for child in children:
            node_list[child].parent = idx
    root_idx = [i for i, x in enumerate(node_list) if x.parent == -1][0]
    node_list[root_idx].type = 'root'
    dfs(node_idx=root_idx, node_list=node_list)
    return node_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(lambda x: list(map(int, x.split())), _input[1:]))
    assert len(array) == array_length

    init_node_list = [Node() for _ in range(array_length)]
    ans = generate_tree(_array=array, node_list=init_node_list)
    for key, node in enumerate(ans):
        print('node ' + str(key) + ':', end=' ')
        print_result(_node=node)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


import sys


class Node(object):
    __slots__ = ('parent', 'depth', 'type', 'children')

    def __init__(self):
        self.parent = -1
        self.type = ''
        self.depth = 0
        self.children = []


def dfs(node_idx, node_list, d=0):
    node_list[node_idx].depth = d
    for child in node_list[node_idx].children:
        dfs(child, node_list, d=d + 1)
    return None


def print_result(_node):
    print('parent = ' + str(_node.parent) + ',', end=' ')
    print('depth = ' + str(_node.depth) + ',', end=' ')
    print(_node.type + ',', end=' ')
    print(_node.children)
    return None


def generate_tree(_array, node_list):
    for each in _array:
        idx, k, *children = [x for x in each]
        node_list[idx].children = children
        if k:
            node_list[idx].type = 'internal node'
        else:
            node_list[idx].type = 'leaf'
        for child_idx in children:
            node_list[child_idx].parent = idx
    root_idx = [i for i, x in enumerate(node_list) if x.parent == -1][0]
    node_list[root_idx].type = 'root'
    dfs(node_idx=root_idx, node_list=node_list)
    return node_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(lambda x: list(map(int, x.split())), _input[1:]))
    # assert len(array) == array_length

    init_node_list = [Node() for _ in range(array_length)]
    ans = generate_tree(_array=array, node_list=init_node_list)
    for key, node in enumerate(ans):
        print('node ' + str(key) + ':', end=' ')
        print_result(_node=node)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


import sys


class Node(object):
    __slots__ = ('parent', 'depth', 'type', 'children')

    def __init__(self):
        self.parent = -1
        self.type = ''
        self.depth = 0
        self.children = []


def dfs(node_idx, node_list, depth=0):
    node_list[node_idx].depth = depth
    for child in node_list[node_idx].children:
        dfs(child, node_list, depth=depth + 1)
    return None


def print_result(_node):
    print('parent = ' + str(_node.parent) + ',', end=' ')
    print('depth = ' + str(_node.depth) + ',', end=' ')
    print(_node.type + ',', end=' ')
    print(_node.children)
    return None


def generate_tree(_array, node_list):
    for each in _array:
        idx, k, *children = [int(x) for x in each]
        node_list[idx].children = children
        if k:
            node_list[idx].type = 'internal node'
        else:
            node_list[idx].type = 'leaf'
        for child_idx in children:
            node_list[child_idx].parent = idx
    root_idx = [i for i, x in enumerate(node_list) if x.parent == -1][0]
    node_list[root_idx].type = 'root'
    dfs(node_idx=root_idx, node_list=node_list)
    return node_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(lambda x: x.split(), _input[1:]))
    # assert len(array) == array_length

    init_node_list = [Node() for _ in range(array_length)]
    ans = generate_tree(_array=array, node_list=init_node_list)
    for key, node in enumerate(ans):
        print('node ' + str(key) + ':', end=' ')
        print_result(_node=node)

Submission status: Accepted

Solution code:
class Node(object):
    def __init__(self, parent, left, right):
        self.parent = parent  # ????????????
        self.left = left      # ??????????????????????????????????????????
        self.right = right    # ??????????????????????????????????????´?????????

    def get_depth(self):
        if self.parent == -1:
            return 0
        else:
            depth = 1
            t = Nodes[self.parent]
            while t.parent != -1:
                t = Nodes[t.parent]
                depth += 1
            return depth

    def get_type(self):
        if self.parent == -1:
            return 'root'
        elif self.left == None:
            return 'leaf'
        else:
            return 'internal node'


def decode_node_data(n):
    global Nodes
    num_of_elem = len(n)
    if num_of_elem < 2:
        raise ValueError
    elif num_of_elem == 2:  # leaf
        pass
    else:
        id, num_of_children = int(n[0]), int(n[1])
        children = n[2:]
        Nodes[id].left = int(children[0])
        prev_child = None
        for c in children:
            Nodes[int(c)].parent = id
            if prev_child != None:
                Nodes[prev_child].right = int(c)
            prev_child = int(c)


MAX_NODES = 100001
Nodes = [Node(-1, None, None) for _ in range(MAX_NODES)]
if __name__ == '__main__':
    # ??????????????\???
    num_of_nodes = int(input())
    node_data = []
    for _ in range(num_of_nodes):
        node_data.append(input().split(' '))

    # ??¨????§£???
    for n in node_data:
        decode_node_data(n)


    # ???????????¨???
    for node_id in range(num_of_nodes):
        type = Nodes[node_id].get_type()
        children = []
        if type != 'leaf':
            if Nodes[node_id].left != None:
                c = Nodes[node_id].left
                children.append(c)
                while Nodes[c].right != None:
                    c = Nodes[c].right
                    children.append(c)
        print('node {0}: parent = {1}, depth = {2}, {3}, [{4}]'.format(node_id, Nodes[node_id].parent, Nodes[node_id].get_depth(), type,
                                                                       ', '.join(map(str, children))))