Problem:

Rooted Trees

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

Fig. 1

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

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

node ID of u

parent of u

depth of u

node type (root, internal node or leaf)

a list of chidlren of u

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

siblings.

-->

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

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

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

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

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

Fig. 2

Input

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

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

id k c1 c2 ... ck

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

Output

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

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

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

d is depth of the node.

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

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

Please follow the format presented in a sample output below.

Constraints

1 ≤ n ≤ 100000

Sample Input 1

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

Sample Output 1

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

Sample Input 2

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

Sample Output 2

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

Note

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

the parent of u

the leftmost child of u

the immediate right sibling of u

Template in C

-->

Reference

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



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


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

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10 ** 6)

class Tree:
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)]
        self.depth = [0 for _ in range(n)]
        self.children = [[] for _ in range(n)]

    def add(self, x, children):
        self.children[x] = children
        for child in children:
            self.parent[child] = x

    def update(self):
        root = -1
        for node, p in enumerate(self.parent):
            if p == -1:
                root = node
                break
        stack = [root]
        d = 0
        while stack:
            temp = []
            for node in stack:
                self.depth[node] = d
                temp += self.getChildren(node)
            stack = temp
            d += 1
    
    def getParent(self, x):
        return self.parent[x]
    
    def getChildren(self, x):
        return self.children[x]

    def getDepth(self, x):
        return self.depth[x]

    def isRoot(self, x):
        return self.getParent(x) == -1

    def isLeaf(self, x):
        return self.getChildren(x) == []

    def getType(self, x):
        if self.isRoot(x):
            return 'root'
        elif self.isLeaf(x):
            return 'leaf'
        return 'internal node'
    
N = int(input())
t = Tree(N)

for _ in range(N):
    q = list(map(int, input().split()))
    i = q[0]
    k = q[1]
    childs = q[2:]
    t.add(i, childs)

t.update()

for i in range(N):
    print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(i, t.getParent(i), t.getDepth(i), t.getType(i), t.getChildren(i)))

Submission status: Accepted

Solution code:
n = int(input())

class Node:
    def __init__(self, id, k, c):
        self.id = id
        self.k = k
        self.c = c
        self.parent = -1
        self.depth = -1

    def setParent(self, parent):
        self.parent = parent

    def setDepth(self, depth):
        self.depth = depth

    def getId(self):
        return self.id

    def getChildren(self):
        return self.c

    def getParent(self):
        return self.parent

    def getDepth(self):
        return self.depth

    def printInfo(self):
        info = ''
        if self.parent == -1:
            info = 'root'
        elif self.k != 0:
            info = 'internal node'
        else:
            info = 'leaf'
        print("node {}: parent = {}, depth = {}, {}, {}".format(
            self.id, self.parent, self.depth, info, self.c
        ))

nodes = [0] * n

for i in range(n):
    arr = input().split()
    id = int(arr[0])
    k = int(arr[1])
    c = list(map(int, arr[2:]))
    nodes[id] = Node(id, k, c)

for e in nodes:
    for id in e.getChildren():
        nodes[id].setParent(e.getId())

for e in nodes:
    if e.getParent() == -1:
        e.setDepth(0)

for i in range(21):
    for e in nodes:
        if e.getDepth() == i:
            for j in e.getChildren():
                nodes[j].setDepth(i + 1)

for e in nodes:
    e.printInfo()

Submission status: Accepted

Solution code:
def set_info(i, p, d):
    r = T[i]
    r[1], r[2] = p, d
    for c in r[0]:
        set_info(c, i, d+1)


n = int(input())
root = set(range(n))
T = [None] * n

for _ in range(n):
    A = list(map(int, input().split()))
    children = A[2:]
    T[A[0]] = [children, None, None]
    root -= set(children)

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

for i,node in enumerate(T):
    ch, p, d = node
    print('node {}: parent = {}, depth = {}, {}, {}'.format(
            i, p, d, 'root' if not d else 'internal node' if ch else 'leaf', ch
        ))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

