Problem:

Rooted Trees

A graph G = (V, E) is a data structure where V is a finite set of vertices and E is a binary relation on V represented by a set of edges. Fig. 1 illustrates an example of a graph (or graphs).

Fig. 1

A free tree is a connnected, acyclic, undirected graph. A rooted tree is a free tree in which one of the vertices is distinguished from the others. A vertex of a rooted tree is called "node."

Your task is to write a program which reports the following information for each node u of a given rooted tree T:

node ID of u

parent of u

depth of u

node type (root, internal node or leaf)

a list of chidlren of u

If the last edge on the path from the root r of a tree T to a node x is (p, x), then p is the parent of x, and x is a child of p. The root is the only node in T with no parent.

siblings.

-->

A node with no children is an external node or leaf. A nonleaf node is an internal node

The number of children of a node x in a rooted tree T is called the degree of x.

The length of the path from the root r to a node x is the depth of x in T.

Here, the given tree consists of n nodes and evey node has a unique ID from 0 to n-1.

Fig. 2 shows an example of rooted trees where ID of each node is indicated by a number in a circle (node). The example corresponds to the first sample input.

Fig. 2

Input

The first line of the input includes an integer n, the number of nodes of the tree.

In the next n lines, the information of each node u is given in the following format:

id k c1 c2 ... ck

where id is the node ID of u, k is the degree of u, c1 ... ck are node IDs of 1st, ... kth child of u. If the node does not have a child, the k is 0.

Output

Print the information of each node in the following format ordered by IDs:

node id: parent = p, depth = d, type, [c1...ck]

p is ID of its parent. If the node does not have a parent, print -1.

d is depth of the node.

type is a type of nodes represented by a string (root, internal node or leaf). If the root can be considered as a leaf or an internal node, print root.

c1...ck is the list of children as a ordered tree.

Please follow the format presented in a sample output below.

Constraints

1 ≤ n ≤ 100000

Sample Input 1

13
0 3 1 4 10
1 2 2 3
2 0
3 0
4 3 5 6 7
5 0
6 0
7 2 8 9
8 0
9 0
10 2 11 12
11 0
12 0

Sample Output 1

node 0: parent = -1, depth = 0, root, [1, 4, 10]
node 1: parent = 0, depth = 1, internal node, [2, 3]
node 2: parent = 1, depth = 2, leaf, []
node 3: parent = 1, depth = 2, leaf, []
node 4: parent = 0, depth = 1, internal node, [5, 6, 7]
node 5: parent = 4, depth = 2, leaf, []
node 6: parent = 4, depth = 2, leaf, []
node 7: parent = 4, depth = 2, internal node, [8, 9]
node 8: parent = 7, depth = 3, leaf, []
node 9: parent = 7, depth = 3, leaf, []
node 10: parent = 0, depth = 1, internal node, [11, 12]
node 11: parent = 10, depth = 2, leaf, []
node 12: parent = 10, depth = 2, leaf, []

Sample Input 2

4
1 3 3 2 0
0 0
3 0
2 0

Sample Output 2

node 0: parent = 1, depth = 1, leaf, []
node 1: parent = -1, depth = 0, root, [3, 2, 0]
node 2: parent = 1, depth = 1, leaf, []
node 3: parent = 1, depth = 1, leaf, []

Note

You can use a left-child, right-sibling representation to implement a tree which has the following data:

the parent of u

the leftmost child of u

the immediate right sibling of u

Template in C

-->

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.



Sample input:
13
0 3 1 4 10
1 2 2 3
2 0
3 0
4 3 5 6 7
5 0
6 0
7 2 8 9
8 0
9 0
10 2 11 12
11 0
12 0


Sample output:
node 0: parent = -1, depth = 0, root, [1, 4, 10]
node 1: parent = 0, depth = 1, internal node, [2, 3]
node 2: parent = 1, depth = 2, leaf, []
node 3: parent = 1, depth = 2, leaf, []
node 4: parent = 0, depth = 1, internal node, [5, 6, 7]
node 5: parent = 4, depth = 2, leaf, []
node 6: parent = 4, depth = 2, leaf, []
node 7: parent = 4, depth = 2, internal node, [8, 9]
node 8: parent = 7, depth = 3, leaf, []
node 9: parent = 7, depth = 3, leaf, []
node 10: parent = 0, depth = 1, internal node, [11, 12]
node 11: parent = 10, depth = 2, leaf, []
node 12: parent = 10, depth = 2, leaf, []

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self):
        self.nodes = {}
    def add_node(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)        
    def add_child(self, parent_id, child_id):
        self.add_node(parent_id)
        self.add_node(child_id)
        self.nodes[parent_id].add_child(self.nodes[child_id])
    
