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:
def tail_recursive(func):
	from functools import wraps
	@wraps(func)
	def _tail(*args, **kwd):
		_tail.__args = args
		_tail.__kwd = kwd

		if _tail.__firstcall:
			_tail.__firstcall = False

			result = func
			try:
				while result is func:
					result = func(*_tail.__args, **_tail.__kwd)
			finally:
				_tail.__firstcall = True

			return result
		else:
			return func
	_tail.__firstcall = True

	return _tail

class Tree:
    def __init__(self,parent,left,right):
        self.parent = parent
        self.left = left
        self.right = right

@tail_recursive
def setdepth(u, p):
    depths[u] = p
    if trees[u].right != -1:
        # ???????????????????????±???????¨????
        setdepth(trees[u].right, p)
    if trees[u].left != -1:
        # ??????????????????????????±???+1????¨????
        setdepth(trees[u].left, p+1)

N = int(input())
# ?????????
trees = [Tree(-1,-1,-1) for i in range(N)]
for i in range(N):
    l = list(map(int, input().split()))
    no = l[0]
    jisu = l[1]
    # 2???????????????????????§???????´??????????
    childs = l[2:]
    for j in range(jisu):
        child = childs[j]
        if j == 0:
            trees[no].left = child

        if j != len(childs)-1:
            trees[child].right = childs[j+1]

        trees[child].parent = no

r = 0
for i in range(N):
    if trees[i].parent == -1:
        r = i

depths = [-1] * N
setdepth(r, 0)

for i in range(N):
    type = ""
    if trees[i].parent == -1: type = "root"
    elif trees[i].left == -1: type = "leaf"
    else: type = "internal node"
    childs = "["
    child = trees[i].left
    while child != -1:
        childs += str(child)
        child = trees[child].right
        if child != -1: childs += ", "
    childs += "]"

    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(i, trees[i].parent, depths[i], type, childs))

Submission status: Wrong Answer

Solution code:
N = int(input())

tree = [{'p': -1, 'c': list(), 'd': 0} for _ in range(N)]

for _ in range(N):
    l = list(map(int, input().split()))
    tree[l[0]]['c'] = l[2:]
    for i in l[2:]:
        tree[i]['p'] = l[0]


def calcDepth(tree, root, curDepth=0):
    tree[root]['d'] = curDepth
    [calcDepth(tree, c, curDepth + 1) for c in tree[root]['c']]


calcDepth(tree, 0)

for i in range(N):
    state = 'leaf'
    if tree[i]['p'] == -1:
        state = 'root'
    elif len(tree[i]['c']):
        state = 'internal node'
    print('node {i}: parent = {p}, depth = {d}, {state}, {ch}'.format(
        i=i, p=tree[i]['p'], d=tree[i]['d'], state=state, ch=tree[i]['c']
    ))

Submission status: Wrong Answer

Solution code:
NIL = -1


class Node:
    parent = NIL
    left = NIL
    right = NIL
    label = ""


def show_info(u):
    global T, D
    if T[i].parent == NIL:
        T[u].label = "root"
    elif T[i].left == NIL:
        T[u].label = "leaf"
    else:
        T[u].label = "internal node"
    print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(u, T[u].parent, D[u], T[u].label, getChildren(u)))


def getChildren(u):
    global T
    c = T[u].left
    R =[]
    while c != NIL:
        R.append(c)
        c = T[c].right
    return R


def setDepth(u,p):
    global T, D
    D[u] = p
    if T[u].right != NIL:
        setDepth(T[u].right, p)
    if T[u].left != NIL:
        setDepth(T[u].left, p + 1)