nodedict = {}

class Node:
    def __init__(self, id, jisu, children):
        self.id = id
        self.jisu = jisu
        self.children = children
        self.parent = -1
        self.depth = -1

    def __repr__(self):
        return "id:{}, jisu:{}, parent:{}, depth:{}, children:{}".format(self.id, self.jisu, self.parent, self.depth, self.children)

def assign_depth(node, current_depth):
    node.depth = current_depth
    for childid in node.children:
        assign_depth(nodedict[childid], current_depth+1)

def solve():
    n = int(input())

    # Node作成
    for i in range(n):
        input_list = list(map(int, input().split()))
        id = input_list[0]
        jisu = input_list[1]
        children = input_list[2:]
        nodedict[id] = Node(id, jisu, children)

    # 親番号の割り当て
    for i in range(n):
        node = nodedict[i]
        for childid in node.children:
            child = nodedict[childid]
            child.parent = node.id

    #print(nodedict)
    # 根探し
    neid = None
    for i in range(n):
        node = nodedict[i]
        if node.parent == -1:
            neid = node.id
            break

    # 深さを割り当てる
    assign_depth(nodedict[neid], 0)

    # 出力
    for i in range(n):
        node = nodedict[i]
        if node.depth == 0:
            type = "root"
        elif len(node.children) == 0:
            type = "leaf"
        else:
            type = "internal node"

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

solve()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self,id):
        self.id = id
        self.child = []
        self.parent = -1
        self.depth = 0
        self.type = "root"    

n = int(input())
T = [Node(i) for i in range(n)]
for ni in range(n):
    id,  k, *c = [int(i) for i in input().split()]
    T[id].child = c 

#teach parent to each child
for ni in range(n):
    for c in T[ni].child:
        T[c].parent = ni

#teach depth
for ni in range(n):
    i = ni
    cnt = 0
    while T[i].parent != -1:
        i = T[i].parent
        cnt += 1
    T[ni].depth = cnt

#teach node type
for ni in range(n):
    if T[ni].parent == -1:
        T[ni].type = "root"
    elif T[ni].child == []:
        T[ni].type = "leaf"
    else:
        T[ni].type = "internal node"

for ni in range(n):
    print("node "+str(T[ni].id)+": parent = "+str(T[ni].parent)+\
    ", depth = "+str(T[ni].depth)+", "+T[ni].type+", ",end="")
    print(T[ni].child)

Submission status: Accepted

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

def get_depth(u, p):
  D[u] = p
  if result[u].right is not None:
    get_depth(result[u].right, p)
  if result[u].left is not None:
    get_depth(result[u].left, p+1)

def get_depth_1(u, p):
  i = u
  d = 0
  while result[u].parent != -1:
    u = result[u].parent
    d += 1
  D[i] = d

n = int(input())
node  = [list(map(int, input().split())) for _ in range(n)] 
result = [Node() for _ in range(n)]
D = [0 for _ in range(n)]

def initiate(li):
  for l in li:
    n = l[0]
    child_num = l[1]
    child = []
    i = 1
    if child_num != 0:
      child = l[2:]
    for c in child:
      if i == 1:
        result[n].left = c 
        i += 1
      else:
        result[idx].right = c 
      idx = c
      result[c].parent = n

initiate(node)
u = 0
for i in range(n):
  if result[i].parent == -1:
    u = i
for u in range(n):
  get_depth_1(u, 0)
final = []
for i in range(n):
  n = i 
  p = result[i].parent
  d = D[i]
  c = [result[i].left]
  j = result[i].left
  if j is not None:
    while result[j].right is not None:
      c.append(result[j].right)
      j = result[j].right
  final.append([n, p, d, c])
  
