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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May 19 19:34:44 2018
ALDS1_7_A
@author: maezawa
"""

n = int(input())

parent =[]
left = []
right = [None for _ in range(n)]
child = [[] for _ in range(n)]
depth = [None for _ in range(n)]

def get_parent(i):
    for j in range(n):
        if i in child[j]:
            return j
    return -1

def get_left(i):
    if len(child[i]) == 0:
        return None
    return child[i][0]

def set_right():
    global right
    for j in range(n):
        for i, k in enumerate(child[j]):
            #if len(child[j]) > i+1:
            try:
                right[k] = child[j][i+1]
            except:
                continue


#def get_right(i):
#    j = parent[i]
#    try:
#        ind = child[j].index(i)
#    except:
#        return None
#    if len(child[j]) > ind+1:
#        return child[j][ind+1]
#    else:
#        return None
    
def set_depth(i, p):
    global depth
    if depth[i] != None:
        return
    depth[i] = p
    if right[i] != None:
        set_depth(right[i], p)
    if left[i] != None:
        set_depth(left[i], p+1)
       
def get_depth(i):
    global depth
    if depth[i] != None:
        return depth[i]
    d = 0
    u = i
    while parent[u] != -1:
        u = parent[u]
        d += 1
    depth[i] = d
    return d

    
for i in range(n):
    line = list(map(int, input().split()))
    child[line[0]] = [line[i+2] for i in range(line[1])]

for i in range(n):
    parent.append(get_parent(i))
    left.append(get_left(i))

set_right()
    
for i in range(n):
    out_str = 'node {}: parent = {}, depth = {}, '.format(i,parent[i],get_depth(i))
    if parent[i] == -1:
        out_str += 'root, '
    elif len(child[i]) == 0:
        out_str += 'leaf, '
    else:
        out_str += 'internal node, '
    out_str += str(child[i])
    print(out_str)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May 19 19:34:44 2018
ALDS1_7_A
@author: maezawa
"""

n = int(input())

parent =[]
left = []
right = [None for _ in range(n)]
child = [[] for _ in range(n)]
depth = [None for _ in range(n)]

def get_parent(i):
    for j in range(n):
        if i in child[j]:
            return j
    return -1

def get_left(i):
    if len(child[i]) == 0:
        return None
    return child[i][0]

def set_right():
    global right
    for j in range(n):
        for i, k in enumerate(child[j]):
            #if len(child[j]) > i+1:
            try:
                right[k] = child[j][i+1]
            except:
                continue


#def get_right(i):
#    j = parent[i]
#    try:
#        ind = child[j].index(i)
#    except:
#        return None
#    if len(child[j]) > ind+1:
#        return child[j][ind+1]
#    else:
#        return None
    
def set_depth(i, p):
    global depth
    if depth[i] != None:
        return
    depth[i] = p
    if right[i] != None:
        set_depth(right[i], p)
    if left[i] != None:
        set_depth(left[i], p+1)
       
def get_depth(i):
    global depth
    if depth[i] != None:
        return depth[i]
    d = 0
    u = i
    while parent[u] != -1:
        u = parent[u]
        d += 1
    depth[i] = d
    return d

    
for i in range(n):
    line = list(map(int, input().split()))
    child[line[0]] = [line[i+2] for i in range(line[1])]

for i in range(n):
    parent.append(get_parent(i))
    left.append(get_left(i))

p = get_depth(0)
set_depth(0,p)    
set_right()
    
for i in range(n):
    out_str = 'node {}: parent = {}, depth = {}, '.format(i,parent[i],get_depth(i))
    if parent[i] == -1:
        out_str += 'root, '
    elif len(child[i]) == 0:
        out_str += 'leaf, '
    else:
        out_str += 'internal node, '
    out_str += str(child[i])
    print(out_str)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nodes = []
id_list = []
output = []
cnt = 0
for i in range(n):
    id, _, *li = list(map(int, input().split(' ')))
    nodes.append(li)
    id_list.append(id)

def rooted_tree(id, depth, parent):
    out = {}
    ind = id_list.index(id)
    out['node'] = id
    out['parent'] = parent
    out['depth'] = depth
    out['c'] = nodes[ind]
    if len(nodes[ind]) == 0:
        if depth == 0:
            out['type'] = 'root'
        else:
            out['type'] = 'leaf'
        output.append(out)
        return
    if depth == 0:
        out['type'] = 'root'
    else:
        out['type'] = 'internal node'
    output.append(out)
    for i in (nodes[ind]):
        rooted_tree(i, depth+1, id)

check_parent = [0 for i in range(n)]
for i in range(n):
    for j in nodes[i]:
        check_parent[j] += 1
root = check_parent.index(0)
rooted_tree(root, 0, -1)
for line in sorted(output, key=lambda x:x['node']):
    print("node {}: parent = {}, depth = {}, {}, {}".format(line['node'], line['parent'], line['depth'], line['type'], line['c']))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nodes = []