if __name__ == "__main__":
    n = int(input())
    T = [None] * n
    D = [None] * n
    for i in range(n):
        T[i] = Node()
    for i in range(n):
        tmp = list(map(int, input().split()))
        id = tmp.pop(0)
        k = tmp.pop(0)
        C = tmp
        if k != 0:
            T[id].left = C[0]
            for j in range(len(C)):
                T[C[j]].parent = id
            for j in range(len(C) - 1):
                T[C[j]].right = C[j + 1]
    # ??±????¨????
    setDepth(0, 0)
    for i in range(n):
        show_info(i)

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self):
        self.id = None
        self.parent = None
        self.children = []
        self.node_type = None
        self.deep = None



def trace_root(nodes, current_node_id):
    depth = 0
    while nodes[current_node_id].parent != -1:
        current_node_id = nodes[current_node_id].parent
        depth += 1
    return depth


if __name__ == '__main__':
    n = int(input())
    nodes = {}
    for x in xrange(n):
        nodes.update({x:Node()})

    for x in xrange(n):
        node_data = map(int, raw_input().split(" "))
        tmp_node = nodes.get(node_data[0])
        tmp_node.id = node_data[0]
        if node_data[1] == 0:
            tmp_node.node_type = "leaf"
        else:
            tmp_node.node_type = "internal node"
            for y in node_data[2:]:
                tmp_node.children.append(y)
                child_node = nodes.get(y)
                child_node.parent = node_data[0]
                nodes[y] = child_node
        nodes[x] = tmp_node

    # for node in nodes.values():
    #     print "node ", node.id, ": parent =", node.parent, ", depth =", node.deep, ",", node.node_type, ",", node.children

    root_node = None
    for node in nodes.values():
        if node.parent == None:
            node.parent = -1
            node.deep = 0
            node.node_type = "root"
            break

    print nodes
    for node in nodes.values():
        depth = trace_root(nodes, node.id)
        node.deep = depth
            # else:

        print "node", node.id, ": parent =", node.parent, ", depth =", node.deep, ",", node.node_type,",", node.children

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self):
        self.id = None
        self.parent = None
        self.children = []
        self.node_type = None
        self.deep = None



def trace_root(nodes, current_node_id):
    depth = 0
    while nodes[current_node_id].parent != -1:
        current_node_id = nodes[current_node_id].parent
        depth += 1
    return depth


if __name__ == '__main__':
    n = int(input())
    nodes = {}
    for x in xrange(n):
        nodes.update({x:Node()})

    for x in xrange(n):
        node_data = map(int, raw_input().split(" "))
        tmp_node = nodes.get(node_data[0])
        tmp_node.id = node_data[0]
        if node_data[1] == 0:
            tmp_node.node_type = "leaf"
        else:
            tmp_node.node_type = "internal node"
            for y in node_data[2:]:
                tmp_node.children.append(y)
                child_node = nodes.get(y)
                child_node.parent = node_data[0]
                nodes[y] = child_node
        nodes[x] = tmp_node

    # for node in nodes.values():
    #     print "node ", node.id, ": parent =", node.parent, ", depth =", node.deep, ",", node.node_type, ",", node.children

    root_node = None
    for node in nodes.values():
        if node.parent == None:
            node.parent = -1
            node.deep = 0
            node.node_type = "root"
            break

    print nodes
    for node in nodes.values():
        depth = trace_root(nodes, node.id)
        node.deep = depth
            # else:

        print "node %d: parent = %d, depth = %d, %s, %s" % (node.id, node.parent, node.deep, node.node_type, node.children)

Submission status: Wrong Answer

Solution code:
# coding=utf-8

class Node:
    def __init__(self, idx, degree, children=None):
        self.id = idx
        self.parent = -1 #??????
        self.depth = 0 #??????
        self.type = None #??????
        self.children = children

n = int(input())
data = [list(map(int, input().split())) for x in range(n)]
node_list = []

for data_row in data:
    idx, degree, *children = data_row
    node = Node(idx, degree, children)
    node_list.append(node)

### set parent & type ###
for i, node in enumerate(node_list):
    if node.children:
        node.type = "internal node"
        for child in node.children:
            node_list[child].parent = i
    else:
        node.type = "leaf"

