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 -*-


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


if __name__ == '__main__':

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

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

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

    for node in tree:
        if node.parent == -1:
            root = node.id

    setDepth(root, 0)

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

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

Submission status: Wrong Answer

Solution code:
class tree:
    def __init__(self,name,parent):
        self.name = name
        self.parent = parent
        
        
n = int(input())
trees = {str(i):tree(str(i),'-1') for i in range(n)}


for i in range(n):
    s = [i for i in input().split()]
    p = s[0]

    s_t = s[2:]
    for j in range(len(s_t)):
        trees[s_t[j]] = tree(s_t[j],p)

def getDepth(u):
    d = 0
    while trees[u].parent != '-1':
        u = trees[u].parent
        d += 1
    return d

def getChildren(u):
    c = []
    for i in trees.values():
        if i.parent == u:
            c.append(i.name)
    return c

for i in range(n):
    
    par = trees[str(i)].parent
    dep = getDepth(str(i))
    ch = sorted([int(i) for i in getChildren(str(i))])
    
    if par == '-1':sit = 'root'
    elif len(ch) != 0:sit = 'internal node'
    else:sit = 'leaf'
    
    print('node {}: parent = {}, depth = {}, {}, {}'.format(i,par,dep,sit,ch))

Submission status: Wrong Answer

Solution code:
import collections

def search(node, elems, tree, depth):
    elems[node].append(depth)
    if elems[node][0] == -1:
        state = 'root'
    elif not tree[node]:
        state = 'leaf'
    else:
        state = 'internal node'
    elems[node].append(state)
    elems[node].append(tree[node])
    depth += 1
    for c in tree[node]:
        search(c, elems, tree, depth)
    
if __name__ == '__main__':
    n = int(input())
    tree = collections.defaultdict(list)
    elems = collections.defaultdict(list)
    #elems key:id, value: parent, depth, state, children
    parents = list()
    node_list = list()
    for _ in range(n):
        hoge = [int(x) for x in input().split()]
        node_list.append(hoge[0])
        tree[hoge[0]]
        for childs in range(hoge[1]):
            tree[hoge[0]].append(hoge[childs+2])
    
    for key, value in tree.items():
        for v in value:
            elems[v].append(key)
    for node in node_list:
        if not elems[node]:
            parents.append(node)
            elems[node].append(-1)
    
    for p in parents:
        search(p, elems, tree, 0)
        
    for key, value in elems.items():
        print('node {0}: parent = {1[0]}, depth = {1[1]}, {1[2]}, '.format(key, value), end='')
        print (value[-1])

Submission status: Wrong Answer

Solution code:
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t={}
p={}
d={}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in t:print('node',i+':','parent =',p[i]+',','depth =',d[i]+',','root,'if'-1'==p[i]else'internal node,'if t[i]else'leaf,',list(map(int,t[i])))

Submission status: Wrong Answer

Solution code:
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):i=str(i);print(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{' '.join(t[i])}]")

Submission status: Wrong Answer