for i in range(n+1):
  n, p, d, c = final[i]
  typ = ""
  if p == -1:
    typ = "root"
    if c == [None]:
      c = []
  else:
    if c == [None]:
      typ = "leaf"
      c = []
    else:
      typ = "internal node"
  print("node {}: parent = {}, depth = {}, {}, {}".format(n, p, d, typ, c))

Submission status: Accepted

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

    def addParent(self,parent):
        self.parent = parent

    def addChild(self,child):
        self.child = child

n = int(input())
nodes = {}

for i in range(n):
    line = list(input().split(" "))
    id = int(line[0])
    child = []
    for k in range(int(line[1])):
        childId = int(line[2+k])
        child.append(childId)
        if not childId in nodes:
            nodes[childId] = Node(childId)
        nodes[childId].addParent(id)

    if not id in nodes:
        nodes[id] = Node(id)
    nodes[id].addChild(child)

for i in sorted(nodes):
    node = nodes[i]
    depth = 0
    startNode = node
    while not startNode.parent == -1:
        startNode = nodes[startNode.parent]
        depth += 1

    if node.parent == -1:
        type = "root"
    elif not node.parent == -1 and not node.child == []:
        type = "internal node"
    elif not node.parent == -1 and node.child == []:
        type = "leaf"

    ans = ''
    ans += 'node ' + str(node.id) + ': '
    ans += 'parent = '
    ans += str(node.parent)
    ans += ', depth = ' + str(depth)
    ans += ', ' + type + ', '
    ans += str(node.child)

    print(ans)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self):
        self.id = -1
        self.parent = None
        self.childs = []

    def parentId(self):
        return -1 if self.parent == None else self.parent.id

    def depth(self):
        r = 0
        p = self.parent
        while p != None:
            r += 1
            p = p.parent
        return r

    def type(self):
        if self.parent == None:
            return "root"
        elif len(self.childs) > 0:
            return "internal node"
        return "leaf"

    def childIds(self):
        return [c.id for c in self.childs]


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

for i in range(n):
    id, k, *c, = map(int, input().split())
    p = nodes[id]
    p.id = id
    for v in c:
        p.childs.append(nodes[v])
        nodes[v].parent = p

for node in nodes:
    s = f"node {node.id}: "
    s += f"parent = {node.parentId()}, "
    s += f"depth = {node.depth()}, "
    s += f"{node.type()}, "
    s += f"{node.childIds()}"
    print(s)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, n, parent=None, child=None):
        self.n = n
        self.p = parent
        self.child = child

    @property
    def parent(self):
        return self.p

    @parent.setter
    def parent(self, v):
        self.p = v

    @property
    def depth(self):
        count = 0
        p = self.parent
        while p is not None:
            count += 1
            p = p.parent
        return count

    @property
    def type(self):
        if self.parent is None:
            return "root"
        elif not self.child:
            return "leaf"
        else:
            return "internal node"

    def __str__(self):
        if self.parent is None:
            parent = -1
        else:
            parent = self.parent.n

        return "node {}: parent = {}, depth = {}, {}, {}".format(
            self.n, parent, self.depth, self.type, self.child
        )


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

for i in range(n):
    l = [int(i) for i in input().split()]
    id_ = l[0]
    k = l[1]
    nodes[id_].child = l[2:]
    if k != 0:
        for li in l[2:]:
            nodes[li].parent = nodes[id_]

for n in nodes:
    print(n)

Submission status: Accepted

Solution code:
# coding: utf-8
import queue

class Node:
    def __init__(self, myNum, childNums):
        self.myNum = myNum
        self.parentNum = -1
        self.childNums = childNums
        self.nodeType = ""
        self.depth = -1
        
n = int(input().rstrip())
nodes = []
# 入力を使ってクラスに放り込む
for i in range(n):
    line = [int(i) for i in input().rstrip().split()]
    childNums = [i for i in line[2:]]
    nodes.append(Node(line[0],childNums))