### calc depth ###
for i, node in enumerate(node_list):
    depth = 0
    parent = node.parent
    #?????\???type
    if parent == -1:
        node.type = "root"
    while parent != -1:
        parent = node_list[parent].parent
        depth += 1
    node.depth = depth

for node in node_list:
    print("node:", str(node.id) + ", parent =", str(node.parent) + ", depth =", str(node.depth) + ",", node.type + "," , node.children)

Submission status: Wrong Answer

Solution code:
import sys


def dep(u, p):
    D[u] = p
    if tree[u][2] != NIL:
        dep(tree[u][2], p)
    if tree[u][1] != NIL:
        dep(tree[u][1], p+1)


def print_ans():
    for i in range(n):
        if tree[i][0] == NIL:
            typea = "root"
        elif tree[i][1] == NIL:
            typea = "leaf"
        else:
            typea = "internal node"
        child = []
        b = tree[i]
        if b[1] != NIL:
            child.append(b[1])
            b = tree[b[1]]
            while b[2] != NIL:
                child.append(b[2])
                b = tree[b[2]]
        print("node {}: parent = {}, depth = {}, {}, {}"
              .format(i, tree[i][0], D[i], typea, child))


if __name__ == "__main__":
    NIL = -1
    n = int(sys.stdin.readline())
    tree = [[NIL, NIL, NIL] for i in range(n)]
    D = [0 for i in range(n)]
    for a in sys.stdin.readlines():
        a = list(map(int, a.split()))
        if a[1] > 0:
            tree[a[0]][1] = a[2]    # ???????????????
            for i in range(a[1]):
                tree[a[i+2]][0] = a[0] # ????????????
                if i != a[1] - 1:
                    tree[a[i+2]][2] = a[i+3] # ??????????????????
    dep(0, 0)
    print_ans()

Submission status: Wrong Answer

Solution code:
import sys


def dep(u, p):
    D[u] = p
    for i in tree[u][3]:
        print("a")
        dep(i, p+1)


def print_ans():
    for i in range(n):
        print("node {}: parent = {}, depth = {}, {}, {}"
              .format(i, tree[i][0], D[i],
                      "root" if tree[i][0] == NIL else "leaf" if tree[i][1] == NIL else "internal node",
                      tree[i][3]))


if __name__ == "__main__":
    NIL = -1
    n = int(sys.stdin.readline())
    tree = [[NIL, NIL, NIL] for i in range(n)]
    D = [0 for i in range(n)]
    root = set(range(n))
    for a in sys.stdin.readlines():
        a = list(map(int, a.split()))
        tree[a[0]].append(a[2:])
        if a[1] > 0:
            tree[a[0]][1] = a[2]    # ???????????????
            for i in range(a[1]):
                tree[a[i+2]][0] = a[0] # ????????????
                if i != a[1] - 1:
                    tree[a[i+2]][2] = a[i+3] # ??????????????????
        root -= set(a[2:])
    dep(root.pop(), 0)
    print_ans()

Submission status: Wrong Answer

Solution code:
def main():
    n = input()
    tree = MyTree(n)
    for i in range(n):
        id_k_cn = map(int,raw_input().split())
        id_node = id_k_cn.pop(0)
        k = id_k_cn.pop(0)
        tree.add(id_node,k,None,id_k_cn)

    tree.set_depth(tree.nodes[0],0)
    
    for node in tree.nodes:
        print "node {0}: parent = {1}, depth = {2}, {3}, {4}".format(node.id_self, node.id_parent, node.depth, node.node_type, node.id_children)