id_list = []
output = []
cnt = 0
root = set(range(n))
for i in range(n):
    id, _, *li = list(map(int, input().split(' ')))
    root -= set(li)
    nodes.append(li)
    id_list.append(id)

def rooted_tree(id, depth, parent):
    out = {}
    ind = id_list.index(id)
    out['node'] = id
    out['parent'] = parent
    out['depth'] = depth
    out['c'] = nodes[ind]
    if len(nodes[ind]) == 0:
        if depth == 0:
            out['type'] = 'root'
        else:
            out['type'] = 'leaf'
        output.append(out)
        return
    if depth == 0:
        out['type'] = 'root'
    else:
        out['type'] = 'internal node'
    output.append(out)
    for i in (nodes[ind]):
        rooted_tree(i, depth+1, id)

rooted_tree(root.pop(), 0, -1)
for line in sorted(output, key=lambda x:x['node']):
    print("node {}: parent = {}, depth = {}, {}, {}".format(line['node'], line['parent'], line['depth'], line['type'], line['c']))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nodes = []
id_list = []
output = [None for i in range(n)]
cnt = 0
root = set(range(n))
for i in range(n):
    id, _, *li = list(map(int, input().split(' ')))
    root -= set(li)
    nodes.append(li)
    id_list.append(id)

def rooted_tree(id, depth, parent):
    out = {}
    ind = id_list.index(id)
    out['node'] = id
    out['parent'] = parent
    out['depth'] = depth
    out['c'] = nodes[ind]
    if len(nodes[ind]) == 0:
        if depth == 0:
            out['type'] = 'root'
        else:
            out['type'] = 'leaf'
        output[id] = out
        return
    if depth == 0:
        out['type'] = 'root'
    else:
        out['type'] = 'internal node'
    output[id] = out
    for i in (nodes[ind]):
        rooted_tree(i, depth+1, id)

rooted_tree(root.pop(), 0, -1)
for line in output:
    print("node {}: parent = {}, depth = {}, {}, {}".format(line['node'], line['parent'], line['depth'], line['type'], line['c']))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nodes = []
id_list = []
output = [None for i in range(n)]
cnt = 0
root = set(range(n))
for i in range(n):
    id, _, *li = list(map(int, input().split(' ')))
    root -= set(li)
    nodes.append(li)
    id_list.append(id)

def rooted_tree(id, depth, parent):
    out = {}
    ind = id_list.index(id)
    out['node'] = id
    out['parent'] = parent
    out['depth'] = depth
    out['c'] = nodes[ind]
    if depth == 0:
        out['type'] = 'root'
    elif len(nodes[ind]) == 0:
        out['type'] = 'leaf'
    else:
        out['type'] = 'internal node'
    output[id] = out
    for i in (nodes[ind]):
        rooted_tree(i, depth+1, id)

rooted_tree(root.pop(), 0, -1)
for line in output:
    print("node {}: parent = {}, depth = {}, {}, {}".format(line['node'], line['parent'], line['depth'], line['type'], line['c']))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def calc_depth(tree, i):
    for j in tree[i][2:]:
        tree[j][0] += 1
        calc_depth(tree, j)


n = int(stdin.readline())
tree = [0] * n
#assert 1 <= n <= 100000
for _ in range(n):
    node = [int(s) for s in stdin.readline().split()]
    tree[node[0]] = [0] + node[1:]

for i in range(n):
    calc_depth(tree, i)

fmt = 'node {}: parent = {}, depth = {}, {}, {}'.format
for i, node in enumerate(tree):
    pa = -1
    for j, n in enumerate(tree):
        if i in n[2:]:
            pa = j
            break
    if pa == -1:
        kind = 'root'
    elif not node[1]:
        kind = 'leaf'
    else:
        kind = 'internal node'
    print(fmt(i, pa, node[0], kind, node[2:]))

Submission status: Accepted

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" not in node:
        return "leaf"
    return "internal node"

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

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

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: Accepted

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: Accepted

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


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

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

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

for count in range(n):
    j = tree[count]

    if j.parent == -1:
        state = "root"
    elif j.child:
        state = "internal node"
    else:
        state = "leaf"

    print("node {}: parent = {}".format(count, j.parent), "depth = {}".format(
        j.depth), state, "[{}]".format(", ".join(map(str, j.child))), sep=", ")

Submission status: Accepted

Solution code:
n = int(input())
rt = {}
clist = [0 for i in range(n)]
for i in range(n):
    id, k, *c = list(map(int, input().split()))
    for j in c:
        rt[j] = id
    clist[id] = c