Solution code:
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join("node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Submission status: Wrong Answer

Solution code:
class Vertex:
    _id = -1
    _children = []
    _parent = -1
    _depth = 0
    _type = "root"

    def __init__(self, i, c):
        self._id = i
        self._children = c

    def getId(self):
        return self._id

    def getChildren(self):
        return self._children

    def getParent(self):
        return self._parent

    def getDepth(self):
        return self._depth

    def getType(self):
        return self._type

    def setParent(self, p):
        self._parent = p

    def setDepth(self, d):
        self._depth = d

    def setType(self, t):
        self._type = t

    def print(self):
        print("node {}: parent = {}, depth = {}, {}, {}".format(self._id, self._parent, self._depth, self._type, self._children))


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

# 節点
for i in range(n):
    u = list(map(int, input().split(' ')))
    tree[u[0]] = Vertex(u[0], u[2:u[1]+2])

# 親を設定
for w in tree:
    for c in w.getChildren():
        tree[c].setParent(w.getId())
        tree[c].setType("internal node")

# 葉を判定
for w in tree:
    if w.getChildren() == []:
        w.setType("leaf")

# DFS
def dfs(v, depth):
    v.setDepth(depth)
    for child in v.getChildren():
        dfs(tree[child], depth+1)

# 根を探す
root = tree[0]
for w in tree:
    if w.getType() == "root":
        root = w

dfs(root, 0)

# 回答を出力
for w in tree:
    w.print()

Submission status: Wrong Answer

Solution code:
NIL = -1

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

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

for i in range(n):
    tmp = list(map(int, input().split()))
    id = tmp.pop(0)
    k = tmp.pop(0)
    c = tmp
    if k != 0:
        for j in c:
            t[j].parent = id
        t[id].left = c[0]
        for j in range(len(c)-1):
            t[c[j]].right = c[j+1]

def getdepth(u):
    d = 0
    while t[u].parent != NIL:
        u = t[u].parent
        d += 1
    return d

def getchildren(u):
    c = t[u].left
    result = []
    while c != NIL:
        result.append(c)
        c = t[c].right
    return result

for i in range(n):
    d = getdepth(i)
    c = getchildren(i)
    if d == 0:
        v = "root"
    elif c == []:
        v = "leaf"
    else:
        v = "internal node"
print('node {}: parent = {}, depth = {}, {}, [{}]'.format(i, t[i].parent, d, v, ', '.join(map(str, c))))

Submission status: Wrong Answer

Solution code:

class TreeNode:
    def __init__(self, nodeid, children=[]):
        self.nodeid = nodeid
        self.parent = None
        self.sibling = None
        self.child = None
        self.depth = 0

        self.add_children(children)

    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):
        return [c.nodeid for c in self.children()]

    def sibling_nodeids(self):
        return [c.nodeid for c in self.siblings()]

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

    def siblings(self):
        s = self.sibling
        while s is not None:
            yield s
            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_children(self, cs):
        if len(cs) > 0:
            c, *rest = cs
            self.child = self.__class__(c)
            self.child.parent = self
            self.child.add_siblings(rest)

    def add_siblings(self, ss):
        node = self
        for sid in ss:
            node.sibling = self.__class__(sid)
            node.sibling.parent = self.parent
            node = node.sibling

    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()])))


def run():
    c = int(input())
    nodes = {}

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

        if nodeid not in nodes:
            node = TreeNode(nodeid, cs)
            nodes[nodeid] = node
        else:
            node = nodes[nodeid]
            node.add_children(cs)

        for n in node.children():
            nodes[n.nodeid] = n

    for n in [nodes[node] for node in sorted(nodes.keys())]:
        print(n)


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

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):
        if self.child is not None:
            yield self.child.nodeid
            yield from self.child.sibling_nodeids()

    def sibling_nodeids(self):
        siblings = []
        s = self.sibling
        while s is not None:
            siblings.append(s.nodeid)
            s = s.sibling
        for sid in sorted(siblings):
            yield sid

    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):
        node.parent = self.parent
        node.sibling = self.sibling
        self.sibling = node

    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: Wrong Answer

Solution code:
def rec_function(i, p):
    node_info[i]['depth'] = p

    if node_info[i]['parent'] == None:
        node_info[i]['type'] = 'root'
    elif node_info[i]['left'] == None:
        node_info[i]['type'] = 'leaf'
    else:
        node_info[i]['type'] = 'internal node'

    if node_info[i]['right'] != None:
        rec_function(node_info[i]['right'],  p)
    if node_info[i]['left'] != None:
        rec_function(node_info[i]['left'], p + 1)


n = int(input())
node_info = [ { 
    'parent': None,
    'right': None,
    'left': None,
    'depth': None,
    'type': None,
    'children': [],
} for _ in range(n) ]

for _ in range(n):
    input_info = list(map(int, input().split()))
    node = input_info[0]
    children = input_info[2:]
    
    node_info[node]['children'] = children

    if len(children) > 0:
        node_info[node]['left'] = children[0] 

    for i in range(len(children)):
        node_info[children[i]]['parent'] = node
        if i < len(children) - 1:
            node_info[children[i]]['right'] = children[i+1]

root_node = 0

for i in range(len(node_info)):
    if node_info[i]['parent'] == None:
        node_info[i]['parent'] = -1
        root_node = i
        break

rec_function(root_node, 0)

for i in range(len(node_info)):
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(
        i,
        node_info[i]['parent'],
        node_info[i]['depth'],
        node_info[i]['type'],
        node_info[i]['children']
    ))

Submission status: Wrong Answer

Solution code:
from enum import Enum, auto

class NodeType(Enum):
    LEAF = auto()
    INTERNAL_NODE = auto()
    ROOT = auto()