class MyTree():
    def __init__(self,num_nodes):
        self.nodes = [None]*num_nodes

    def add(self,id_node,num_children,id_parent,id_children):
        self.nodes[id_node] = MyNode(id_node,id_parent,id_children)

        if self.nodes[id_node].id_self == 0:
            self.nodes[id_node].id_parent = -1
            self.nodes[id_node].node_type = "root"
        else:
            if num_children == 0:
                self.nodes[id_node].node_type = "leaf"
            else:
                self.nodes[id_node].node_type = "internal node"
            for item in self.nodes:
                if not item == None:
                    if id_node in item.id_children:
                        self.nodes[id_node].id_parent = item.id_self
                        break

    def set_depth(self,node,depth):
        node.depth = depth
        node.id_children
        for item in node.id_children:
            self.set_depth(self.nodes[item],depth+1)

class MyNode():
    def __init__(self,id_self,id_parent,id_children):
        self.id_self = id_self
        self.id_parent = id_parent
        self.id_children = id_children
        self.depth = None
        self.node_type = None


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class Node():
    def __init__(self, id, num, child, nodetype=None, depth=-1, parent=-1):
        self.id = id
        self.num = num
        self.child = child
        self.nodetype = nodetype
        self.depth = depth
        self.parent = parent
    def showFinal(self):
        print 'node %d: parent = %d, depth = %d, %s,' % (self.id, self.parent, self.depth, self.nodetype), self.child
        
def calcDepth(node):
    if node.parent == -1:
        return 0
    return calcDepth(tree[node.parent]) + 1

n = int(raw_input())
tree = []

for i in range(n):
    a = map(int, raw_input().split())
    if len(a) > 2:
        tree.append(Node(a[0], a[1], a[2:]))
    else:
        tree.append(Node(a[0], a[1], [], nodetype='leaf'))
        
for i in range(n):
    children = tree[i].child
    for j in children:
        tree[j].parent = tree[i].id

for i in range(n):
    tree[i].depth = calcDepth(tree[i])
    if tree[i].parent != -1 and tree[i].child != []:
        tree[i].nodetype = 'internal node'
    elif tree[i].parent == -1:
        tree[i].nodetype = 'root'
        
for i in range(n):
    tree[i].showFinal()

Submission status: Wrong Answer

Solution code:
n = int(input())

tree = {}

for i in range(n):
    row = [int(k) for k in input().split()]
    id = row[0]
    ch = row[2:]
    val = tree.get(id, [])
    val += ch
    tree[id] = val

def printInfo(id):
    parent = -1
    depth = 0
    for p in tree.keys():
        if id in tree[p]:
            parent = p
            break
    for p in tree.keys():
        if id in tree[p]:
            depth += 1
    if parent == -1:
        type = 'root'
    elif tree[id] != []:
        type = 'internal node'
    else:
        type = "leaf"
    print('node %d: parent = %d, depth = %d, %s, %s' %(id,parent,depth,type,str(tree[id])))

for p in tree.keys():
    printInfo(p)

Submission status: Wrong Answer

Solution code:
n = int(input())
tree = {}

for i in range(n):
    row = [int(k) for k in input().split()]
    id = row[0]
    ch = row[2:]
    val = tree.get(id, [])
    val += ch
    tree[id] = val



def printInfo(id):
    parent = -1
    depth = 0
    for p in tree.keys():
        if id in tree[p]:
            parent = p
            break
    l=list(tree.keys())[-1]
    while True:
        for p in tree.keys():
            if id in tree[p]:
                depth += 1
                id = p
                break
        if p == l:
            break
    for p in tree.keys():
        if id in tree[p]:
            depth += 1
    if parent == -1:
        type = 'root'
    elif tree[id] != []:
        type = 'internal node'
    else:
        type = "leaf"
    print('node %d: parent = %d, depth = %d, %s, %s' %(id,parent,depth,type,str(tree[id])))

for p in tree.keys():
    printInfo(p)

Submission status: Wrong Answer

Solution code:
n = int(input())
tree = {}

for i in range(n):
    row = [int(k) for k in input().split()]
    id = row[0]
    ch = row[2:]
    val = tree.get(id, [])
    val += ch
    tree[id] = val