# nodesを節点順にソートする
nodes = sorted(nodes,key=lambda x: x.myNum)
# 親を計算する
for node in nodes:
    for num in node.childNums:
        nodes[num].parentNum = node.myNum

# type を求める
for node in nodes:
    if node.parentNum == -1:
        node.nodeType = "root"
        rootNum = node.myNum
    elif not node.childNums:
        node.nodeType = "leaf"
    else:
        node.nodeType = "internal node"
        
# depth を計算する
q = queue.Queue()
q.put(nodes[rootNum])
nodes[rootNum].depth=0
while not q.empty():
    nd = q.get()
    for c in nd.childNums:
        nodes[c].depth = nd.depth + 1
        q.put(nodes[c])

#アウトプット
for node in nodes:
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(node.myNum,node.parentNum,node.depth,node.nodeType,node.childNums))

Submission status: Accepted

Solution code:
from sys import stdin

class Node:
    def __init__(self):
        self.parent = -1
        self.depth = -1
        self.children = []

class Tree:
    def __init__(self, nodes):
        self.nodes = nodes

        for i in range(self.size()):
            if not self.isLeaf(i):
                for c in self.nodes[i].children:
                    self.nodes[c].parent = i

        for i in range(self.size()):
            self.nodes[i].depth = self.depth(i)

    def depth(self, i):
        n = self.nodes[i]
        if self.isRoot(i):
            return 0
        else:
            return self.depth(n.parent)+1


    def size(self):
        return len(self.nodes)

    def isLeaf(self, i):
        return len(self.nodes[i].children) == 0

    def isRoot(self, i):
        return self.nodes[i].parent == -1

n = int(stdin.readline().rstrip())
nodes = [Node() for _ in range(n)]
for i in range(n):
    l = [int(x) for x in stdin.readline().rstrip().split()]
    if l[1] > 0:
        nodes[l[0]].children.extend(l[2:])

t = Tree(nodes)
for i in range(t.size()):
    l = ["node ", i, ": parent = ", t.nodes[i].parent, ", depth = ", t.nodes[i].depth, ", "]
    if t.isRoot(i):
        l.append("root, ")
    elif t.isLeaf(i):
        l.append("leaf, ")
    else:
        l.append("internal node, ")

    l.append(t.nodes[i].children)
    print(*l, sep="")

Submission status: Accepted

Solution code:
class node:
    parent = -1
    depth = 0

    def __init__(self, no, Children, k):
        self.no = no
        self.Children = Children
        self.numofchild = k
    
    def dfs(self, nodes, d):
        self.depth = d
        for i in range(self.numofchild):
            nodes[self.Children[i]].dfs(nodes, d+1)

head = -1
nodes = []
n = int(input())
for i in range(n):
    temp = node(i, [], 0)
    nodes.append(temp)

for i in range(n):
    temp = list(map(int,input().split()))
    if temp[1] > 0:
        child = temp[2 : 2+temp[1]]
        nodes[temp[0]].Children =child
        for j in range(temp[1]):
            nodes[nodes[temp[0]].Children[j]].parent = temp[0]
    nodes[temp[0]].numofchild = temp[1]

for i in range(n):
    if nodes[i].parent == -1:
        head = i
        break

nodes[head].dfs(nodes, 0)

for i in range(n):
    if nodes[i].parent == -1:
        print("node " + str(i) + ": parent = " + str(nodes[i].parent) + ", depth = " + str(nodes[i].depth) + ", root, [" + ', '.join(map(str, nodes[i].Children)) + "]")
    elif nodes[i].numofchild == 0:
        print("node " + str(i) + ": parent = " + str(nodes[i].parent) + ", depth = " + str(nodes[i].depth) + ", leaf, [" + ', '.join(map(str, nodes[i].Children)) + "]")
    else:
        print("node " + str(i) + ": parent = " + str(nodes[i].parent) + ", depth = " + str(nodes[i].depth) + ", internal node, [" + ', '.join(map(str, nodes[i].Children)) + "]")

