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: Wrong Answer

Solution code:
class Node:
    def __init__(self):
        self.p = None
        self.depth = None
        self.l = None
        self.r = None

    def show(self, i):
        global T
        ans = 'node {}: parent = {}, depth = {}, {}, {}'.format(i, self.p, self.depth, self.t(), self.degree(T))
        print(ans)

    def degree(self, T):
        if self.l != None:
            deg = [self.l]
            ch = T[self.l]
            while ch.r:
                deg.append(ch.r)
                ch = T[ch.r]
            return deg
        else:
            return []

    def t(self):
        if self.p == -1:
            return 'root'
        elif self.l == None:
            return 'leaf'
        else:
            return 'internal node'

def set_depth(root, d):
    r = T[root]
    r.depth = d
    if r.r:
        set_depth(r.r, d)
    if r.l:
        set_depth(r.l, d+1)

n = int(input())

T = [Node() for x in range(n)]
for i in range(n):
    A = list(map(int, input().split()))
    l = 0
    for x in range(A[1]):
        if x == 0:
            T[A[0]].l = A[2:][x]
        else:
            T[l].r = A[2:][x]
        l = A[2:][x]
        T[A[2:][x]].p = A[0]

root = None
for i in range(n):
    if T[i].p == None:
        root = i
        T[root].p = -1

set_depth(root, 0)

count = 0
for node in T:
    node.show(count)
    count += 1

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self):
        self.p = None
        self.depth = None
        self.l = None
        self.r = None

    def show(self, i):
        global T
        ans = 'node {}: parent = {}, depth = {}, {}, {}'.format(i, self.p, self.depth, self.t(), self.degree(T))
        print(ans)

    def degree(self, T):
        if self.l != None:
            deg = [self.l]
            ch = T[self.l]
            while ch.r:
                deg.append(ch.r)
                ch = T[ch.r]
            return deg
        else:
            return []

    def t(self):
        if self.p == -1:
            return 'root'
        elif self.l == None:
            return 'leaf'
        else:
            return 'internal node'

def set_depth(root, d):
    r = T[root]
    r.depth = d
    if r.r != None:
        set_depth(r.r, d)
    if r.l != None:
        set_depth(r.l, d+1)

n = int(input())

T = [Node() for x in range(n)]
for i in range(n):
    A = list(map(int, input().split()))
    l = 0
    for x in range(A[1]):
        if x == 0:
            T[A[0]].l = A[2:][x]
        else:
            T[l].r = A[2:][x]
        l = A[2:][x]
        T[A[2:][x]].p = A[0]

root = None
for i in range(n):
    if T[i].p == None:
        root = i
        T[root].p = -1

set_depth(root, 0)

count = 0
for node in T:
    node.show(count)
    count += 1

Submission status: Wrong Answer

