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:
N = int(input())
A = [input() for i in range(N)]

def get_depth(node_dict):
    depth = 0
    parent = node_dict["parent"]
    while parent > -1:
        depth += 1
        parent = rooted_tree[parent]["parent"]
    return depth

def get_node_type(node_dict):
    if node_dict["parent"] == -1:
        return "root"
    if node_dict["left"] == -1:
        return "leaf"
    return "internal node"

def get_children(node_dict):
    left = node_dict["left"]
    if left == -1:
        return "[]"
    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 = [{"parent": -1, "left": -1, "right": -1} for i in range(N)]
for row in A:
    node, degree_and_children = row.split(" ", 1)
    node = int(node)
    degree = int(degree_and_children[0])
    if degree > 0:
        children_list = list(map(int, degree_and_children[1:].split()))
        rooted_tree[node]["left"] = children_list[0]
        for i in range(len(children_list)):
            child_node = children_list[i]
            right = -1
            if i < len(children_list)-1:
                right = children_list[i+1]
            rooted_tree[child_node]["right"] = right
            rooted_tree[child_node]["parent"] = node

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

Submission status: Wrong Answer

Solution code:
N = int(input())

def get_depth(node_dict):
    depth = 0
    parent = node_dict["parent"]
    while parent > -1:
        depth += 1
        parent = rooted_tree[parent]["parent"]
    return depth

def get_node_type(node_dict):
    if node_dict["parent"] == -1:
        return "root"
    if node_dict["left"] == -1:
        return "leaf"
    return "internal node"

def get_children(node_dict):
    left = node_dict["left"]
    if left == -1:
        return "[]"
    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 = [{"parent": -1, "left": -1, "right": -1} for i in range(N)]
for idx in range(N):
    row = input()
    node, degree_and_children = row.split(" ", 1)
    node = int(node)
    degree = int(degree_and_children[0])
    if degree > 0:
        children_list = list(map(int, degree_and_children[1:].split()))
        rooted_tree[node]["left"] = children_list[0]
        for i in range(len(children_list)):
            child_node = children_list[i]
            right = -1
            if i < len(children_list)-1:
                right = children_list[i+1]
            rooted_tree[child_node]["right"] = right
            rooted_tree[child_node]["parent"] = node

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

Submission status: Wrong Answer

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

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" in node:
        depth += 1
        parent = node["parent"]
        node = rooted_tree[parent]
    return depth

def get_node_type(node):
    if "parent" not 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: Wrong Answer

Solution code:
# coding=utf-8
class Node():
    # About Type
    # parent = -1 ==> Root ==> 0
    # child = [] ==> Leaf ==> 1
    # others ==> Internal ==> 2
    def __init__(self, id, parent, child):
        self.id = id
        self.parent = parent
        self.child = child

    def update(self):
        self.depth = 0
        back = -1
        if self.parent == -1:
            self.Type = "root"
            back = self.id
        elif self.child == []:
            self.Type = "leaf"
        else :
            self.Type = "internal node"
        return back

    def printInfo(self):
        print("node :" + str( self.id ), end = " :" )
        print("parent = " + str( self.parent ), end = ", " )
        print("depth = " + str( self.depth ), end = ", " )
        print( self.Type, end = ", " )
        print("[", end="")
        length = len( self.child )
        for i in self.child[0: length - 1]:
            print(str(i), end=", ")
        if length > 0:
            print( str(self.child[length-1]) , end="")
        print("]")


    def calcDepth(self, Tree):
        if self.parent == -1:
            self.depth = 0
        else :
            self.depth = Tree[self.parent].depth + 1
        for i in self.child:
            Tree[i].calcDepth(Tree)


def main():
    # データ入力
    n = int( input() )
    InputData = []
    Tree = {} # Nodeクラスのディクショナリ

    tmp = []
    for i in range(n):
        tmp = [int(x) for x in input().split()] # [Node, num, 子1, 子2, ...]
        InputData.append(tmp)
        # Treeの初期化
        Tree[tmp[0]] = Node(tmp[0], -1, tmp[2: 2+tmp[1]])

    for val in Tree.values():
        for i in val.child:
            Tree[i].parent = val.id

    for key in Tree.keys():
        tmp = Tree[key].update()
        if tmp != -1:
            root = tmp

    Tree[root].calcDepth(Tree)

    keys = list(Tree.keys())
    keys.sort()

    for key in keys:
        Tree[key].printInfo()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding=utf-8