for i in range(n):
    print("node %d: parent = "%i, end = "")
    p = [i]
    while 1:
        try:
            p.append(rt[p[-1]])
        except:
            break
    if len(p) == 1:
        print("-1, depth = 0, root,",clist[i])
    else:
        print("%d, depth ="%p[1] ,len(p) - 1, end = "")
        if clist[i] == []:
            print(", leaf, []")
        else:
            print(", internal node,",clist[i])

Submission status: Accepted

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

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
	a = list(map(int, input().split()))
	id = a[0]
	node = nodes[id]
	if node.parent_id != -1:
		node.depth = nodes[node.parent_id].depth + 1

	m = a[1]
	children = []
	for j in range(m):
		child_id = a[j + 2]
		children.append(child_id)
		nodes[child_id].parent_id = id
		nodes[child_id].depth = node.depth + 1
	node.children = children

for i in range(n):
	print(nodes[i])

Submission status: Accepted

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

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
	a = list(map(int, input().split()))
	id = a[0]
	node = nodes[id]
	if node.parent_id != -1:
		node.depth = nodes[node.parent_id].depth + 1

	m = a[1]
	children = [0] * m
	for j in range(m):
		child_id = a[j + 2]
		children[j] = child_id
		nodes[child_id].parent_id = id
		nodes[child_id].depth = node.depth + 1
	node.children = children

for i in range(n):
	print(nodes[i])

Submission status: Accepted

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

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

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

calc_depth(nodes)

for i in range(n):
	print(nodes[i])

Submission status: Accepted

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

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

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

calc_depth(nodes)

for i in range(n):
	print(nodes[i])

Submission status: Accepted

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

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

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

    for i in range(n):
        d = 0
        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: Accepted

Solution code:
from sys import stdin

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

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

    for i in range(n):
        d = 0
        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: Accepted

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

from sys import setrecursionlimit

setrecursionlimit(21)


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


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


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


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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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


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


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

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

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


main()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self):
        self.parent = -1

def dfs(v, d=0):
    G[v].depth = d
    for child in G[v].children:
        dfs(child,d+1)

N = int(input())
G = [Node() for _ in range(N)]
for _ in range(N):
    idx,k,*children = [int(x) for x in input().split()]
    G[idx].children = children
    if k:
        G[idx].type = 'internal node'
    else:
        G[idx].type = 'leaf'
    for child in children:
        G[child].parent = idx

root = [i for i,x in enumerate(G) if x.parent == -1][0]
G[root].type = 'root'
dfs(root)
for i,node in enumerate(G):
    print('node {}: parent = {}, depth = {}, {}, [{}]'.format(
        i,
        node.parent,
        node.depth,
        node.type,
        ', '.join(map(str,node.children))
        )
    )

Submission status: Accepted

Solution code:
n = int(input())
child = {}
parent = {}

for i in range(n):
    a = list(map(int, input().split()))
    child[a[0]] = a[2:]
    for i in child[a[0]]:
        parent[i] = a[0] 

root = (set(child)-set(parent)).pop()
depth = [None]*n
depth[root] = 0
parent[root] = -1

    
def dfs(s):
    for i in child[s]:
            depth[i]=depth[s]+1
            dfs(i)
    
dfs(root)
    
for i in range(n):
    node_type = "root" if parent[i] == -1 else "leaf" if len(child[i]) == 0 else "internal node"
    print(f'node {i}: parent = {parent[i]}, depth = {depth[i]}, {node_type}, {child[i]}')

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

class Node():
    def __init__(self, p, l, r):
        self.p = p
        self.l = l
        self.r = r


def rec(u, p):
    D[u] = p
    if T[u].r != -1:
        rec(T[u].r, p)
    if T[u].l != -1:
        rec(T[u].l, p + 1)


N = int(input())
T = [Node(-1, -1, -1) for _ in range(N)]
D = [-1] * N
for i in range(N):
    i, k, *cs = map(int, input().split())
    for j, c in enumerate(cs):
        if j == 0:
            T[i].l = c
        else:
            T[l].r = c
        l = c
        T[c].p = i
for i, t in enumerate(T):
    if t.p == -1:
        r = i
rec(r, 0)
for i, t in enumerate(T):
    cs = []
    c = t.l
    while c != -1:
        cs.append(c)
        c = T[c].r
    if t.p == -1:
        print('node {}: parent = {}, depth = {}, root, {}'
              .format(i, t.p, D[i], cs))
    elif t.l == -1:
        print('node {}: parent = {}, depth = {}, leaf, {}'
              .format(i, t.p, D[i], cs))
    else:
        print('node {}: parent = {}, depth = {}, internal node, {}'
              .format(i, t.p, D[i], cs))

Submission status: Accepted

Solution code:
def f(n,e,a):
    d[n].extend([a,e,"root" if a<0 else "internal node" if len(d[n][1]) else "leaf"])
    for i in d[n][1]: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 = {2}, depth = {3}, {4}, {1}".format(*i)