Submission status: Accepted

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

"""
・再帰検索を各辺1回通れば良くした版
"""

import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

def upd_dpth(children, depth):
    for i in children:
        nodes[i][1] = depth+1 
        upd_dpth(nodes[i][2], depth+1)

N = INT()

# node: [parent, depth, children]
nodes = [[-1, 0, []] for i in range(N)]

for i in range(N):
    node = LIST()
    # 子の記録
    nodes[node[0]][2].extend(node[2:])
    # 親の更新
    for j in nodes[node[0]][2]:
        nodes[j][0] = node[0]

for i in range(N):
    # 深さの更新
    if nodes[i][0] == -1:
        # 深さを引数に持てばルートから1回回るだけで終わる
        upd_dpth(nodes[i][2], 0)

for i in range(N):
    parent, depth, children = nodes[i]
    if parent == -1:
        _type = 'root'
    elif len(children) == 0:
        _type = 'leaf'
    else:
        _type = 'internal node'
    print('node {node}: parent = {parent}, depth = {depth}, {type}, {children}'.format(
        node=i, parent=parent, depth=depth, type=_type, children=children))

Submission status: Accepted

Solution code:
from typing import List

# id
# k 子の数
# 子のID


class Node:
    node_id = -999
    child = []
    parent = -1
    depth = -999
    node_type = 'Not set'

    def __init__(self, id: int, child: List[int]):
        self.node_id = id
        self.child = child

    def show(self):
        out = f'node {self.node_id}: '
        out += f'parent = {self.parent}, depth = {self.depth}, '
        out += f'{self.node_type}, '
        tmp = ', '.join(map(str, self.child))
        out += f'[{tmp}]'
        print(out)

    def get_value(self):
        return self.node_id


def show(node_list: List[Node]):
    for n in node_list:
        n.show()


def get_parent(node_id: int) -> int:
    return node_list[node_id].parent


def set_depth(node_id: int, depth: int):
    node_list[node_id].depth = depth
    for ch in node_list[node_id].child:
        set_depth(ch, depth + 1)


def set_node_info(node_list: List[Node]):

    # depthを設定する。
    for target in node_list:
        if target.parent == -1:
            set_depth(target.node_id, 0)
            break

    # typeを設定する。
    for target in node_list:
        if target.depth == 0:
            target.node_type = 'root'
        elif target.depth > 0:
            target.node_type = \
                'leaf' if len(target.child) == 0 else 'internal node'
        else:
            raise ValueError()


n = int(input())
node_list = []
for _i in range(n):
    node_list.append(Node(_i, []))

for _i in range(n):
    line = [int(i) for i in input().split()]
    node_id = line[0]
    num = line[1]

    # 親子関係を設定する。
    for i in range(num):
        child_id = line[2 + i]
        node_list[node_id].child.append(child_id)
        node_list[child_id].parent = node_id

set_node_info(node_list)
show(node_list)

Submission status: Accepted

Solution code:
def depth(s):
    for i in ch[s]:
        dep[i] = dep[s]+1
        if len(ch[i]) != 0:
            depth(i)


def parent(t):
    for i in ch[t]:
        par[i] = t
        if len(ch[i]) != 0:
            parent(i)


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


ch = {}
par = {}
dep = {}
kari = []
for i in range(n):
    kari.append(i)
#print(data)

for i in data:
    ch[i[0]] = list(i[2:])
    for j in list(i[2:]):
        kari.remove(j)


r = kari[0]
dep[r] = 0
par[r] = -1
#print(r)
#print(ans)
'''
for i in range(n):
    #print(i[0])
    try:
        par[i] = [k for k, v in ch.items() if i in v][0]
    except:
        par[i] = -1
        dep[i] = 0
        r = i
        '''

depth(r)
parent(r)