def printInfo(id):
    parent = -1
    depth = 0
    for p in tree.keys():
        if id in tree[p]:
            parent = p
            break
    l=list(tree.keys())[-1]
    oid = id
    while True:
        for p in tree.keys():
            if id in tree[p]:
                depth += 1
                id = p
                break
        if p == l:
            break
    for p in tree.keys():
        if id in tree[p]:
            depth += 1
    if parent == -1:
        type = 'root'
    elif tree[id] != []:
        type = 'internal node'
    else:
        type = "leaf"
    print('node %d: parent = %d, depth = %d, %s, %s' %(oid,parent,depth,type,str(tree[id])))

for p in tree.keys():
    printInfo(p)

Submission status: Wrong Answer

Solution code:
n = int(input())
tree = {}

for i in range(n):
    row = [int(k) for k in input().split()]
    id = row[0]
    ch = row[2:]
    val = tree.get(id, [])
    val += ch
    tree[id] = val



def printInfo(id):
    parent = -1
    depth = 0
    for p in tree.keys():
        if id in tree[p]:
            parent = p
            break
    l=list(tree.keys())[-1]
    oid = id
    while True:
        for p in tree.keys():
            if id in tree[p]:
                depth += 1
                id = p
                break
        if p == l:
            break
    for p in tree.keys():
        if id in tree[p]:
            depth += 1
    if parent == -1:
        type = 'root'
    elif tree[id] != []:
        type = 'internal node'
    else:
        type = "leaf"
    print('node %d: parent = %d, depth = %d, %s, %s' %(oid,parent,depth,type,str(tree[oid])))

for p in tree.keys():
    printInfo(p)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
tree = {n:{"parent":-1, "left": -1, "right": -1} for n in range(N)} # left-child right-sibing
parent = set([n for n in range(N)])

for n in range(N):
    inp = [int(n) for n in input().split()]
    tree[n]["children"] = inp[2:]

    tree[inp[0]]["left"] = inp[2] if len(inp) > 2 else -1
    
    for ip in inp[2:]:
        tree[ip]["parent"] = inp[0]
    
    for i, ip in enumerate(inp[2:-1]):
        tree[inp[2+i]]["right"] = inp[3+i]
    parent = parent.difference(inp[2:])    

def set_depth(n, depth):
    tree[n]["depth"] = depth
    if tree[n]["left"] != -1:
        set_depth(tree[n]["left"], depth+1)
    if tree[n]["right"] != -1:
        set_depth(tree[n]["right"], depth)

set_depth(parent.pop(), 0)
        
for n in range(N):
    if tree[n]["parent"] == -1:
        tree[n]["type"] = "root"
    elif tree[n]["children"] != []:
        tree[n]["type"] = "internal node"
    else:
        tree[n]["type"] = "leaf"
        
    print("node {}: parent = {}, depth = {}, {}, {}"\
          .format(n, tree[n]["parent"], tree[n]["depth"], tree[n]["type"], tree[n]["children"]))

Submission status: Wrong Answer

Solution code:
N = int(input())
tree = [[-1, 0, []] for _ in [0]*N]

for _ in [0]*N:
    a = tuple(map(int, input().split()))
    v = a[0]
    n = a[1]
    children = list(a[2:])
    depth = tree[v][1]
    tree[v][2] = children
    for child in children:
        tree[child][0] = v
        tree[child][1] = depth + 1

for i in range(N):
    v = tree[i]
    parent = v[0]
    depth = v[1]
    children = v[2]
    node_type = "root" if parent == -1 else "leaf" if len(children) == 0 else "internal node"
    print("node %d: parent = %d, depth = %d, %s, %s" % (i, parent, depth, node_type, str(children)))

Submission status: Wrong Answer

Solution code:
n = int(input())
tree = [[-1,0,0,0] for _ in range(n)]
t = ["root", "internal node", "leaf"]