class Node():
    # About Type
    # parent = -1 ==> Root ==> 0
    # child = [] ==> Leaf ==> 1
    # others ==> Internal ==> 2
    def __init__(self, id, parent, child):
        self.id = id
        self.parent = parent
        self.child = child

    def update(self):
        self.depth = 0
        back = -1
        if self.parent == -1:
            self.Type = "root"
            back = self.id
        elif self.child == []:
            self.Type = "leaf"
        else :
            self.Type = "internal node"
        return back

    def printInfo(self):
        print("node :" + str( self.id ), end = " " )
        print("parent = " + str( self.parent ), end = ", " )
        print("depth = " + str( self.depth ), end = ", " )
        print( self.Type, end = ", " )
        print("[", end="")
        length = len( self.child )
        for i in self.child[0: length - 1]:
            print(str(i), end=", ")
        if length > 0:
            print( str(self.child[length-1]) , end="")
        print("]")


    def calcDepth(self, Tree):
        if self.parent == -1:
            self.depth = 0
        else :
            self.depth = Tree[self.parent].depth + 1
        for i in self.child:
            Tree[i].calcDepth(Tree)


def main():
    # データ入力
    n = int( input() )
    InputData = []
    Tree = {} # Nodeクラスのディクショナリ

    tmp = []
    for i in range(n):
        tmp = [int(x) for x in input().split()] # [Node, num, 子1, 子2, ...]
        InputData.append(tmp)
        # Treeの初期化
        Tree[tmp[0]] = Node(tmp[0], -1, tmp[2: 2+tmp[1]])

    for val in Tree.values():
        for i in val.child:
            Tree[i].parent = val.id

    for key in Tree.keys():
        tmp = Tree[key].update()
        if tmp != -1:
            root = tmp

    Tree[root].calcDepth(Tree)

    keys = list(Tree.keys())
    keys.sort()

    for key in keys:
        Tree[key].printInfo()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding=utf-8
def setDepth(index, Tree):
    if Tree[index][1] == -1:
        Tree[index][2] = 0
    else :
        Tree[index][2] = 1 + Tree[ Tree[index][1] ][2]
    for i in Tree[index][4]:
        setDepth(i, Tree)

def main():
    # データ入力
    n = int( input() )
    Tree = [] # 0=>n-1まで, [id, parent, depth, type, [child]]
    for i in range(n):
        Tree.append([0, -1, 0, "root", []])

    tmp = []
    for i in range(n):
        tmp = [int(x) for x in input().split()] # [Node, num, 子1, 子2, ...]
        Tree[tmp[0]][0] = tmp[0]
        Tree[tmp[0]][4] = tmp[2: 2+tmp[1] ]

    for i in range(n):
        for j in Tree[i][4]:
            Tree[j][1] = j # parentを代入

    # typeを求める
    for i in range(n):
        if Tree[i][1] == -1:
            root = i
            Tree[i][3] = "root"
        elif Tree[i][4] == []:
            Tree[i][3] = "leaf"
        else :
            Tree[i][3] = "internal node"

    setDepth(root, Tree)

    for i in range(n):
        print("node :" + str( Tree[i][0] ), end = " " )
        print("parent = " + str( Tree[i][1] ), end = ", " )
        print("depth = " + str( Tree[i][2] ), end = ", " )
        print( Tree[i][3], end = ", " )
        print("[", end="")
        length = len( Tree[i][4] )
        for j in Tree[i][4][0: length - 1]:
            print(str(j), end=", ")
        if length > 0:
            print( str(Tree[i][4][length-1]) , end="")
        print("]")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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
    if p == None:
        nodes[u].parent = -1
        nodes[u].depth = 0
        nodes[u].name = "root"
    elif p != -1:
        d = nodes[p].depth
        if d != None:
            nodes[u].depth = d + 1
        set_depth(nodes, p)

def read_and_setup_rooted_tree(nodes, n):
    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 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]

    for i in range(n):
        set_depth(nodes, i)