for i in range(n):
    if par[i] == -1:
        tmp = 'root'
    elif len(ch[i]) == 0:
        tmp = 'leaf'
    else:
        tmp = 'internal node'
    print('node {}: parent = {}, depth = {}, {}, {}'.format(i, par[i], dep[i], tmp, ch[i]))

#print(ch)
#print(par)
#print(dep)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, parent, lchild, sibling):
        self.parent = parent
        self.lchild = lchild
        self.sibling = sibling
        self.depth = None

    def __repr__(self):
        return "{" + str(self.parent) + " " + str(self.lchild) + " " + str(self.sibling) + "}"

class NodeList:
    def __init__(self,size):
        self.nlist = [Node(None,None,None) for i in range(size)]

    def add(self, id, sibs):
        #print(self)
        self.nlist[id].lchild = sibs[0]
        #print(self)
        for i in range(len(sibs)-1):
            self.nlist[sibs[i]].parent = id
            self.nlist[sibs[i]].sibling = sibs[i+1]
            #print(self)
        self.nlist[sibs[-1]].parent = id

    def calcDepth(self, idx):
        cnt = -1
        while  idx != None:
            #print("depth",self.nlist[idx])
            idx = self.nlist[idx].parent
            cnt += 1
        return cnt

    def getChilds(self, lchild):
        res = []
        while lchild != None:
            #print("childs",self.nlist[lchild])
            res.append(lchild)
            lchild = self.nlist[lchild].sibling
        return res

    def calcStatus(self, node):
        if node.parent == None:
            return "root"
        if node.lchild == None:
            return "leaf"
        return "internal node"

    def print(self):
        for idx, node in enumerate(self.nlist):
            parent = node.parent
            if parent == None:
                parent = -1
            depth = self.calcDepth(idx)
            childs = self.getChilds(node.lchild)
            status = self.calcStatus(node)
            print("node "+str(idx)+": parent = "+str(parent)+", depth = "+str(depth)+", "+str(status)+", "+str(childs))


    def __repr__(self):
        return str(self.nlist)

            


N = int(input())
NL = NodeList(N)

for i in range(N):
    D = list(map(int, input().split()))
    if len(D) is not 2:
        NL.add(D[0], D[2:])
NL.print()

Submission status: Accepted

Solution code:
import sys

n = int(input())
node_list = []

sys.setrecursionlimit(10 ** 8)
for i in range(n):
    node_list.append(list(map(int, sys.stdin.readline().split())))

parents = [-1 for i in range(n)]
right = [None for i in range(n)]
left = [None for i in range(n)]
depth = [None for i in range(n)]


def get_children(num):
    c = left[num]
    r = []
    while c is not None:
        r.append(c)
        c = right[c]
    return r


def set_depth(num, p):
    depth[num] = p
    if right[num] is not None:
        set_depth(right[num], p)
    if left[num] is not None:
        set_depth(left[num], p + 1)


for i in range(n):
    node = node_list[i]
    v = node[0]
    d = node[1]
    for j in range(d):
        if j == 0:
            left[v] = node[2 + j]
        else:
            right[m] = node[2 + j]
        m = node[2 + j]
        parents[node[2 + j]] = v
root = -1
for i in range(n):
    if parents[i] == -1:
        root = i
set_depth(root, 0)
for i in range(n):
    print("node " + str(i) + ":", end=" ")
    print("parent = " + str(parents[i]) + ",", end=" ")
    print("depth = " + str(depth[i]) + ",", end=" ")

    if parents[i] == -1:
        print("root,", end=" ")
    elif left[i] is None:
        print("leaf,", end=" ")
    else:
        print("internal node,", end=" ")
    print(get_children(i))

Submission status: Accepted

Solution code:
import sys

TYPE_ROOT = 0
TYPE_NODE = 1
TYPE_LEAF = 2


class Node:
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.children = []
        self.type = None
        self.depth = 0


def set_depth(node, depth):
    node.depth = depth
    for child in node.children:
        set_depth(child, depth + 1)


nodes = {}


