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:
class Node:
    def __init__(self):
        self.p = None
        self.depth = None
        self.l = None
        self.r = None

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

    def degree(self, T):
        if self.l != None:
            deg = [self.l]
            ch = T[self.l]
            while ch.r != None:
                deg.append(ch.r)
                ch = T[ch.r]
            return deg
        else:
            return []

    def t(self):
        if self.p == -1:
            return 'root'
        elif self.l == None:
            return 'leaf'
        else:
            return 'internal node'

def set_depth(root, d):
    r = T[root]
    r.depth = d
    if r.r != None:
        set_depth(r.r, d)
    if r.l != None:
        set_depth(r.l, d+1)

n = int(input())

T = [Node() for x in range(n)]
for i in range(n):
    A = list(map(int, input().split()))
    l = 0
    for x in range(A[1]):
        if x == 0:
            T[A[0]].l = A[2:][x]
        else:
            T[l].r = A[2:][x]
        l = A[2:][x]
        T[A[2:][x]].p = A[0]

root = None
for i in range(n):
    if T[i].p == None:
        root = i
        T[root].p = -1

set_depth(root, 0)

count = 0
for node in T:
    node.show(count)
    count += 1

Submission status: Time Limit Exceeded

Solution code:
#coding:UTF-8
def depth(leaf,A,d):
    for i in range(len(A)):
        if len(A[i][2])>0 and leaf in A[i][2]:
            return depth(A[i][0],A,d+1)
    return d

def RT(A,n):
    for i in range(n):
        p=0
        d=0
        t=""
        c="["
        if A[i][1]==0 and n>1:
            t="leaf"
            d=depth(A[i][0],A,d)
            for j in range(len(A)):
                if A[i][0] in A[j][2]:
                    p=A[j][0]
                    break
        else:
            d=depth(A[i][0],A,d)
            if d==0:
                p=-1
                t="root"
            else:
                for j in range(len(A)):
                    if A[i][0] in A[j][2]:
                        p=A[j][0]
                        t="internal node"
                        break
        if len(A[i][2])==0:
            c="[]"
        else:
            for j in range(len(A[i][2])):
                if j==len(A[i][2])-1:
                    c+=str(A[i][2][j])+"]"
                else:
                    c+=str(A[i][2][j])+", "
        print("node "+str(A[i][0])+": parent = "+str(p)+", depth = "+str(d)+", "+t+", "+c)

if __name__=="__main__":
    n=int(input())
    A=[]
    for i in range(n):
        a=[]
        A.append(list(map(int,input().split(" "))))
        if len(A[i])==2:
            A[i].append(a)
        else:
            for j in range(len(A[i])-2):
                a.append(A[i][j+2])
            del A[i][2:]
            A[i].append(a)  
    for i in range(n):
        minj=i
        for j in range(i,n):
            if A[j][0]<A[minj][0]:
                minj=j
        A[i],A[minj]=A[minj],A[i]
    RT(A,n)

Submission status: Time Limit Exceeded

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_A&lang=jp
class RootedTree:
    def __init__(self):
        self.id = None
        self.child = []
        self.parent = -1
        self.node_type = "root"
        self.depth = 0

    def show(self):
        print("node {}: parent = {}, depth = {}, {}, {}".format(self.id, self.parent, self.depth, self.node_type, self.child))

def cal_depth(tree, node, cur_depth):
    node.depth += cur_depth
    #node.show()
    for index in node.child:
        cal_depth(tree, tree[index], cur_depth + 1)
        
def make_tree(tree_data):
    tree = [RootedTree() for i in range(len(tree_data))]
    
    for data in tree_data:
        focus = tree[data[0]]
        focus.id = data[0]
        if data[2:]:
            focus.child = data[2:]
            
            for child_index in data[2:]:
                tree[child_index].parent = data[0]
                
                if tree_data[[a[0] for a in tree_data].index(child_index)][2:]:
                    tree[child_index].node_type = "internal node"
                else:
                    tree[child_index].node_type = "leaf"

    root_index = [n.node_type for n in tree].index("root")
    cal_depth(tree, tree[root_index], 0)
    return tree
    
def main():
    n_trees = int(input())
    tree_data = [[int(a) for a in input().split()] for i in range(n_trees)]
    
    for n in make_tree(tree_data):
        n.show()
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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



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


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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8

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

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

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

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

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

for node in node_list:
    print("node {}: parent = {}, depth = {}, {}, {}".format(node.id, node.parent, node.depth, node.type, node.children))

Submission status: Time Limit Exceeded

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

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



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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
tree = {n:{} for n in range(N)}
children = set()

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

parent = set([n for n in range(N)]).difference(children).pop()
tree[parent]["depth"] = 0
tree[parent]["parent"] = -1

siblings = tree[parent]["leaf"]
for c in siblings:
    tree[c]["depth"] = 1
    tree[c]["parent"] = parent

depth = 2
while len(children):
    children = children.difference(siblings)
    next_gen = []
    for s in siblings:
        next_gen.extend(tree[s]["leaf"])
        for c in tree[s]["leaf"]:
            tree[c]["depth"] = depth
            tree[c]["parent"] = s
    siblings = next_gen
    depth += 1

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