def print_nodes(nodes, n):
    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))

n = int(input())
nodes = [Node() for _ in range(n)]
read_and_setup_rooted_tree(nodes, n)
print_nodes(nodes, n)

Submission status: Wrong Answer

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

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

def print_nodes(nodes, n):
    for i in range(n):
        if nodes[i].parent == None:
            nodes[i].parent = -1
            nodes[i].name = "root"
        print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(
               i, nodes[i].parent, get_depth(nodes, i), nodes[i].name, nodes[i].children))

def read_rooted_tree(nodes, n):
    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 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]

n = int(input())
nodes = [Node() for _ in range(n)]
read_rooted_tree(nodes, n)
print_nodes(nodes, n)

Submission status: Wrong Answer

Solution code:
class tree:
    def __init__(self,node,dim,child):
        self.node = node
        self.dim = dim
        self.child = child
n = int(input())

dali = []

def getDepth(u): #節点uの深さを求める
    d = 0
    ans = u
    while True:
        x = dali[u].parent
        
        if x!= -1:
            
            u = dali[u].parent
            d += 1
            
        else:
            dali[ans].depth = d
            break
def getParent(u):
    flag = 0
    if u == 0 :
        dali[u].parent = -1
        return dali[u].parent
    j = u-1

    while j >= 0:
        if (dali[u].node) in (dali[j].child):
            flag = 1
            dali[u].parent = dali[j].node
            break
        j -= 1
    if flag == 0:
       dali[u].parent = -1
    
    return dali[u].parent
def getType(u):
    if dali[u].parent == -1:
        dali[u].type = "root"
        
    elif dali[u].child ==None :
        dali[u].type = "leaf"
    else:
        dali[u].type = "internal node"

def inputData(i): #入力値の取得  dali[i] にnode==iの節点番号、次元、子の配列を格納
    data = [int(s) for s in input().split()]
    
    childata = []
    if len(data) >2:
        for j in range(2,len(data)):
            childata.append(data[j])
    
    dali.append(tree(data[0],data[1],childata))
    
for k in range(0,n):
    inputData(k)#入力値の取得
    getParent(k)
    getDepth(k)
    getType(k)
    lis = str(dali[k].child)
    print("node %d: parent = %d, depth = %d, %s, %s"%(dali[k].node,dali[k].parent,dali[k].depth,dali[k].type,lis))

Submission status: Wrong Answer

Solution code:
class tree:
    def __init__(self,node,dim,child):
        self.node = node
        self.dim = dim
        self.child = child
n = int(input())

dali = []

def getDepth(u): #節点uの深さを求める
    d = 0
    ans = u
    while True:
        x = dali[u].parent
        if x!= -1:
            u = dali[u].parent
            d += 1
        else:
            dali[ans].depth = d
            break
def getParent(u):
    flag = 0
    j = 0

    while j < n:
        if (dali[u].node) in (dali[j].child):
            flag = 1
            dali[u].parent = dali[j].node
            break
        j +=1
    if flag == 0:
       dali[u].parent = -1
    
    return dali[u].parent
def getType(u):
    if dali[u].parent == -1:
        dali[u].type = "root"
        
    elif dali[u].child ==None :
        dali[u].type = "leaf"
    else:
        dali[u].type = "internal node"

def inputData(i): #入力値の取得  dali[i] にnode==iの節点番号、次元、子の配列を格納
    data = [int(s) for s in input().split()]
    
    childata = []
    if len(data) >2:
        for j in range(2,len(data)):
            childata.append(data[j])
    
    dali.append(tree(data[0],data[1],childata))
    
for k in range(0,n):
    inputData(k)#入力値の取得
    
for k in range(n):
    getParent(k)
    
for k in range(n):
    getDepth(k)
    getType(k)
    lis = str(dali[k].child)
    dali[k].lis = lis

for k in range(n):
    print("node %d: parent = %d, depth = %d, %s, %s"%(dali[k].node,dali[k].parent,dali[k].depth,dali[k].type,lis))

Submission status: Wrong Answer

Solution code:
class tree:
    def __init__(self,node,dim,child):
        self.node = node
        self.dim = dim
        self.child = child