class Node():
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.children = []
        self.depth = 0
        self.nodetype = 'root'

    def add_child(self, child):
        self.children.append(child)
        child.parent = self
        child.update_depth()
        child.update_nodetype()
        self.update_nodetype()
        if self.parent:
            self.parent.update_nodetype()
            
    def update_depth(self):
        depth = self.depth
        if self.parent:
            self.depth = self.parent.depth + 1
        if depth != self.depth:
            for child in self.children:
                child.update_depth()
                
    def update_nodetype(self):
        if self.parent:
            if len(self.children):
                self.nodetype = 'internal node'
            else:
                self.nodetype = 'leaf'
        else:
            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 i in range(n):
    line = input().split()
    id = int(line[0])
    tree.add_node(id)
    for ci in map(int, line[2:]):
        tree.add_child(id, ci)

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

Submission status: Accepted

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):
        assert self.parent == -1
        self.parent = parent

    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_

def set_depth(nodes_, node_id_):
    for child_id_ in nodes_[node_id_].children:
        nodes_[child_id_].depth = nodes_[node_id_].depth + 1
        set_depth(nodes_, child_id_)


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

# set parent and child
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)

root = 0
# find root
if nodes[root].parent != -1:
    for node in nodes:
        if node.parent == -1:
            root = node.id_
            break
    assert root != 0

# set depth
set_depth(nodes, root)

for n in nodes:
    print n

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !
from collections import deque 

class Node:
    def __init__(self):
        self.id = -1
        self.k = -1
        self.depth = -1
        self.parent = -1
        self.type = 'root'
        self.end = False
        self.children = []
        
def find_root_id(nodes):
    i = 0
    rootid = -1
    while nodes[i].parent != -1:
        nodes[i]
        i += 1
    else:
        rootid = nodes[i].id
        return rootid
        
def set_depth(rootid, nodes):
    que = deque()
    depth = 0
    node = nodes[rootid]
    que = deque(node.children)
    for i in que:
        nodes[i].depth = depth + 1
    depth += 1
    
    while que:
        for i in range(len(que)):
            for child in nodes[que.popleft()].children:
                que.append(child)
        for j in que:
            nodes[j].depth = depth + 1
        depth += 1

n = int(raw_input())
nodes = []
for i in range(n):
    node = Node()
    ls =  map(int, raw_input().split())
    node.id = ls[0]
    node.k = ls[1]
    if node.k == 0:
        pass
    else:
        node.children = ls[2:]
    nodes.append(node)
    
nodes = sorted(nodes, key=lambda node:node.id)
for node in nodes:
    for child in node.children:
        nodes[child].parent = node.id
        
for node in nodes:
    if node.children == []:
        if node.parent != -1:
            node.type = 'leaf'
    else:
        if node.parent != -1:
            node.type = 'internal node'

rootid = find_root_id(nodes)
nodes[rootid].depth = 0

def set_depth(rootid, nodes):
    que = deque()
    depth = 0
    node = nodes[rootid]
    que = deque(node.children)
    for i in que:
        nodes[i].depth = depth + 1
    depth += 1
    
    while que:
        for i in range(len(que)):
            for child in nodes[que.popleft()].children:
                que.append(child)
        for j in que:
            nodes[j].depth = depth + 1
        depth += 1

set_depth(rootid, nodes)
for node in nodes:#sorted(nodes, key=lambda node:node.id):
    print 'node %s: parent = %s, depth = %s, %s, %s'%(node.id,
    node.parent, node.depth, node.type, node.children)

Submission status: Accepted

Solution code:
# coding: utf-8
from collections import deque 

class Node:
    def __init__(self):
        self.id = -1
        self.k = -1
        self.depth = -1
        self.parent = -1
        self.type = 'root'
        self.end = False
        self.children = []
        
def find_root_id(nodes):
    i = 0
    rootid = -1
    while nodes[i].parent != -1:
        nodes[i]
        i += 1
    else:
        rootid = nodes[i].id
        return rootid
        
