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:
# -*- 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],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: Wrong Answer

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:
        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(id_list[0], 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: Wrong Answer

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:
        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(id_list[0], 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: Wrong Answer

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)

rooted_tree(id_list[0], 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: Wrong Answer

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'
    else:
        out['type'] = 'internal node'
    if len(nodes[ind]) == 0:
        out['type'] = 'leaf'
    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: Wrong Answer

Solution code:
import sys

n = int(input())
ary = [[int(_) for _ in line.strip().split()] for line in sys.stdin]
# ary = [[int(_) for _ in input().split()] for i in range(n)]
ary.sort(key=lambda x: x[0])


def output(i, p, d, t, ch):

    print('node {}: parent = {}, depth = {}, {}, {}'.format(i, p, d, t, ch))


bry = [{
    'id': i,
    'parent': -1,
    'depth': 0,
    'type': 'root',
    'children': []
} for i in range(n)]
for node in ary:
    no = node[0]
    if node[1]:
        for cno in node[2:]:
            bry[no]['children'].append(cno)
            bry[cno]['parent'] = no
            bry[cno]['depth'] = bry[no]['depth'] + 1
            if ary[cno][1]:
                bry[cno]['type'] = 'internal node'
            else:
                bry[cno]['type'] = 'leaf'
    else:
        bry[no]['type'] = 'leaf'

for node in bry:
    output(node['id'], node['parent'], node['depth'], node['type'],
           node['children'])

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
ary = [[int(_) for _ in line.strip().split()] for line in sys.stdin]
ary.sort(key=lambda x: x[0])


def output(i, p, d, t, ch):

    print('node {}: parent = {}, depth = {}, {}, {}'.format(i, p, d, t, ch))


bry = [{
    'id': i,
    'parent': -1,
    'depth': 0,
    'type': 'root',
    'children': []
} for i in range(n)]
for node in ary:
    no = node[0]
    if node[1]:
        for cno in node[2:]:
            bry[no]['children'].append(cno)
            bry[cno]['parent'] = no
            if ary[cno][1]:
                bry[cno]['type'] = 'internal node'
            else:
                bry[cno]['type'] = 'leaf'
    else:
        if n > 0:
            bry[no]['type'] = 'leaf'

tmp = [(node['id'], node['parent']) for node in bry]
root = [min(tmp, key=lambda x: x[1])[0]]
flag = True
while flag:
    flag = False
    tmp = []
    for i in root:
        for cno in bry[i]['children']:
            bry[cno]['depth'] = bry[i]['depth'] + 1
            tmp.append(cno)
            flag = True
    root = tmp

for node in bry:
    output(node['id'], node['parent'], node['depth'], node['type'],
           node['children'])

Submission status: Wrong Answer

Solution code:
#coding:utf-8
n = int(input())
data = [list(map(int, input().split())) for i in range(n)]
ID = 0
parent = -1
depth = 0
sect = data[0][2:]
print("note {}: parent = {}, depth = {}, root, {}".format(ID, parent, depth, sect))

parent = 0
depth = 1

def rootedTrees(ID, parent, depth):
    if data[ID][1] == 0:
        sect = []
        print("note {}: parent = {}, depth = {}, leaf, {}".format(ID, parent, depth, sect))
    else:
        sect = data[ID][2:]
        print("note {}: parent = {}, depth = {}, internal node, {}".format(ID, parent, depth, sect))
        parent = ID
        for i in sect:
            rootedTrees(i, parent, depth+1)

for i in sect:
    rootedTrees(i, parent, depth)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
n = int(input())
data = [list(map(int, input().split())) for i in range(n)]
ID = 0
parent = -1
depth = 0
try:
    sect = data[0][2:]
except:
    sect = []
print("note {}: parent = {}, depth = {}, root, {}".format(ID, parent, depth, sect))

parent = 0
depth = 1

def rootedTrees(ID, parent, depth):
    if data[ID][1] == 0:
        sect = []
        print("note {}: parent = {}, depth = {}, leaf, {}".format(ID, parent, depth, sect))
    else:
        sect = data[ID][2:]
        print("note {}: parent = {}, depth = {}, internal node, {}".format(ID, parent, depth, sect))
        parent = ID
        for i in sect:
            rootedTrees(i, parent, depth+1)

for i in sect:
    rootedTrees(i, parent, depth)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
n = int(input())
data = [list(map(int, input().split())) for i in range(n)]
ID = 0
parent = -1
depth = 0
try:
    sect = data[0][2:]
except:
    sect = []
print("node {}: parent = {}, depth = {}, root, {}".format(ID, parent, depth, sect))

parent = 0
depth = 1

def rootedTrees(ID, parent, depth):
    if data[ID][1] == 0:
        sect = []
        print("node {}: parent = {}, depth = {}, leaf, {}".format(ID, parent, depth, sect))
    else:
        sect = data[ID][2:]
        print("node {}: parent = {}, depth = {}, internal node, {}".format(ID, parent, depth, sect))
        parent = ID
        for i in sect:
            rootedTrees(i, parent, depth+1)

for i in sect:
    rootedTrees(i, parent, depth)

Submission status: Wrong Answer

Solution code:
#coding:utf-8

n = int(input())
T = [list(map(int, input().split())) for i in range(n)]
A = []
def parentSearch():
    numList = []
    for t in T:
        if t[1] != 0:
            for num in t[2:]:
                numList.append(num)
    numList.sort()
    for i in range(n-1):
        if numList[i] != i:
            return i
            break


def rootedTrees(node, parent, depth):
    print(node)
    t = T[node]
    if t[1] != 0:
        if parent == -1:
            kind = "root"
        else:
            kind = "internal node"
        A.append([t[0], parent, depth, kind, t[2:]])
        parent = node
        for i in t[2:]:
            rootedTrees(i, parent, depth+1)
    else:
        if parent == -1:
            kind = "root"
        else:
            kind = "leaf"
        A.append([t[0], parent, depth, kind, []])


def Merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append([510000])
    R.append([510000])
    i,j = 0,0
    for k in range(left,right):
        if L[i][0] <= R[j][0]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def MergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right)//2
        MergeSort(A, left, mid)
        MergeSort(A, mid, right)
        Merge(A, left, mid, right)

node = parentSearch()
if node == None:
    node = 0
depth = 0
parent = -1
rootedTrees(node, parent, depth)
MergeSort(A, 0, n)

for t in A:
    print("node {}: parent = {}, depth = {}, {}, {}".format(t[0],t[1],t[2],t[3],t[4]))

Submission status: Wrong Answer

Solution code:
from typing import List

class Node:
    def __init__(self, node_id, parent_id):
        self.node_id = node_id
        self.parent_id = parent_id
        self.children = []
        
        self.depth = None
        self.node_type =None

    def __str__(self):
        return str(self.node_id)
    def __repr__(self):
        return self.__str__()
        
    
class Tree:
    def __init__(self, n):
        self.root = None
        self.n_node = n
        self.node_list = [None for _ in range(n)]
    
    def find_node(self, node_id: int):
        if self.node_list[node_id] != None:
            return self.node_list[node_id]
        return None
    
    def add_children_from_ids(self, node_id: int, children_ids: List[int]):
        # check parent already exists
        parent_node = self.find_node(node_id)
        if parent_node == None:
            # create new node from parent_id
            parent_node = Node(node_id = node_id, parent_id = -1)
            self.node_list[node_id] = parent_node
            
        if len(children_ids) > 0:
            # add all the children (unregistered)
            # register parent_id, node_id, children
            for child_id in children_ids:
                child_node = self.find_node(child_id)
                
                if child_node == None:
                    child_node = Node(node_id = child_id, parent_id = node_id)
                else:
                    child_node.parent_id = node_id
                    
                parent_node.children.append(child_node)
                self.node_list[child_id] = child_node
    
    def overwrite_node_type(self):
        # find root and overwrite node type
        
        for node in self.node_list:
            # root, internal node, leaf
            if node.parent_id == -1:
                node_type = "root"
                self.root = node
            else:
                if node.children != []:
                    node_type = "internal node"
                else:
                    node_type = "leaf"
                    
            node.node_type = node_type

    def overwrite_depth(self, node, depth):
        if node.children == []:
            node.depth = depth
            # print("node.id: ", node.node_id, ",  node.depth: ", node.depth)
            return None
        else:
            for child_node in node.children:
                self.overwrite_depth(child_node, depth+1)
        return None

    def print_nodes(self):
        for node in self.node_list:
            print("node {}: parent = {}, depth = {}, {}, {}".format(
                node.node_id, node.parent_id, node.depth, node.node_type, node.children
            ))            
  
def main():
    n = int(input())
    tree = Tree(n)
    for _ in range(n):
        node_id, k, *children = map(int, input().split())
        tree.add_children_from_ids(node_id = node_id, children_ids = children)
    tree.overwrite_node_type()

    tree.overwrite_depth(tree.root, 0)
    tree.print_nodes()    
main()

Submission status: Wrong Answer

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 not node[1]:
        kind = 'leaf'
    elif pa == -1:
        kind = 'root'
    else:
        kind = 'internal node'
    print(fmt(i, pa, node[0], kind, node[2:]))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

dali = []

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

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

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

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

Submission status: Time Limit Exceeded

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

dali = [0] * n

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

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

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

Submission status: Time Limit Exceeded

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

Solution code:
n = int(input())
tree = [None] * n
formatted_tree = [None] * n


def register_node(i, node, searching):
    for si, st in enumerate(searching[1]):
        if type(st) is int:
            if st == i:
                searching[1][si] = node
                return True
        else:
            if register_node(i, node, st):
                return True
    return False


def format(node, parent, depth):
    (i, cs) = node
    cis = [format(c, i, depth + 1) for c in cs]
    formatted_tree[i] = 'node {0}: parent = {1}, depth = {2}, {3}, [{4}]'.format(
        i, parent, depth,
        'root' if not depth else 'internal node' if cis else 'leaf',
        ', '.join(cis)
    )
    return str(i)


while n:
    l = list(map(int, input().split()))
    i, c = l[0], l[2:]
    node = (i, c)
    for p in tree:
        if not p:
            continue
        if register_node(i, node, p):
            break
    else:
        tree[i] = node

    for i, ci in enumerate(c):
        if tree[ci]:
            c[i] = tree[ci]
            tree[ci] = None

    n -= 1

format(next(filter(None, tree)), -1, 0)

for fn in formatted_tree:
    print(fn)

Submission status: Time Limit Exceeded

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

class Node_Class():
    def __init__(self, c_list):
        self.c_list = c_list

n = int(raw_input())
node_dic = {}
p_list = [0]*n
d_list = [0]*n
t_list = ['']*n
for i in range(n):
    line = map(str, raw_input().split())
    if int(line[1]) > 0:
        node_dic[int(line[0])] = Node_Class(map(int, line[2:]))
    else:
        node_dic[int(line[0])] = Node_Class([])
#parent
for i in range(n):
    flag = False
    for j in range(n):
        if i in node_dic[j].c_list:
            p_list[i] = j
            flag = True
            break
    if not flag:
        p_list[i] = -1
#depth
for i in range(n):
    j = i
    while p_list[j] > -1:
        j = p_list[j]
        d_list[i] += 1
#type
for i in range(n):
    if p_list[i] == -1:
        t_list[i] = t_list[i] + "root"
    else:
        if len(node_dic[i].c_list):
            t_list[i] = t_list[i] + "internal node"
        else:
            t_list[i] = t_list[i] + "leaf"
#print
for i in range(n):
    s = "node %d: parent = %d, depth = %d, %s," %(i, p_list[i], d_list[i], t_list[i])
    print s, node_dic[i].c_list

Submission status: Time Limit Exceeded

Solution code:
class my_tree:
    def __init__(self):
        self.t = {}
    def addNode(self, i, c=[]):
        self.t[i] = {'parent':-1, 'type': 'root', 'c':c}
        ti = self.t[i]
        for j in self.t.keys():
            tj = self.t[j]
            if j in ti['c'] :
                tj['parent'] = i
                if tj['c']:
                    tj['type'] = 'internal node'
                else:
                    tj['type'] = 'leaf'
            elif i in tj['c']:
                ti['parent'] = j
                if ti['c']:
                    ti['type'] = 'internal node'
                else:
                    ti['type'] = 'leaf'
    def getDepth(self, i):
        p_id = self.t[i]['parent']
        if p_id==-1: return 0
        return self.getDepth(p_id) + 1
    def getParentId(self, i): return self.t[i]['parent']
    def getNodeType(self, i): return self.t[i]['type']
    def getChildren(self, i): return self.t[i]['c']
    def getIdList(self)     : return sorted(self.t.keys())

if __name__=='__main__':
    n = int(input())
    tree = my_tree()
    for _ in range(n):
        node = list(map(int,input().split()))
        i = node[0]
        c = node[2:] if node[1] > 0 else []
        tree.addNode(i,c)
    
    for i in tree.getIdList():        
        print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(\
                i, tree.getParentId(i), tree.getDepth(i), tree.getNodeType(i), tree.getChildren(i)))