Submission status: Time Limit Exceeded

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

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

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

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


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

Submission status: Time Limit Exceeded

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

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


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


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

Submission status: Time Limit Exceeded

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

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


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


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

Submission status: Time Limit Exceeded

Solution code:
class Tree:
    nodes = []
    def __init__(self, root = None):
        self.root = root
    def insert(self, label, children = []):
        self.nodes.append(Node(label, children))
    def search_label(self, label):
        for i in self.nodes:
            if i.label == label:
                return i
    def find_parent(self):
        for i in self.nodes:
            if i.children != []:
                for k in i.children:
                    self.search_label(k).parent = i.label
    def distribute_type(self):
        for i in self.nodes:
            if i.parent != -1:
                if i.children == []:
                    i.type_ = "leaf"
                else:
                    i.type_ = "internal node"
    def distribute_depth(self, node):
        if node.children == []:
            return
        for i in node.children:
            x = self.search_label(i)
            x.depth += node.depth + 1
            self.distribute_depth(x)

class Node:
# type_は0:root, 1:internal node, 2:leaf
    def __init__(self, label, children = []):
        self.label = label
        self.type_ = "root"
        self.depth = 0
        self.parent = -1
        self.children = children


tree = Tree()
n = int(input())
for i in range(n):
    a = list(map(int, input().split()))
    label = a[0]
    if a[1] > 0:
        children = a[2:]
        tree.insert(label, children)
    else:
        tree.insert(label)
tree.find_parent()
tree.distribute_type()
tree.nodes.sort(key = lambda x: x.label)
for i in tree.nodes:
    if i.type_ == "root":
        tree.distribute_depth(i)
for i in tree.nodes:
    print("node {0:}: parent = {1:}, depth = {2:}, {3:}, {4:}".format(i.label, i.parent, i.depth, i.type_, i.children))

Submission status: Time Limit Exceeded

Solution code:
class TreeNode:
    def __init__(self, nodeid):
        self.nodeid = nodeid
        self.parent = None
        self.sibling = None
        self.child = None
        self.depth = 0

    def node_type(self):
        if self.parent is None:
            return 'root'
        elif self.child is None:
            return 'leaf'
        else:
            return 'internal node'

    def parent_nodeid(self):
        if self.parent is None:
            return -1
        else:
            return self.parent.nodeid

    def child_nodeids(self):
        c = self.child
        while c is not None:
            yield c.nodeid
            c = c.sibling

    def sibling_nodeids(self):
        s = self.sibling
        while s is not None:
            yield s.nodeid
            s = s.sibling

    def get_depth(self):
        if self.node_type() != 'root' and self.depth == 0:
            self.depth = self.parent.get_depth() + 1

        return self.depth

    def add_child(self, node):
        if self.child is None:
            self.child = node
            self.child.parent = self
        else:
            self.child.add_sibling(node)

    def add_sibling(self, node):
        s = self
        while s.sibling is not None:
            s = s.sibling

        s.sibling = node
        s.sibling.parent = self.parent

    def __str__(self):
        return ('node {}: parent = {}, depth = {}, {}, [{}]'.format(
                self.nodeid, self.parent_nodeid(), self.get_depth(),
                self.node_type(),
                ", ".join([str(i) for i in self.child_nodeids()])))


class Tree:
    def __init__(self):
        self.nodes = {}

    def node(self, nodeid):
        if nodeid not in self.nodes:
            self.nodes[nodeid] = TreeNode(nodeid)

        return self.nodes[nodeid]

    def sorted_nodes(self):
        for nodeid in sorted(self.nodes.keys()):
            yield self.nodes[nodeid]


def run():
    c = int(input())
    tree = Tree()

    for _ in range(c):
        nodeid, deg, *cs = [int(i) for i in input().split()]
        node = tree.node(nodeid)
        for c in cs:
            node.add_child(tree.node(c))

    for node in tree.sorted_nodes():
        print(node)


if __name__ == '__main__':
    run()

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 = []
child =[[] 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 get_right(i):
    for j in range(n):
        if i in child[j]:
           ind = child[j].index(i)
           if len(child[j]) > ind+1:
               return child[j][ind+1]
           else:
               return None
           
def get_depth(i):
    d = 0
    u = i
    while parent[u] != -1:
        u = parent[u]
        d += 1
    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))
    right.append(get_right(i))
    
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 = []
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 get_right(i):
    for j in range(n):
        if i in child[j]:
           ind = child[j].index(i)
           if len(child[j]) > ind+1:
               return child[j][ind+1]
           else:
               return None
    
def set_depth(i, p):
    global depth
    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))
    right.append(get_right(i))
    
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 = []
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 get_right(i):
    for j in range(n):
        try:
           ind = child[j].index(i)
           if len(child[j]) > ind+1:
               return child[j][ind+1]
           else:
               return None
        except:
           continue 
    
def set_depth(i, p):
    global depth
    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))
    right.append(get_right(i))
    
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 = []
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 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
    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))
    right.append(get_right(i))
    
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:
                right[k] = child[j][i+1]


#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
    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
    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)