class Node():
    def __init__(self, parent=None, left=None, right=None, depth=None, nodetype=None):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
        self.nodetype = nodetype

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

for i in range(n):
    arr = list(map(int, input().split(' ')))
    if arr[1] == 0:
        nodes[arr[0]].nodetype = NodeType.LEAF
        continue
    id, k, c = arr[0], arr[1], arr[2:]
    nodes[id].nodetype = NodeType.INTERNAL_NODE
    nodes[id].left = c[0]
    for j in range(k-1):
        nodes[c[j]].right = c[j+1]
        nodes[c[j]].parent = id
    nodes[c[k-1]].parent = id

root = 0
for i in range(n):
    if nodes[i].parent == None:
        root = i
        nodes[i].nodetype = NodeType.ROOT

# 深さの探索
# h < 20 なので再帰的にたどっても良い
def rec(u, d):
    nodes[u].depth = d
    if nodes[u].right != None: rec(nodes[u].right, d)
    if nodes[u].left != None: rec(nodes[u].left, d+1)

rec(root, 0)

for i in range(n):
    if nodes[i].nodetype == NodeType.LEAF:
        print('node %d: parent = %d, depth = %d, leaf, []'%(i, nodes[i].parent, nodes[i].depth))

    c = nodes[i].left
    child_list = []
    while c:
        child_list.append(c)
        c = nodes[c].right

    if nodes[i].nodetype == NodeType.ROOT:
        print('node %d: parent = -1, depth = 0, root,'%(i), child_list)
    elif nodes[i].nodetype == NodeType.INTERNAL_NODE:
        print('node %d: parent = %d, depth = %d, internal node,'%(i, nodes[i].parent, nodes[i].depth), child_list)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

class Node():
    def __init__(self, p=None, l=None, r=None):
        self.parent = p
        self.left = l
        self.right = r
        self.depth = None

n = int(input())
nodes = [Node() for i in range(n)]
for i in range(n):
    id, k, *c = list(map(int, input().split(' ')))
    if k == 0: continue
    nodes[id].left = c[0]
    nodes[c[0]].parent = id
    for j in range(1, k):
        nodes[c[j-1]].right = c[j]
        nodes[c[j]].parent = id

root = None
for i in range(n):
    if nodes[i].parent == None:
        root = i

def get_childs(i):
    if nodes[i].left == None: return []
    j = 0
    childs = [nodes[i].left]
    while nodes[childs[j]].right != None:
        childs.append(nodes[childs[j]].right)
        j += 1
    return childs

def set_depth(s, d):
    nodes[s].depth = d
    if nodes[s].right != None:
        set_depth(nodes[s].right, d)
    if nodes[s].left != None:
        set_depth(nodes[s].left, d+1)

set_depth(root, 0)

for i in range(n):
    nodetype = 'internal node'
    parent = nodes[i].parent
    if parent == None:
        parent = -1
        nodetype = 'root'
    childs = get_childs(i)
    if childs == []:
        nodetype = 'leaf'
    print('node ' + str(i) + ': parent = ' + str(parent) + ', depth = ' + str(nodes[i].depth) + ', ' + nodetype + ', ' + str(childs))

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000)

class Node():
    def __init__(self, p=None, l=None, r=None):
        self.parent = p
        self.left = l
        self.right = r
        self.depth = None

n = int(input())
nodes = [Node() for i in range(n)]
for i in range(n):
    id, k, *c = list(map(int, input().split(' ')))
    if k == 0: continue
    nodes[id].left = c[0]
    nodes[c[0]].parent = id
    for j in range(1, k):
        nodes[c[j-1]].right = c[j]
        nodes[c[j]].parent = id

root = None
for i in range(n):
    if nodes[i].parent == None:
        root = i

def get_childs(i):
    if nodes[i].left == None: return []
    j = 0
    childs = [nodes[i].left]
    while nodes[childs[j]].right != None:
        childs.append(nodes[childs[j]].right)
        j += 1
    return childs

# 再帰だと segmentation faultが発生する
# while で実装

def set_depth(s):
    nodes[s].depth = 0
    if nodes[s].left == None: return []
    queue = deque([nodes[s].left])
    while len(queue) > 0:
        u = queue.popleft()
        par_depth = nodes[u].depth
        next_child = nodes[u].left
        while next_child != None:
            nodes[next_child].depth = par_depth + 1
            queue.append(next_child)
            next_child = nodes[next_child.right]