Submission status: Time Limit Exceeded

Solution code:
class Tree:
    def __init__(self):
        self.nodes = {}
        self.roots = []

    def add(self, node):
        for i_number in self.roots:
            if i_number in node.degree:
                node.t = "root"
                r = self.nodes[i_number]
                if 0 < len(r.degree):
                    r.t = 'internal node'
                else:
                    r.t = 'leaf'
                r.parent = node.i
                self.roots.remove(i_number)
                self.roots.append(node.i)

        if len(self.nodes) == 0:
            node.t = 'root'
            self.roots.append(node.i)
        elif node.t != 'leaf' and node.t != 'root':
            node.t = 'internal node'

        if node.t != "root":
            for k, n in self.nodes.items():
                if node.i in n.degree:
                    node.parent = n.i

        self.nodes[node.i] = node

    def set_parent(self):
        for n in self.nodes.values():
            for deg in n.degree:
                child = self.nodes[deg]
                child.parent = n.i

    def calc_depth(self):
        for n in self.nodes.values():
            if n.parent == -1:
                continue
            else:
                p = self.nodes[n.i]
                depth = 0
                while not (p.parent == -1):
                    p = self.nodes[p.parent]
                    depth += 1
                n.depth = depth


class Node:
    def __init__(self, i=-1, parent=-1, depth=0, t="n", degree=[]):
        self.i = i
        self.parent = parent
        self.depth = depth
        self.t = t
        self.degree = degree
        if 0 < len(self.degree):
            self.leaf = False
        else:
            self.leaf = True
            self.t = "leaf"

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

n = int(input())
tree = Tree()
for i in range(n):
    A = list(map(int, input().split()))
    node = Node(i=A[0], degree=A[2:])
    tree.add(node)

tree.set_parent()
tree.calc_depth()

for k, node in tree.nodes.items():
    node.show()