n = int(input())

dali = []

def getDepth(u): #節点uの深さを求める
    d = 0
    ans = u
    while True:
        x = dali[u].parent
        if x!= -1:
            u = dali[u].parent
            d += 1
        else:
            dali[ans].depth = d
            break
def getParent(u):
    flag = 0
    j = 0

    while j < n:
        if (dali[u].node) in (dali[j].child):
            flag = 1
            dali[u].parent = dali[j].node
            break
        j +=1
    if flag == 0:
       dali[u].parent = -1
    
    return dali[u].parent
def getType(u):
    if dali[u].parent == -1:
        dali[u].type = "root"
        
    elif dali[u].child ==[] :
        dali[u].type = "leaf"
    else:
        dali[u].type = "internal node"

def inputData(i): #入力値の取得  dali[i] にnode==iの節点番号、次元、子の配列を格納
    data = [int(s) for s in input().split()]
    
    childata = []
    if len(data) >2:
        for j in range(2,len(data)):
            childata.append(data[j])
    
    dali.append(tree(data[0],data[1],childata))
    
for k in range(0,n):
    inputData(k)#入力値の取得
    
for k in range(n):
    getParent(k)
    
for k in range(n):
    getDepth(k)
    getType(k)
    lis = str(dali[k].child)
    dali[k].lis = lis

for k in range(n):
    print("node %d: parent = %d, depth = %d, %s, %s"%(dali[k].node,dali[k].parent,dali[k].depth,dali[k].type,lis))

Submission status: Wrong Answer

Solution code:
class tree:
    def __init__(self,node,dim,child):
        self.node = node
        self.dim = dim
        self.child = child
n = int(input())

dali = []

def getDepth(u): #節点uの深さを求める
    d = 0
    ans = u
    while True:
        x = dali[u].parent
        if x!= -1:
            u = dali[u].parent
            d += 1
        else:
            dali[ans].depth = d
            break
def getParent(u):
    flag = 0
    j = 0

    while j < n:
        if (dali[u].node) in (dali[j].child):
            flag = 1
            dali[u].parent = dali[j].node
            break
        j +=1
    if flag == 0:
       dali[u].parent = -1
    
    return dali[u].parent
def getType(u):
    if dali[u].parent == -1:
        dali[u].type = "root"
        
    elif dali[u].child ==[] :
        dali[u].type = "leaf"
    else:
        dali[u].type = "internal node"

def inputData(i): #入力値の取得  dali[i] にnode==iの節点番号、次元、子の配列を格納
    data = [int(s) for s in input().split()]
    
    childata = []
    if len(data) >2:
        for j in range(2,len(data)):
            childata.append(data[j])
    
    dali.append(tree(data[0],data[1],childata))
    
for k in range(0,n):
    inputData(k)#入力値の取得
    
for k in range(n):
    getParent(k)
    
for k in range(n):
    getDepth(k)
    getType(k)
    lis = str(dali[k].child)
    dali[k].lis = lis
    print(dali[k].child)

for k in range(n):
    print("node %d: parent = %d, depth = %d, %s, %s"%(dali[k].node,dali[k].parent,dali[k].depth,dali[k].type,dali[k].lis))

Submission status: Wrong Answer

Solution code:
def f(n,e,a):
    d[n][1:1]=[a,e,"root" if a<0 else "leaf" if len(d[n])<3 else "internal node"]
    for i in d[n][4]:f(i,e+1,n)
n=input()
c=[0]*n
d=sorted([map(int,raw_input().split()) for _ in range(n)])
for i in d:
    i[1:]=[i[2:]]
    for j in i[1]:c[j]=1
f(c.index(0),0,-1)
for i in d:print "node {0}: parent = {1}, depth = {2}, {3}, {4}".format(*i)

Submission status: Wrong Answer

Solution code:
class Tree():
    def __init__(self):
        self.nodes = {}
    def add_node(self, parent_id, child_id):
        if len(self.nodes) == 0:
            self.nodes[parent_id] = Node(parent_id)
        child = Node(child_id, self.nodes[parent_id])
        self.nodes[child.id] = child
    