Solution code:
class Node(object):
    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 = [-1 for i in range(N)]

    def set_depth(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 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()]
    
    if len(A) > 2:
        T.l[j] = A[2]
    else:
        T.l[j] = -1

    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(0, 0)

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: Wrong Answer

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

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 = [-1 for i in range(N)]

    def set_depth(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 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[j] = A[2]
    else:
        T.l[j] = -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(T.p.index(-1), 0)

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: Wrong Answer

Solution code:
#coding:UTF-8
def depth(leaf,A,d):
    for i in range(len(A)):
        if len(A[i][2])>1 and leaf in A[i][2]:
            return depth(A[i][0],A,d+1)
    return d

def RT(A,n):
    for i in range(n):
        p=0
        d=0
        t=""
        c="["
        if A[i][1]==0:
            t="leaf"
            d=depth(A[i][0],A,d)
            for j in range(len(A)):
                if A[i][0] in A[j][2]:
                    p=A[j][0]
                    break
        else:
            d=depth(A[i][0],A,d)
            if d==0:
                p=-1
                t="root"
            else:
                for j in range(len(A)):
                    if A[i][0] in A[j][2]:
                        p=A[j][0]
                        t="internal node"
                        break
        if len(A[i][2])==0:
            c="[]"
        else:
            for j in range(len(A[i][2])):
                if j==len(A[i][2])-1:
                    c+=str(A[i][2][j])+"]"
                else:
                    c+=str(A[i][2][j])+", "
        print("node "+str(A[i][0])+": parent = "+str(p)+", depth = "+str(d)+", "+t+", "+c)

if __name__=="__main__":
    n=int(input())
    A=[]
    for i in range(n):
        a=[]
        A.append(list(map(int,input().split(" "))))
        if len(A[i])==2:
            A[i].append(a)
        else:
            for j in range(len(A[i])-2):
                a.append(A[i][j+2])
            del A[i][2:]
            A[i].append(a)  
    for i in range(n):
        minj=i
        for j in range(i,n):
            if A[j][0]<A[minj][0]:
                minj=j
        A[i],A[minj]=A[minj],A[i]
    print(A)  
    RT(A,n)

Submission status: Wrong Answer

Solution code:
#coding:UTF-8
def depth(leaf,A,d):
    for i in range(len(A)):
        if len(A[i][2])>1 and leaf in A[i][2]:
            return depth(A[i][0],A,d+1)
    return d

def RT(A,n):
    for i in range(n):
        p=0
        d=0
        t=""
        c="["
        if A[i][1]==0 and n>1:
            t="leaf"
            d=depth(A[i][0],A,d)
            for j in range(len(A)):
                if A[i][0] in A[j][2]:
                    p=A[j][0]
                    break
        else:
            d=depth(A[i][0],A,d)
            if d==0:
                p=-1
                t="root"
            else:
                for j in range(len(A)):
                    if A[i][0] in A[j][2]:
                        p=A[j][0]
                        t="internal node"
                        break
        if len(A[i][2])==0:
            c="[]"
        else:
            for j in range(len(A[i][2])):
                if j==len(A[i][2])-1:
                    c+=str(A[i][2][j])+"]"
                else:
                    c+=str(A[i][2][j])+", "
        print("node "+str(A[i][0])+": parent = "+str(p)+", depth = "+str(d)+", "+t+", "+c)

if __name__=="__main__":
    n=int(input())
    A=[]
    for i in range(n):
        a=[]
        A.append(list(map(int,input().split(" "))))
        if len(A[i])==2:
            A[i].append(a)
        else:
            for j in range(len(A[i])-2):
                a.append(A[i][j+2])
            del A[i][2:]
            A[i].append(a)  
    for i in range(n):
        minj=i
        for j in range(i,n):
            if A[j][0]<A[minj][0]:
                minj=j
        A[i],A[minj]=A[minj],A[i]
    print(A)  
    RT(A,n)

Submission status: Wrong Answer

Solution code:
#coding:UTF-8
def depth(leaf,A,d):
    for i in range(len(A)):
        if len(A[i][2])>1 and leaf in A[i][2]:
            return depth(A[i][0],A,d+1)
    return d

def RT(A,n):
    for i in range(n):
        p=0
        d=0
        t=""
        c="["
        if A[i][1]==0 and n>1:
            t="leaf"
            d=depth(A[i][0],A,d)
            for j in range(len(A)):
                if A[i][0] in A[j][2]:
                    p=A[j][0]
                    break
        else:
            d=depth(A[i][0],A,d)
            if d==0:
                p=-1
                t="root"
            else:
                for j in range(len(A)):
                    if A[i][0] in A[j][2]:
                        p=A[j][0]
                        t="internal node"
                        break
        if len(A[i][2])==0:
            c="[]"
        else:
            for j in range(len(A[i][2])):
                if j==len(A[i][2])-1:
                    c+=str(A[i][2][j])+"]"
                else:
                    c+=str(A[i][2][j])+", "
        print("node "+str(A[i][0])+": parent = "+str(p)+", depth = "+str(d)+", "+t+", "+c)

if __name__=="__main__":
    n=int(input())
    A=[]
    for i in range(n):
        a=[]
        A.append(list(map(int,input().split(" "))))
        if len(A[i])==2:
            A[i].append(a)
        else:
            for j in range(len(A[i])-2):
                a.append(A[i][j+2])
            del A[i][2:]
            A[i].append(a)  
    for i in range(n):
        minj=i
        for j in range(i,n):
            if A[j][0]<A[minj][0]:
                minj=j
        A[i],A[minj]=A[minj],A[i]
    RT(A,n)

Submission status: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_A&lang=jp
class RootedTree:
    def __init__(self, node, parent_node):
        self.id = node[0]
        self.parent = parent_node
        self.item = node[2:]
        self.children = []
        self.depth = 0
        self.type = None
        self.next_id_node = None
        
        if parent_node == None:
            self.type = "root"
        else:
            parent_node.type = "internal node"
            self.type = "leaf"
            self.depth = parent_node.depth + 1
            
    def filled(self):
        return len(self.children) == len(self.item)
    
    def show_self(self):
        if self.parent == None:
            parent_id = -1
        else:
            parent_id = self.parent.id
        print("node " + str(self.id) + ":" + " parent = " + str(parent_id) + ", depth = " + str(self.depth)+ ", " + self.type + ", " + str(self.item))

def make_tree(trees):
    root = None
    target_node = None
    for node in trees:
        if target_node == None:
            root = RootedTree(node, None)
            target_node = root
            root.show_self()
        else:
            child = RootedTree(node, target_node)
            child.show_self()
            target_node.next_id_node = child
            target_node.children.append(child)
            target_node = child
            while target_node.filled():
                target_node = target_node.parent
                if not target_node:
                    break
                
    return root
def main():
    n_trees = int(input())
    trees = [[int(a) for a in input().split()] for i in range(n_trees)]

    make_tree(trees)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_A&lang=jp
class RootedTree:
    def __init__(self, node, parent_node):
        self.id = node[0]
        self.parent = parent_node
        self.item = node[2:]
        self.children = []
        self.depth = 0
        self.type = None
        
        if parent_node == None:
            self.type = "root"
        else:
            parent_node.type = "internal node"
            self.type = "leaf"
            self.depth = parent_node.depth + 1
            
    def filled(self):
        return len(self.children) == len(self.item)

    def get_info(self):
        if self.parent == None:
            parent_id = -1
        else:
            parent_id = self.parent.id
        return ("node " + str(self.id) + ":" + " parent = " + str(parent_id) + ", depth = " + str(self.depth)+ ", " + self.type + ", " + str(self.item))

def get_tree_info(focus_node, info):
    info[focus_node.id] = focus_node.get_info()
    for child in focus_node.children:
        get_tree_info(child, info)
    return info

def make_tree(trees):
    root = None
    target_node = None
    for node in trees:
        if target_node == None:
            root = RootedTree(node, None)
            target_node = root
        else:
            child = RootedTree(node, target_node)
            target_node.children.append(child)
            target_node = child
            while target_node.filled():
                target_node = target_node.parent
                if not target_node:
                    break
                
    return root
def main():
    n_trees = int(input())
    trees = [[int(a) for a in input().split()] for i in range(n_trees)]

    t_info = [None for a in  range(n_trees)]
    print("\n".join(get_tree_info(make_tree(trees),t_info)))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 = None
        self.parent = None
        self.node_type = None
        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
    for index in node.child:
        cal_depth(tree, tree[index],cur_depth + 1)
        
def make_tree(tree_data):
    tree = [RootedTree() for i in range(len(tree_data))]
    root_index = 0
    for data in tree_data:
        focus = tree[data[0]]
        focus.id = data[0]
        if not data[2:]:
            focus.node_type = "leaf"
            focus.child = []
        else:
            focus.child = data[2:]
            if root_index in data[2:]:
                root_index = data[0]
            for child_index in data[2:]:
                tree[child_index].parent = data[0]
                tree[child_index].node_type = "internal node"

    cal_depth(tree, tree[root_index], 0)
    return tree
    
def main():
    n_trees = int(input())
    tree_data = [[int(a) for a in input().split()] for i in range(n_trees)]

    for n in make_tree(tree_data):
        n.show()
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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
    for index in node.child:
        cal_depth(tree, tree[index],cur_depth + 1)
        
def make_tree(tree_data):
    tree = [RootedTree() for i in range(len(tree_data))]
    root_index = 0
    for data in tree_data:
        focus = tree[data[0]]
        focus.id = data[0]
        if data[2:]:
            focus.child = data[2:]
            if root_index in data[2:]:
                root_index = data[0]
            for child_index in data[2:]:
                tree[child_index].parent = data[0]
                if tree_data[child_index][2:]:
                    tree[child_index].node_type = "internal node"
                else:
                    tree[child_index].node_type = "leaf"
    cal_depth(tree, tree[root_index], 0)
    return tree
    
def main():
    n_trees = int(input())
    tree_data = [[int(a) for a in input().split()] for i in range(n_trees)]

    for n in make_tree(tree_data):
        n.show()
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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
    for index in node.child:
        cal_depth(tree, tree[index],cur_depth + 1)
        
def make_tree(tree_data):
    tree = [RootedTree() for i in range(len(tree_data))]
    root_index = 0
    for data in tree_data:
        focus = tree[data[0]]
        focus.id = data[0]
        if data[2:]:
            focus.child = data[2:]

            if root_index in data[2:]:
                root_index = data[0]
                
            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"
       
    cal_depth(tree, tree[root_index], 0)
    return tree
    
def main():
    n_trees = int(input())
    tree_data = [[int(a) for a in input().split()] for i in range(n_trees)]
    
    for n in make_tree(tree_data):
        n.show()
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 node["parent"] and node["child"]:
            category = "internal node"
        else:
            category = "leaf"

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

Submission status: Wrong Answer

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 == None:
            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 = 20
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))))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [0] * N
    node_info = [[-1, 0, 'internal node', ['']] for _ in range(int(1E5 + 1))]
    for i in range(N):
        A[i] = [int(i) for i in input().strip().split()]
    for line in A:
        if line[1] != 0:
            node_info[line[0]][3] = line[2:]
            for c in line[2:]:
                node_info[c][0] = line[0]

    for line in A:
        pid = node_info[line[0]][0]
        if pid == -1:
            node_info[line[0]][2] = 'root'
        else:
            if node_info[line[0]][3] is None:
                node_info[line[0]][2] = 'leaf'

        depth = 0
        while pid != -1:
            depth += 1
            pid = node_info[pid][0]
        node_info[line[0]][1] = depth

    for line in A:
        print('node {}: parent = {}, depth = {}, {}, [{}]'.format(
            line[0], node_info[line[0]][0],
            node_info[line[0]][1], node_info[line[0]][2], ', '.join([str(i) for i in node_info[line[0]][3]]))
        )


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [0] * N
    node_info = [[-1, 0, 'internal node', ['']] for _ in range(int(1E5 + 1))]
    for i in range(N):
        A[i] = [int(i) for i in input().strip().split()]
    for line in A:
        if line[1] != 0:
            node_info[line[0]][3] = line[2:]
            for c in line[2:]:
                node_info[c][0] = line[0]

    for line in A:
        pid = node_info[line[0]][0]
        if pid == -1:
            node_info[line[0]][2] = 'root'
        else:
            if node_info[line[0]][3]:
                node_info[line[0]][2] = 'leaf'

        depth = 0
        while pid != -1:
            depth += 1
            pid = node_info[pid][0]
        node_info[line[0]][1] = depth

    for line in A:
        print('node {}: parent = {}, depth = {}, {}, [{}]'.format(
            line[0], node_info[line[0]][0],
            node_info[line[0]][1], node_info[line[0]][2], ', '.join([str(i) for i in node_info[line[0]][3]]))
        )


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [0] * N
    node_info = [[-1, 0, 'internal node', None] for _ in range(int(1E5 + 1))]
    for i in range(N):
        A[i] = [int(i) for i in input().strip().split()]
    for line in A:
        if line[1] != 0:
            node_info[line[0]][3] = line[2:]
            for c in line[2:]:
                node_info[c][0] = line[0]

    for line in A:
        pid = node_info[line[0]][0]
        if pid == -1:
            node_info[line[0]][2] = 'root'
        else:
            if node_info[line[0]][3] is None:
                node_info[line[0]][2] = 'leaf'
        if node_info[line[0]][3] is None:
            node_info[line[0]][3] = ['']

        depth = 0
        while pid != -1:
            depth += 1
            pid = node_info[pid][0]
        node_info[line[0]][1] = depth

    for line in A:
        print('node {}: parent = {}, depth = {}, {}, [{}]'.format(
            line[0], node_info[line[0]][0],
            node_info[line[0]][1], node_info[line[0]][2], ', '.join([str(i) for i in node_info[line[0]][3]]))
        )


if __name__ == '__main__':
    main()