def set_depth(rootid, nodes):
    que = deque()
    depth = 0
    node = nodes[rootid]
    que = deque(node.children)
    for i in que:
        nodes[i].depth = depth + 1
    depth += 1
    
    while que:
        for i in xrange(len(que)):
            for child in nodes[que.popleft()].children:
                que.append(child)
        for j in que:
            nodes[j].depth = depth + 1
        depth += 1

n = int(raw_input())
nodes = []
for i in xrange(n):
    node = Node()
    ls =  map(int, raw_input().split())
    node.id = ls[0]
    node.k = ls[1]
    if node.k == 0:
        pass
    else:
        node.children = ls[2:]
    nodes.append(node)
    
nodes = sorted(nodes, key=lambda node:node.id)
for node in nodes:
    for child in node.children:
        nodes[child].parent = node.id
        
for node in nodes:
    if node.children == []:
        if node.parent != -1:
            node.type = 'leaf'
    else:
        if node.parent != -1:
            node.type = 'internal node'

rootid = find_root_id(nodes)
nodes[rootid].depth = 0
set_depth(rootid, nodes)
for node in nodes:
    print 'node %s: parent = %s, depth = %s, %s, %s'%(node.id, node.parent, node.depth, node.type, node.children)

Submission status: Accepted

Solution code:
from operator import attrgetter
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())
    id = L[0]
    T.append(Node(id, L[2:]))
    for child in T[i].children:
        P[child] = id
T.sort(key=attrgetter('id'))
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: Accepted

Solution code:
#!/usr/bin/env python3

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:
            if node_list[current_id].parent_id == -1:
                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):
        if node.parent_id == -1:
            node_type = "root"
        elif len(node.children) == 0:
            node_type = "leaf"
        else:
            node_type = "internal node"

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

Submission status: Accepted

Solution code:
def Get_leafs_list(T, p):
    l = p.l
    ans = []
    while(T[l].r != -1):
        ans.append(T[l].r)
        l = T[l].r
    return ans

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


class Node():
    def __init__(self,i):
        self.p = -1
        self.l = -1
        self.r = -1
        self.d = 0
        self.n = i

    def Get_leafs_list(self,T):
        l = self.l
        if l != -1:
            ans = [l]
        else:
            ans = []
        while(T[l].r != -1):
            ans.append(T[l].r)
            l = T[l].r
        return ans


    def print_ans(self):
        print("node",self.n, end=": ")
        print("parent =",self.p, end=", ")
        print('depth =',self.d, end=", ")
        if self.l == -1 and self.p != -1:
            print('leaf, []')
            return
        else:
            if self.p == -1:
                print("root",end=", ")
            else :
                print("internal node",end=", ")
            ans = self.Get_leafs_list(T)
            print(ans)
T = []
n = int(input())
for i in range(0,n):
    T.append(Node(i))

for i in range(0,n):
    data = [int(x) for x in input().split()]
    k = data[0]
    if(data[1] != 0):   # node has leafs
        for j in range(0,data[1]):  #leafs
            if j == 0:
                T[k].l = data[2]
            else:
                T[l].r = data[2+j]
            l = data[2+j]
            T[l].p = data[0]
#get root 
for x in range(0,n):
    if(T[x].p == -1):
        root = x
        break
try:
    rec(T,root,0)

except:
    for i in range(1,n):
        T[i].d = 1

for x in T:
    x.print_ans()

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:
class Node:
    def __init__(self, parent, left, right):
        self.parent = parent
        self.left = left
        self.right = right

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

def set_depth(u,d):
    global D
    global tree
    D[u] = d
    v = tree[u].right
    while not v == -1:
        D[v] = d
        if not tree[v].left == -1:
            set_depth(tree[v].left, d+1)
        v = tree[v].right
    if not tree[u].left == -1:
        set_depth(tree[u].left, d+1)

def print_tree(t,D):
    for i in range(len(t)):
        children = []
        c = t[i].left
        if not c == -1:
            while True:
                children.append(c)
                c = t[c].right
                if c == -1: break
        print "node %s: parent = %s, depth = %s, %s, [%s]" % (i, t[i].parent, D[i], t[i].get_type(), ", ".join(map(str, children)))

n = int(raw_input().strip())

tree = {}
for i in range(n):
    tree[i] = Node(-1, -1, -1)