class Node():
    def __init__(self, id, parent = None):
        self.id = id
        self.parent = parent
        self.children = []
        if self.parent:
            self.parent.children.append(self)
            self.depth = self.parent.depth + 1
            self.nodetype = 'leaf'
            if self.parent.nodetype == 'leaf':
                self.parent.nodetype = 'internal node'
        else:
            self.depth = 0
            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 _ in range(n):
    line = input().split()
    for ci in map(int, line[2:]):
        tree.add_node(int(line[0]), ci)

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

Submission status: Wrong Answer

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_A
# Rooted Trees
# Result:
import sys

class Node(object):
    def __init__(self, id_):
        super(Node, self).__init__()
        self.id_ = id_
        self.parent = -1
        self.depth = 0
        self.children = []

    def add_child(self, child_):
        self.children.append(child_)

    def set_parent(self, parent, parent_depth):
        assert self.parent == -1
        self.parent = parent
        self.depth = parent_depth + 1

    def __str__(self):
        str_ = 'node %d: ' % (self.id_)
        str_ += 'parent = %d, ' % (self.parent)
        str_ += 'depth = %d, ' % (self.depth)
        if self.parent == -1:
            str_ += 'root, '
        elif len(self.children) > 0:
            str_ += 'internal node, '
        else:
            str_ += 'leaf, '
        str_ += '[%s]' % (', '.join([str(x) for x in self.children]))
        return str_


nnodes = int(sys.stdin.readline())
nodes = []
for i in range(0, nnodes):
    nodes.append(Node(i))

for _ in range(0, nnodes):
    vals = sys.stdin.readline().rstrip().split(' ')
    node_id = int(vals[0])
    node = nodes[node_id]
    nchild = int(vals[1])
    for i in range(0, nchild):
        child_id = int(vals[2+i])
        node.add_child(child_id)
        child = nodes[child_id]
        child.set_parent(node_id, node.depth)

for n in nodes:
    print n

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self, id, children):
        self.id = id
        self.children = children
        self.childNode = []
        self.parent = -1
        self.depth = -1
        self.nodeType = ''

    def setChildNode(self, node):
        self.childNode.append(node)

    def __repr__(self):
        return self.__str__()

    def __str__(self):
        return 'node ' + str(self.id) + ': parent = ' + str(self.parent) + ', depth = ' + str(self.depth) + ', '\
                + self.nodeType + ', ' + self.children.__str__()

    def setNodeType(self):
        if self.parent == -1:
            self.nodeType = 'root'
        elif len(self.children) == 0:
            self.nodeType = 'leaf'
        else:
            self.nodeType = 'internal node'

def setDepth(node, depth):
    node.depth = depth
    for child in node.childNode:
        setDepth(child, depth + 1)

n = int(raw_input())
T = []
P = [-1] * n
for i in xrange(n):
    L = map(int, raw_input().split())
    T.append(Node(i, L[2:]))
    for child in T[i].children:
        P[child] = i
root = P.index(-1)
for i, x in enumerate(P):
    T[i].parent = P[i]
    for cid in T[i].children:
        T[i].setChildNode(T[cid])

setDepth(T[root], 0)
for x in T:
    x.setNodeType()
    print x

Submission status: Wrong Answer

Solution code:
import sys


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

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    node_list = [None] * int(lines[0])  # Create empty list
    child_parent_map = [None] * int(lines[0])

    # Create the list of Node
    for line in lines[1:]:
        node_id, _, *children = [int(x) for x in line.strip().split(" ")]
        node_list[node_id] = Node(children=children)
        for child in children:
            child_parent_map[child] = node_id

    # Set the parent_id of each node
    for node_id, node in enumerate(node_list):
        if child_parent_map[node_id] is not None:
            node.parent_id = child_parent_map[node_id]

    # Set the depth of each node
    for node_id, node in enumerate(node_list):
        current_id = node_id
        current_depth = 0
        while True:
            if current_id == 0:
                node.depth = current_depth
                break
            else:
                current_id = node_list[current_id].parent_id
                current_depth += 1

    # Output
    for node_id, node in enumerate(node_list):
        print("node %d: parent = %d, depth = %d, leaf, %s" % (node_id, node.parent_id, node.depth, node.children))