for i in range(n):
    _, _, *c = map(int, input().split())
    tree[i][3] = c
    if tree[i][2]:
        tree[i][2] = 1
    for k in c:
        tree[k][0] = i
        tree[k][1] = tree[i][1] + 1
        tree[k][2] = 2

for i in range(n):
    tree[i][2] = t[tree[i][2]]
    print("node {}: parent = {}, depth = {}, {}, {}".format(i, *tree[i]))

Submission status: Wrong Answer

Solution code:
n = int(input())
tree = [[-1,0,0,0] for _ in range(n)]
t = ["root", "internal node", "leaf"]

for i in range(n):
    _, _, *c = map(int, input().split())
    tree[i][3] = c
    if c:
        tree[i][2] -= 1
        for k in c:
            tree[k][0] = i
            tree[k][1] = tree[i][1] + 1
            tree[k][2] += 1

for i in range(n):
    tree[i][2] = t[tree[i][2]+1]
    print("node {}: parent = {}, depth = {}, {}, {}".format(i, *tree[i]))

Submission status: Wrong Answer

Solution code:
n = int(input())
tree = [[-1,0,0,0] for _ in range(n)]
t = ["root", "internal node", "leaf"]

for _ in range(n):
    i, _, *c = map(int, input().split())
    tree[i][3] = c
    if c:
        tree[i][2] -= 1
        for k in c:
            tree[k][0] = i
            tree[k][1] = tree[i][1] + 1
            tree[k][2] += 1

for i in range(n):
    tree[i][2] = t[tree[i][2]+1]
    print("node {}: parent = {}, depth = {}, {}, {}".format(i, *tree[i]))

Submission status: Wrong Answer

Solution code:
n = int(input())
tree = [[-1,0,0,0] for _ in range(n)]
t = ["root", "internal node", "leaf"]

for _ in range(n):
    i, _, *c = map(int, input().split())
    tree[i][3] = c
    if c:
        tree[i][2] = 1
    for k in c:
        tree[k][0] = i
        tree[k][1] = tree[i][1] + 1
        tree[k][2] = 2

for i in range(n):
    tree[i][2] = t[tree[i][2]]
    print("node {}: parent = {}, depth = {}, {}, {}".format(i, *tree[i]))

Submission status: Wrong Answer

Solution code:
n = int(input())
tree = [[-1,0,0,0] for _ in range(n)]
t = ["root", "internal node", "leaf"]

for _ in range(n):
    i, _, *c = map(int, input().split())
    tree[i][3] = c
    for k in c:
        tree[k][0] = i
        tree[k][1] = tree[i][1] + 1

for i in range(n):
    if tree[i][0] == -1:
        tree[i][2] = t[0]
    elif tree[i][3]:
        tree[i][2] = t[1]
    else:
        tree[i][2] = t[2]
    print("node {}: parent = {}, depth = {}, {}, {}".format(i, *tree[i]))

Submission status: Wrong Answer

Solution code:
def set_pdt(i, parent, depth):
    u = tree[i]
    u[0], u[1] = parent, depth
    for c in u[3]:
        set_pdt(c, parent+1, depth+1)
    else:
        if u[0] == -1:
            u[2] = "root"
        elif u[3]:
            u[2] = "internal node"
        else:
            u[2] = "leaf"

n = int(input())
#         p d t ch
tree = [[-1,0,0,0] for _ in range(n)]
root = set(range(n))

for _ in range(n):
    i, k, *c = map(int, input().split())
    tree[i][3] = c
    root -= set(c)
    
for u in root:
    set_pdt(u, -1, 0)

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

Submission status: Wrong Answer

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

n = int(input())
tree = [[None] for i in range(n)]
root = set(range(n))

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

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

for i in range(n):
    c, p, d = tree[i]
    if p == -1:
        t = "root"
    elif len(c) == 0:
        t = "leaf"
    else:
        t = "internal node"
    print("node ", i, ": parent = ", p, " depth = ", d, ", ", t, ", ", c, sep="")

Submission status: Wrong Answer

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