for _ in range(n):
    entry = map(int, raw_input().strip().split(' '))
    nid = entry[0]
    n_child = entry[1]
    for i in range(n_child):
        if i == 0: tree[nid].left = entry[i+2]
        else: tree[entry[i+1]].right = entry[i+2]
        tree[entry[i+2]].parent = nid

r = -1
for i in range(n):
    if tree[i].parent == -1: r = i

D = {}
set_depth(r, 0)

print_tree(tree, D)

Submission status: Accepted

Solution code:
#coding:utf-8
#1_7_A
class Node():
    def __init__(self, node_id, children):
        self.node_id = node_id
        self.parent = -1
        self.depth = 0
        self.typ = "root"
        self.children = children

    def set_child(self, child):
        """ Overwrite child's attribute """
        child.parent = self.node_id
        child.depth = self.depth + 1
        if child.children:
            child.typ = "internal node"
        else:
            child.typ = "leaf"

    def set_children(self, tree):
        """ Repeat set_child starting from root node """
        stack = []
        stack.append(self.node_id)

        while stack:
            node = tree[stack.pop()]
            for child_id in node.children:
                node.set_child(tree[child_id])
            stack.extend(node.children)

n = int(input())
tree = [None for i in range(n)]
children = []
for i in range(n):
    info = list(map(int, input().split()))
    tree[info[0]] = Node(info[0], info[2:])
    children.extend(info[2:])

root_id = list(set([x for x in range(n)]) - set(children)).pop()

tree[root_id].set_children(tree)

for node in tree:
    print("node {}: parent = {}, depth = {}, {}, {}".format(node.node_id, node.parent, node.depth, node.typ, node.children))

Submission status: Accepted

Solution code:
#coding:utf-8
#1_7_A
class Node():
    def __init__(self, node_id, children):
        self.node_id = node_id
        self.parent = -1
        self.depth = 0
        self.typ = "root"
        self.children = children

    def set_child(self, child):
        """ Overwrite child's attribute """
        child.parent = self.node_id
        child.depth = self.depth + 1
        if child.children:
            child.typ = "internal node"
        else:
            child.typ = "leaf"

    def set_children(self, tree):
        """ Repeat set_child starting from root node """
        stack = []
        stack.append(self.node_id)

        while stack:
            node = tree[stack.pop()]
            for child_id in node.children:
                node.set_child(tree[child_id])
            stack.extend(node.children)

n = int(input())
tree = [None for i in range(n)]
children = []
for i in range(n):
    info = list(map(int, input().split()))
    tree[info[0]] = Node(info[0], info[2:])
    children.extend(info[2:])

root_id = (set([x for x in range(n)]) - set(children)).pop()

tree[root_id].set_children(tree)

for node in tree:
    print("node {}: parent = {}, depth = {}, {}, {}".format(node.node_id, node.parent, node.depth, node.typ, node.children))

Submission status: Accepted

Solution code:
n = int(input())
tree = [None] * n
root = set(range(n))


def set_pd(i, parent, depth):
    node = tree[i]
    node[1], node[2] = parent, depth
    for child in node[0]:
        set_pd(child, i, depth + 1)


while n:
    l = list(map(int, input().split()))
    c = l[2:]
    tree[l[0]] = [c, None, None]
    root -= set(c)
    n -= 1

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

for i, node in enumerate(tree):
    c, p, d = node
    print('node {}: parent = {}, depth = {}, {}, [{}]'.format(
        i, p, d, 'root' if not d else 'internal node' if c else 'leaf', ', '.join(map(str, c))
    ))

Submission status: Accepted

Solution code:
#coding:utf-8
#1_7_A
class Node():
    def __init__(self, node_id, degree, children):
        self.node_id    =   node_id
        self.parent     =   -1
        self.depth      =   0
        self.typ        =   "leaf"
        self.degree     =   degree
        self.children   =   children

    def set_attr(self, parent, depth):
        self.parent =   parent
        self.depth  =   depth
        for child_id in self.children:
            self.typ = "internal node"
            tree[child_id].set_attr(self.node_id, self.depth + 1)
        if self.parent == -1:
            self.typ = "root"

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

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

root_id = root.pop()
tree[root_id].set_attr(-1, 0)

for node in tree:
    print("node {}: parent = {}, depth = {}, {}, {}".format(node.node_id, node.parent, node.depth, node.typ, node.children))

Submission status: Accepted