def get_node(id):
    if id in nodes:
        return nodes[id]
    node = Node(id)
    nodes[id] = node
    return node


n = int(sys.stdin.readline())
for _ in range(n):
    id, k, *children = map(int, sys.stdin.readline().split())
    node = get_node(id)
    for cid in children:
        child = get_node(cid)
        child.parent = node
        node.children.append(child)
    node.type = TYPE_NODE if node.children else TYPE_LEAF

root = next(node for node in nodes.values() if not node.parent)
root.type = TYPE_ROOT
set_depth(root, 0)


for _, node in sorted(nodes.items()):
    print('node %d: parent = %d, depth = %d, %s, [%s]' % (
        node.id,
        node.parent.id if node.parent else -1,
        node.depth,
        ['root', 'internal node', 'leaf'][node.type],
        ', '.join(str(child.id) for child in node.children)
    ))

Submission status: Accepted

Solution code:


class node:
    def __init__(self,nodeid):
        self.parent = "" 
        self.child = []
        self.childid = []
        self.depth = 0
        self.parent = -1
        self.parentid = -1
        self.nodeid = nodeid
        self.type = "root"
    def setChild(self,cn):
        self.child.append(cn)
        self.childid.append(cn.nodeid)
        cn.parent = self
        cn.parentid = self.nodeid
        cn.depth = self.depth + 1
        cn.setNodeType()
        self.setNodeType()
        return
    def getDepth(self):
        cnt = 0
        t = self
        while True:
            if (t.parentid == -1 or  cnt > 10):
                break
            t = t.parent
            cnt = cnt + 1
        return cnt

    def getChildCount(self):
        return len(self.child)
    def setNodeType(self):
        if (self.depth == 0):
            self.type = "root"
        else:
            if (len(self.child) == 0 ):
                self.type = "leaf"
            else:
                self.type = "internal node" 
    def getNodeType(self):
        return self.type
    def showNode(self):
        print ('node {}: parent = {}, depth = {}, {}, {}'.format(self.nodeid,self.parentid,self.getDepth(),self.getNodeType(),self.childid))
        return

nl = []
n = int(input())
for i in range(0,n):
    nl.append(node(i))

for i in range(0,n):
    nodeinfo = list (map(int,input().split()))
    for j in nodeinfo[2:]:
        nl[nodeinfo[0]].setChild(nl[j])
for i in range(0,n):
    nl[i].showNode()

Submission status: Accepted

Solution code:
class Node:
    parent = ""
    depth = ""

    def __init__(self, children=[]):
        self.children = children
        if len(children) == 0:
            self.type = 'leaf'
        else:
            self.type = 'internal node'


def add_parent_node_and_depth(nodes, parent_node_no, node_no, depth):
    nodes[node_no].parent = parent_node_no
    nodes[node_no].depth = depth
    for child in nodes[node_no].children:
        add_parent_node_and_depth(nodes, node_no, child, depth+1)
    return


def main():
    n = int(input())
    nodes = {}
    leafs = {}
    for i in range(n):
        node_no, child_num, *children = [int(x) for x in input().split()]
        if child_num == 0:
            leafs[node_no] = Node([])
        else:
            nodes[node_no] = Node(children)

    nodes.update(leafs)
    # search root node no
    node_no = list(leafs.keys())[0]
    while True:
        parent_node_no = [key for key, value in nodes.items() if node_no in value.children]
        if len(parent_node_no) == 0:
            root_node_no = node_no
            nodes[root_node_no].type = 'root'
            break
        node_no = parent_node_no[0]

    # add parent node no and depth to all nodes
    add_parent_node_and_depth(nodes, parent_node_no=-1, node_no=root_node_no, depth=0)

    for i in range(n):
        node = nodes[i]
        print("node {}: parent = {}, depth = {}, {}, [{}]".
              format(str(i), node.parent, node.depth, node.type, ", ".join(map(str, node.children))))

    return


main()