print('start: set_depth')
set_depth(root)
print('end: set_depth')

for i in range(n):
    nodetype = 'internal node'
    childs = get_childs(i)
    if childs == []:
        nodetype = 'leaf'
    parent = nodes[i].parent
    if parent == None:
        parent = -1
        nodetype = 'root'
    print('node ' + str(i) + ': parent = ' + str(parent) + ', depth = ' + str(nodes[i].depth) + ', ' + nodetype + ', ' + str(childs))

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000)

class Node():
    def __init__(self, p=None, l=None, r=None):
        self.parent = p
        self.left = l
        self.right = r
        self.depth = None

n = int(input())
nodes = [Node() for i in range(n)]
for i in range(n):
    id, k, *c = list(map(int, input().split(' ')))
    if k == 0: continue
    nodes[id].left = c[0]
    nodes[c[0]].parent = id
    for j in range(1, k):
        nodes[c[j-1]].right = c[j]
        nodes[c[j]].parent = id

root = None
for i in range(n):
    if nodes[i].parent == None:
        root = i

def get_childs(i):
    if nodes[i].left == None: return []
    j = 0
    childs = [nodes[i].left]
    while nodes[childs[j]].right != None:
        childs.append(nodes[childs[j]].right)
        j += 1
    return childs

# 再帰だと segmentation faultが発生する
# while で実装

def set_depth(s):
    nodes[s].depth = 0
    if nodes[s].left == None: return []
    queue = deque([nodes[s].left])
    while len(queue) > 0:
        u = queue.popleft()
        par_depth = nodes[u].depth
        next_child = nodes[u].left
        while next_child != None:
            nodes[next_child].depth = par_depth + 1
            queue.append(next_child)
            next_child = nodes[next_child.right]

set_depth(root)

for i in range(n):
    nodetype = 'internal node'
    childs = get_childs(i)
    if childs == []:
        nodetype = 'leaf'
    parent = nodes[i].parent
    if parent == None:
        parent = -1
        nodetype = 'root'
    print('node ' + str(i) + ': parent = ' + str(parent) + ', depth = ' + str(nodes[i].depth) + ', ' + nodetype + ', ' + str(childs))

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000)

class Node():
    def __init__(self, p=None, l=None, r=None):
        self.parent = p
        self.left = l
        self.right = r
        self.depth = None

n = int(input())
nodes = [Node() for i in range(n)]
for i in range(n):
    id, k, *c = list(map(int, input().split(' ')))
    if k == 0: continue
    nodes[id].left = c[0]
    nodes[c[0]].parent = id
    for j in range(1, k):
        nodes[c[j-1]].right = c[j]
        nodes[c[j]].parent = id

root = None
for i in range(n):
    if nodes[i].parent == None:
        root = i

def get_childs(i):
    if nodes[i].left == None: return []
    j = 0
    childs = [nodes[i].left]
    while nodes[childs[j]].right != None:
        childs.append(nodes[childs[j]].right)
        j += 1
    return childs

# 再帰だと segmentation faultが発生する
# while で実装

def set_depth(s):
    nodes[s].depth = 0
    queue = deque([s])
    while len(queue) > 0:
        u = queue.popleft()
        print(u)
        par_depth = nodes[u].depth
        next_child = nodes[u].left
        while next_child != None:
            nodes[next_child].depth = par_depth + 1
            queue.append(next_child)
            next_child = nodes[next_child].right

set_depth(root)

for i in range(n):
    nodetype = 'internal node'
    childs = get_childs(i)
    if childs == []:
        nodetype = 'leaf'
    parent = nodes[i].parent
    if parent == None:
        parent = -1
        nodetype = 'root'
    print('node ' + str(i) + ': parent = ' + str(parent) + ', depth = ' + str(nodes[i].depth) + ', ' + nodetype + ', ' + str(childs))

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 = []
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):
#    d = 0
#    u = i
#    while parent[u] != -1:
#        u = parent[u]
#        d += 1
#    return d
    return depth[i]
    
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: 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 = []
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):
#    d = 0
#    u = i
#    while parent[u] != -1:
#        u = parent[u]
#        d += 1
#    return d
    return depth[i]
    
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: 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 = []
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):
#    d = 0
#    u = i
#    while parent[u] != -1:
#        u = parent[u]
#        d += 1
#    return d
    return depth[i]
    
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))
    set_depth(0,0)
    
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)