Solution code:
#coding:utf-8
#1_7_A
class Node():
    def __init__(self, node_id, children):
        self.node_id    =   node_id
        self.parent     =   -1
        self.depth      =   0
        self.typ        =   "leaf"
        self.children   =   children

    def set_attr(self, parent, depth):
        self.parent =   parent
        self.depth  =   depth
        for child_id in self.children:
            self.typ = "internal node"
            tree[child_id].set_attr(self.node_id, self.depth + 1)
        if self.parent == -1:
            self.typ = "root"

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

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

root_id = root.pop()
tree[root_id].set_attr(-1, 0)

for node in tree:
    print("node {}: parent = {}, depth = {}, {}, {}".format(node.node_id, node.parent, node.depth, node.typ, node.children))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
 
FORMAT = ('node {0.id}: parent = {0.parent}, depth = {0.depth},'
          ' {0.kind}, {0.childs}').format
 
 
class Node(object):
    def __init__(self, node):
        self.depth = 0
        self.parent = -1
        self.id = node[0]
        self.degree = node[1]
        self.kind = 'internal node' if node[1] else 'leaf'
        self.childs = node[2:]
 
    def __str__(self):
        return FORMAT(self)
 
 
def calc_depth(tree, i):
    for j in tree[i].childs:
        tree[j].depth += 1
        calc_depth(tree, j)
 
 
n = int(stdin.readline())
tree = [-1] * n
#assert 1 <= n <= 100000
for _ in xrange(n):
    node = Node([int(s) for s in stdin.readline().split()])
    i = node.id
    node.parent = tree[i]
    for j in node.childs:
        if isinstance(tree[j], int):
            tree[j] = i
        else:
            tree[j].parent = i
    tree[i] = node
 
for i in xrange(n):
    calc_depth(tree, i)
 
for i, node in enumerate(tree):
    if node.parent == -1:
        node.kind = 'root'
    print(node)

Submission status: Accepted

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


class RootedTree():
    def __init__(self, n):
        self.base_node = Node(-1, None, None, None)
        self.nodes = [Node(i, self.base_node, None, None) for i in range(n)]
    
    def set_node(self, num, k, *children):
        if children:
            self.nodes[num].leftmostChild = self.nodes[children[0]]
            for i, x in enumerate(children[:-1]):
                self.nodes[x].parent = self.nodes[num]
                self.nodes[x].rightSibling = self.nodes[children[i + 1]]
            self.nodes[children[-1]].parent = self.nodes[num]

    def set_depth(self):
        for n in self.nodes:
            t_n = n
            while t_n.parent.id != -1:
                n.depth += 1
                t_n = t_n.parent

    def show_nodes_info(self):
        for n in self.nodes:
            n.show_info()



import sys

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

T = RootedTree(n)

for x in sys.stdin.readlines():
    T.set_node(*list(map(int, x.split())))

T.set_depth()

T.show_nodes_info()

Submission status: Accepted

Solution code:
"""Rooted Trees."""

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


class RootedTree():
    def __init__(self, n):
        self.nodes = [Node(i, -1) for i in range(n)]
    
    def set_node(self, i_p):
        i_p = list(map(int, i_p.split()))
        num = i_p[0]
        children = i_p[2:]
        if children:
            self.nodes[num].children = children
            for n in children:
                self.nodes[n].parent = num

    def set_depth(self):
        for n in self.nodes:
            t_n = n
            while t_n.parent != -1:
                n.depth += 1
                t_n = self.nodes[t_n.parent]

    def show_nodes_info(self):
        for n in self.nodes:
            n.show_info()



import sys

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

T = RootedTree(n)

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

T.set_depth()

T.show_nodes_info()

Submission status: Accepted

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


def set_node(i_p):
    i_p = list(map(int, i_p.split()))
    num = i_p[0]
    children = i_p[2:]
    if children:
        T[num].children = children
        for n in children:
            T[n].parent = num

def find_root(node):
    while node.parent != -1:
        node = T[node.parent]
    return node

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



import sys

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

T = [Node(i, -1) for i in range(n)]

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

r_n = find_root(T[0])

set_depth(r_n, 0)

for n in T:
    n.show_info()

Submission status: Accepted

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


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

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


import sys

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

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

rn_check_list = [i for i in range(n)]

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

rn_i = rn_check_list[0]

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

for n in T:
    n.show_info()