class Tree(object):
    def __init__(self):
        self._tree = None
        self._print_dict = {}

    def add(self, node, children):
        if self._tree is None:
            self._tree = {node: {n: {} for n in children}}
            self._print_dict[node] = \
                "node {0}: parent = {1}, depth = {2}, {3}, {4}".format(
                node, -1, 0, "root", children)
        else:
            for parent, current in self._tree.items():
                self._rec_add(parent, 1, current, node, children)

    def _rec_add(self, parent, depth, current, target, children):
        if current.get(target) is not None:
            current[target] = {n: {} for n in children}
            self._print_dict[target] = \
                "node {0}: parent = {1}, depth = {2}, {3}, {4}".format(
                target, parent, depth, self._type(parent, children), children)
            return True
        else:
            for parent, current in current.items():
                ret = self._rec_add(parent, depth+1, current, target, children)
                if ret:
                    return True
            return False

    def _type(self, parent, children):
        if parent == -1:
            return "root"
        elif children != []:
            return "internal node"
        else:
            return "leaf"

    def print_info(self):
        for i, info in sorted(self._print_dict.items()):
            print(info)


if __name__ == "__main__":
    n = int(input())
    lst = [[int(n) for n in val.split()] for val in sys.stdin.readlines()]
    lst = [(val[0], val[2:]) for val in lst]
    tree = Tree()
    for node, children in lst:
        tree.add(node, children)
    tree.print_info()

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self, x, y):
        self.id = x
        self.k = y
        self.children = []
        self.type = ''
        self.depth = 20
        self.parent = '-1'

def findRoot(tree):
    for x in tree:
        for y in x.children:
            for a in tree:
                if y == a.id:
                    a.type = 'internal node'
                    a.parent = x.id
    for i,x in enumerate( tree):
        if x.type == 'root':
            return i

def findLeaf(tree):
    for x in tree:
        if x.k == 0:
            x.type = 'leaf'

def setd(tree,node,d):
    node.depth = d
    if len(node.children) == 0:
        return
    else:
        for tmp in node.children:
            for x in tree:
                if x.id == tmp:
                    setd(tree,x,d+1)


if __name__ == '__main__':
    n = (int)(input())
    tree = [None]*n
    for i in range(0,n):
        tmp = input().split()
        a = Node(tmp[0],(int)(tmp[1]))
        a.children=tmp[2:]
        a.type = 'root'
        tree[int(a.id)] = a
    ri = findRoot(tree)
    findLeaf(tree)
    setd(tree,tree[ri],0)
    
    for tmp in tree:
        print("node {}: parent = {}, depth = {}, {}, {}".format(tmp.id, tmp.parent,tmp.depth,tmp.type,list(map(int,tmp.children))))

Submission status: Wrong Answer

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


class Node():
    def __init__(self, ID, parent=-1, left=-1, right=-1, depth=-1, children=[]):
        self.id = ID
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
        self.children = children


if __name__ == '__main__':

    n = int(input())
    tree = [Node(i) for i in range(n)]

    for _ in range(n):
        line = [int(l) for l in input().split(" ")]
        ID = line[0]
        d = line[1]
        if d == 0:
            continue
        else:
            children = line[2:]
            tree[ID].children = children
            tree[ID].left = children[0]
            for j in range(0, d):
                tree[children[j]].parent = ID
                if j < d - 1:
                    tree[children[j]].right = children[j + 1]

    def setDepth(u, p):
        tree[u].depth = p
        if tree[u].right != -1:
            setDepth(tree[u].right, p)
        if tree[u].left != -1:
            setDepth(tree[u].left, p + 1)

    setDepth(0, 0)

    for node in tree:
        if node.parent == -1:
            n_type = "root"
        elif node.left != -1:
            n_type = "internal node"
        else:
            n_type = "leaf"

        print("node {}: parent = {}, depth = {}, {}, {}".format(
            node.id, node.parent, node.depth, n_type, node.children))