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:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    from collections import defaultdict

    NIL = -1

    n = int(input())

    # pythonは構造体を用意するのに手間取るので、辞書型を使う
    # 本の40行目はpythonならdefaultdictで実装可能
    T = defaultdict(lambda: {'p':NIL, 'l':NIL, 'r':NIL})
    D = {}

    # 入力の受け取りは本と若干異なります
    for _ in range(n):
        id, k, *cc = map(int, input().split())
        if k != 0:
            T[id]['l'] = cc[0]
        else:
            T[id]['l'] = NIL
        r = NIL
        for c in cc[::-1]:
            T[c]['p'] = id
            T[c]['r'] = r
            r = c

    # 再帰的に深さを求める
    # 本と同様のコードのすると
    # 再帰回数のエラー(maximum recursion depth exceeded in comparison)
    # が生じるため、自分の子供全てに対して自分の深さ+1することにして解決
    def rec(u, p):
        D[u] = p
        l = T[u]['l']
        while l != NIL:
            rec(l, p+1) # 自分の子に自分の深さ+1を設定
            l = T[l]['r']

    for i, value in T.items():
        if value['p'] == NIL:
            r = i
            break  # breakがなくても問題ないが、余計な計算をしないようにするためつけた

    rec(r, 0)

    def print_children(u):
        c = T[u]['l']
        i = 0
        while c != NIL:
            if i == 0:
                i = 1
            else:
                print(', ', end='')
            print(str(c), end='')
            c = T[c]['r']

    for u in range(n):
        value = T[u]
        print('node ' + str(u) + ': ', end='')
        print('parent = ' + str(value['p']) + ', ', end='')
        print('depth = ' + str(D[u]) + ', ',end='')
        if value['p'] == NIL:
            type = 'root'
        elif value['l'] == NIL:
            type = 'leaf'
        else:
            type = 'internal node'
        print(type + ', ', end = '')
        print('[',end = '')
        print_children(u)
        print(']')

Submission status: Accepted

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

class Node:
    def __init__(self):
        self.parent = -1
        self.left_child = None
        self.right_sibling = None

def get_children(node):
    c = node.left_child
    cs = []
    if c is not None:
        cs.append(c)
        c = nodes[int(node.left_child)]
        while c.right_sibling:
            c = c.right_sibling
            cs.append(c)
            c = nodes[int(c)]
    return cs

# def get_depth(index):
#     depth = 0
#     index = int(index)
#     while index:
#         index = int(nodes[index].parent)
#         depth += 1
#     return depth

def set_depth(i, depth):
    if depths[i] or i >= n:
        return
    depths[i] = depth
    node = nodes[i]
    if node.right_sibling:
        set_depth(int(node.right_sibling), depth)
    if node.left_child:
        set_depth(int(node.left_child), depth+1)

def get_root_index():
    for i, node in enumerate(nodes):
        if node.parent == -1:
            return i
            
def get_kind_of_tree(node):
    if node.parent == -1:
        return "root"
    if node.left_child:
        return "internal node"
    return "leaf"

if __name__ == "__main__":
    n = int(input())
    nodes = [Node() for _ in range(n)]
    depths = [None for _ in range(n)]
    for _ in range(n):
        data, number_of_children, *children = input().split()
        node = nodes[int(data)]
        for i, child_data in enumerate(children):
            if i == 0:
                node.left_child = child_data
            else:
                child.right_sibling = child_data
            child = nodes[int(child_data)]
            child.parent = int(data)
    root_node_index = get_root_index()
    set_depth(root_node_index, 0)
    for i, node in enumerate(nodes):
        children = get_children(node)
        print("node {}: parent = {}, depth = {}, {}, [{}]".format(i, node.parent, depths[i], get_kind_of_tree(node), ', '.join(children)))

Submission status: Accepted

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

#ノードの深さを求める関数
def getdepth(node,node_id):
    d = 0
    while node[node_id].parent != -1:
        node_id = node[node_id].parent
        d += 1
    return d

#子のリストを求める関数
def getchild(node,node_id):
    if node[node_id].left == -1:
        return []
    ret = [node[node_id].left]
    while node[ret[-1]].right != -1:
        ret.append(node[ret[-1]].right)
    return ret

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

#入力を木構造に入力する
for i in range(N):
    n,k,*child = map(int,input().split())
    if k != 0:
        nodes[n].left = child[0]
        for j in range(len(child)):
            nodes[child[j]].parent = n
            if j != len(child)-1:
                nodes[child[j]].right = child[j+1]

for i in range(N):
    depth = getdepth(nodes,i)
    children = getchild(nodes,i)
    if nodes[i].parent == -1:
        node_type = 'root'
    elif nodes[i].left == -1:
        node_type = 'leaf'
    else:
        node_type = 'internal node'
    print('node {}: parent = {}, depth = {}, {}, {}'.format(i,nodes[i].parent, depth, node_type, children))

Submission status: Accepted

Solution code:
# Rooted Trees

import sys
sys.setrecursionlimit(2**20)  # 再帰回数上限の向上 かなり多くしないとREになる

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

def get_depth(T: dict, u: int):
    d = 0
    while T[u].parent is not None:
        u = T[u].parent
        d += 1
    return d

D = {}  # 深さを保存しておく用のdict

def get_all_depth(T: dict, u: int, p: int):
    '''  
    一度にすべてのノードの深さを取得する関数(再帰的に処理を行う)。
    一気に全体の深さを求めるならばこちらの方がオーダーが小さい。
    pは現在扱う深さ
    '''
    D[u] = p
    if T[u].right is not None:
        # 右の兄弟ノード(深さは同じ)から入れていく
        get_all_depth(T, T[u].right, p)
    if T[u].left is not None:
        # 兄弟を入れ終わったら次は下のふさへ
        get_all_depth(T, T[u].left, p+1)

def ret_children(T, u):
    children = []
    c = T[u].left
    while c is not None:
        children.append(c)
        c = T[c].right
    return children

def print_for_a_node(T: dict, node: int, D: dict):
    node_type = 'internal node' if T[node].left is not None else 'leaf'
    if T[node].parent is None:
        parent = -1
        node_type = 'root'
    else:
        parent = T[node].parent
    children = ret_children(T, node)

    print(
        f'node {node}: parent = {parent}, depth = {D[node]}, {node_type}, {children}')

N = int(input())
T = {k: Node(None, None, None) for k in range(N)}
for _ in range(N):
    lst = list(map(int, input().split()))
    if lst[1] == 0:  # もし子ノードがなければ次へ
        continue
    T[lst[0]].left = lst[2]
    T[lst[2]].parent = lst[0]
    prev_sibling = lst[2]  # 前のノード番号を覚えておく用
    for sib in lst[3:]:
        T[prev_sibling].right = sib
        T[sib].parent = lst[0]  # 子から親を与えている
        prev_sibling = sib

for node in range(N):
    if T[node].parent is None:
        get_all_depth(T, node, 0)  # rootを入れなければいけないことに注意
        # Dに深さが入った
        break

for node in range(N):
    print_for_a_node(T, node, D)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2**20)

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

d = {} # {id: depth}
def get_all_depth(t, u, p): # (Tree, id, depth)
    d[u] = p
    if t[u].right is not None:
        get_all_depth(t, t[u].right, p)
    if t[u].left is not None:
        get_all_depth(t, t[u].left, p+1)

def return_children(t, u):
    children = []
    c = t[u].left
    while c is not None:
        children.append(c)
        c = t[c].right
    return children

n = int(input())
t = {k: Node(None, None, None) for k in range(n)}
for _ in range(n):
    tmp = list(map(int, input().split()))
    if tmp[1] == 0: # 子なし
        continue
    t[tmp[0]].left = tmp[2] # 最も左の子
    t[tmp[2]].parent = tmp[0] # 親
    prev_sib = tmp[2]
    for sib in tmp[3:]:
        t[prev_sib].right = sib # すぐ右の子
        t[sib].parent = tmp[0] # 親
        prev_sib = sib

for node in range(n):
    if t[node].parent is None:
        get_all_depth(t, node, 0)
        break

for node in range(n):
    node_type = "internal node" if t[node].left is not None else "leaf"
    if t[node].parent is None:
        parent = -1
        node_type = "root"
    else:
        parent = t[node].parent
    children = return_children(t, node)
    print(f"node {node}: parent = {parent}, depth = {d[node]}, {node_type}, {children}")

Submission status: Accepted

Solution code:
n = int(input())

class Node:
	def __init__(self, index, parent, children):
		self.parent = parent
		self.children = children
		self.depth = -1
		self.index = index
	
	def type(self):
		if self.parent == -1:
			return "root"
		elif len(self.children) == 0:
			return "leaf"
		else:
			return "internal node"
		
nodes = [Node(i, -1,[]) for i in range(n)]

for _ in range(n):
	l = list(map(int, input().split()))
	if l[1] > 0:
		children = l[2:]
		nodes[l[0]].children = children
		for child in children:
			nodes[child].parent = l[0]

def dfs(thisIndex, thisDepth):
	nodes[thisIndex].depth = thisDepth
	for child in nodes[thisIndex].children:
		dfs(child, thisDepth+1)
	

for node in nodes:
	if node.parent == -1:
		depth = 0
		dfs(node.index, 0)
		break
		
for node in nodes:
	print("node {}: parent = {}, depth = {}, {}, {}".format(node.index, node.parent, node.depth, node.type(), node.children))

Submission status: Accepted

Solution code:
from collections import deque

class Node:
    def __init__(self,idx,parent,child,depth):
        self.idx=idx
        self.parent=parent
        self.child=child
        self.depth=depth

n=int(input())

nodes=[Node(-1,-1,-1,-1) for _ in range(n)]

for i in range(n):
    id,k,*c=map(int,input().split())
    nodei=nodes[id]
    nodei.idx=id
    nodei.child=c
    for ci in c:
        nodes[ci].parent=id

q=deque()
root_i=-1
for ni in nodes:
    if(ni.parent==-1):
        root_i=ni.idx
        break

q.append([root_i,0])
while(len(q)>0):
    qi=q.popleft()
    node_idx=qi[0]
    node_depth=qi[1]
    nodes[node_idx].depth=node_depth
    node_child=nodes[node_idx].child
    for c in node_child:
        q.append([c,node_depth+1])


for nodei in nodes:
    print("node "+str(nodei.idx)+": ",end="")
    print("parent = "+str(nodei.parent)+", ",end="")
    print("depth = "+str(nodei.depth)+", ",end="")
    if(nodei.parent==-1):
        print("root, ",end="")
    elif(nodei.child==-1 or len(nodei.child)==0):
        print("leaf, ",end="")
    else:
        print("internal node, ",end="")
    print(nodei.child)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self):
        self.parent = -1
        self.children = []
        self.type = ''
        self.depth = 0

def walk_tree(v, d=0):
    Nodes[v].depth = d
    for child in Nodes[v].children:
        walk_tree(child, d+1)

N = int(input())
Nodes = [Node() for _ in range(N)]
for _ in range(N):
    idx, k, *children = [int(x) for x in input().split()]
    Nodes[idx].children = children
    if k:
        Nodes[idx].type = 'internal node'
    else:
        Nodes[idx].type = 'leaf'
    for child in children:
        Nodes[child].parent = idx
root = [i for i, x in enumerate(Nodes) if x.parent == -1][0]
Nodes[root].type = 'root'
walk_tree(root)
for i, node in enumerate(Nodes):
    print('node {}: parent = {}, depth = {}, {}, [{}]'.format(i, node.parent, node.depth, node.type, ', '.join(map(str, node.children))))

Submission status: Accepted

Solution code:
def tree(s,pls):
	dep[s] += pls
	pls += 1
	#print()
	#print(main[int(order.index(s))])
	for r in range(1,len(main[s])):
		#print(lis)
		tree(main[s][r],pls)

n = int(input())
main = [[-1] * 1 for i in range(n)]
for i in range(n):
	a = input().split()
	for j in range(2,int(a[1])+2):
		main[int(a[j])][0] = int(a[0])
		main[int(a[0])].append(int(a[j]))
	#print(main)

dep = [-1] * n



for i in range(n):
	if main[i][0] == -1:
		tree(int(i),1)
		break

for i in range(n):
	print("node " + str(i) + ": parent = " + str(main[i][0]) +", depth = " + str(dep[i]) + ", " ,end='')
	if main[i][0] == -1:
		print("root, ",end='')
	elif len(main[i]) == 1:
		print("leaf, []")
		continue
	else:
		print("internal node, ",end='')
	print(main[i][1:])


"""
print(main)
print(dep)
"""

Submission status: Accepted

Solution code:
n = int(input())

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

for i in range(n):
  T[i] = list(map(int, input().split()))

TA = [[-1 for i in range(20)] for j in range(n)]

for i in range(n):
  TA[i][0] = i
  k = T[i][1]
  if k >0:
    for j in range(k):
      TA[T[i][2+j]][1] = T[i][0]

for i in range(18):
  for j in range(n):
    if TA[j][1+i] >= 0:
      TA[j][2+i] = TA[TA[j][1+i]][1]

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

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

for i in range(n):
  a = T[i][0]
  TC[a] = T[i]

for i in range(n):
  if TA[i][1] == -1:
    TB[i] = ["node " + str(i) + ": parent = -1,", "depth = 0,", "root,", TC[i][2:] ]
  elif TC[i][1] == 0:
    dep = TA[i].index(-1)-1
    TB[i] = ["node " + str(i) + ": parent = " + str(TA[i][1]) + ",", "depth = " + str(dep) + ",", "leaf,", "[]"]
  else:
    dep = TA[i].index(-1)-1
    TB[i] = ["node " + str(i) + ": parent = " + str(TA[i][1]) + ",", "depth = " + str(dep) + ",", "internal node,", TC[i][2:]]

for i in range(n):
  print(" ".join(map(str, TB[i])))

Submission status: Accepted

Solution code:
'''
左子右兄弟表現で記載する。
元々の木の形を変形させて保存しておく。
具体的には左の木は自分の子供
右の木は自分の兄弟を連結させる。
深さは親を辿っていって、根につくまで加算することで計算する

'''


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

    def get_depth(self):
        if self.parent == -1:
            return 0
        else:
            depth = 1
            t = Nodes[self.parent]
            while t.parent != -1:
                t=Nodes[t.parent]
                depth += 1
            return depth

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


def decode_node_data(n):
    '''
    n...受け取る文字列、一行ずつ
    一行ずつ、文字列からノードに変化する
    '''
    global Nodes
    num_of_elem = len(n)
    if num_of_elem < 2:
        raise ValueError
    elif num_of_elem == 2:  # leaf
        pass

    else:
        id, num_of_children = int(n[0]), int(n[1])
        # 子供
        children = n[2:]
        # まず、一人目の子供をとりあえず左に格納する
        Nodes[id].left = int(children[0])
        prev_child = None

        for c in children:
            # 子Nodeの親を登録しておく
            Nodes[int(c)].parent = id
            if prev_child != None:
                # 兄弟の右の木にprev_childを登録する
                Nodes[prev_child].right = int(c)

            # かこに同じdepthの子供がいる場合、それを登録する
            prev_child = int(c)


MAX_NODES = 100001
Nodes = [Node(-1, None, None) for _ in range(MAX_NODES)]

if __name__ == "__main__":

    num_of_nodes = int(input())
    node_data = []
    for _ in range(num_of_nodes):
        node_data.append(input().split(' '))

    for n in node_data:
        decode_node_data(n)

    for node_id in range(num_of_nodes):
        type = Nodes[node_id].get_type()
        children = []
        #葉でなければ子ノードを集める
        if type != 'leaf':
            #左がついてない時はleaf
            if Nodes[node_id].left != None:
                c = Nodes[node_id].left
                children.append(c)
                #右は兄弟なので追加する
                while Nodes[c].right != None:
                    c = Nodes[c].right
                    children.append(c)
        print('node {0}: parent = {1}, depth = {2}, {3}, [{4}]'.format(
            node_id, Nodes[node_id].parent, Nodes[node_id].get_depth(), type,
            ', '.join(map(str, children))))

Submission status: Accepted

Solution code:
#根付き木
n = int(input())
tree = []

for i in range(n):
    tree.append({})

for i in range(n):
    t = list(map(int, input().split()))
    node = t[0]
    children = t[2:2+t[1]]

    tree[node]['node'] = node
    tree[node]['parent'] = -1
    tree[node]['depth'] = 0
    tree[node]['children'] = children

#親を計算する
for i in range(n):
    for c in tree[i]['children']:
        tree[c]['parent'] = i

#depthを計算する
for i in range(n):
    depth = 0
    t = i
    isParent = False

    while(not isParent):
        if tree[t]['parent'] == -1:
            isParent = True
        else:
            t = tree[t]['parent']
            depth += 1
    
    tree[i]['depth'] = depth


for i in range(n):
    result = ''
    result += 'node '+str(tree[i]['node'])+': parent = '+str(tree[i]['parent'])+', depth = '+str(tree[i]['depth'])+', '
    if tree[i]['parent'] == -1:
        result += 'root, '
    elif tree[i]['children'] == []:
        result += 'leaf, '
    else:
        result += 'internal node, '

    result += '['
    
    r = ''
    for c in tree[i]['children']:
        r += str(c) + ', '

    result += r[:-2]
    result += ']'
    print(result)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2**20)

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

def get_depth(T, u): # T : ノードの情報が入っているdict, u :Node
    d = 0
    while T[u].parent != None:   # TはNodeクラスで作る
        u = T[u].parent     # 親がNIL（つまり根）になるまで親を辿っていく
        d += 1
    return d

D = {}

def get_all_depth(T, u, p):  # p : 深さ
    D[u] = p
    if T[u].right != None:
        get_all_depth(T, T[u].right, p)
    if T[u].left != None:
        get_all_depth(T, T[u].left, p+1)
        
def get_children(T, u):
    children = []
    c = T[u].left
    while c != None:
        children.append(c)
        c = T[c].right
    return children


# 入力
n = int(input()) # Node（節点）の数
T = {i : Node(None, None, None) for i in range(n)} # 情報を入れるdictをNodeクラスで作成

for _ in range(n):   # 変数名を「 _ 」にすることによって、「その変数を使っていない」ことを表現している（Pythonの習慣）
    tmp = list(map(int, input().split())) # Nodeの情報を格納[節点の番号, 次数, 1番目の子の節点番号, ..., k番目の子の節点番号]
    if tmp[1] == 0:  # 子Nodeがなければ次へ 
        continue
    T[tmp[0]].left = tmp[2] # 今見ているNode（tmp[0]）のleftアトリビュートに左子Nodeを入れる
    T[tmp[2]].parent = tmp[0]  # 当然tmp[2]の親はtmp[0]
    prev_sibling = tmp[2]  # 兄弟の一番左のNode番号を保存しておく
    for sib in tmp[3:]:  # 残りの兄弟について
        T[prev_sibling].right = sib  # 一つ右の兄弟 
        T[sib].parent = tmp[0]  # 親は同じくtmp[0]（当然）
        prev_sibling = sib
        
# 出力
def print_for_a_node(T, node, D):
    if T[node].left == None:
        node_type = "leaf"
    else:
        node_type = "internal node"
    
    if T[node].parent == None:
        parent = -1
        node_type = "root"
    else:
        parent = T[node].parent
    
    children = get_children(T, node)

        
    #print(f"node {node} : parent = {parent}, depth = {D[node]}, {node_type}, {children}")
    print("node {}: parent = {}, depth = {}, {}, {}".format(node, parent, D[node], node_type, children))

for node in range(n):
    if T[node].parent == None:
        get_all_depth(T, node, 0)  # rootを入れる
        # Dに深さが入る
        break
        
for node in range(n):
    print_for_a_node(T, node, D)

Submission status: Accepted

Solution code:
"""
根付き木を構成する
"""
class Node:
    def __init__(self):
        self.parent = -1
        self.depth = 0
        self.children = []

#空の木の構成
#node_idをインデックスに持たせる
n = int(input())
nodes = []
for _ in range(n):
    node = Node()
    nodes.append(node)

def getDepth(node_id):
    d = 0
    target = nodes[node_id]
    while target.parent != -1:
        d += 1
        tmp_num = target.parent
        target = nodes[tmp_num]
    return d

def getParent(node_id):
    target = nodes[node_id]
    return target.parent

def getChildren(node_id):
    target = nodes[node_id]
    return target.children

def getType(node_id):
    target = nodes[node_id]
    if target.parent == -1:
        return 'root'
    elif len(target.children) == 0:
        return 'leaf'
    else:
        return 'internal node'


#木の構成
for i in range(n):
    l = list(map(int, input().split()))
    node_id = l[0]
    num = l[1]

    for j in range(num):
        try:
            child = l[2+j] #l[2+j]というのは子供の番号
            nodes[node_id].children.append(child) 
            nodes[child].parent = node_id #子一人当たり親は必ず一人
        except:
            pass
    else:
        pass #子がいないとき


for i in range(n):
    ans = 'node '+str(i)+': parent = '+str(getParent(i))+', ' +\
    'depth = '+str(getDepth(i))+', '+getType(i)+', '+str(getChildren(i))
    print(ans)

Submission status: Accepted

Solution code:
import sys

n = int(input())

nodes = [[-1, None, None] for _ in range(n)]

depths = [None for _ in range(n)]

for _ in range(n):
    nid, k, *children = list(map(int, sys.stdin.readline().split()))
    if k > 0:
        nodes[nid][1] = children[0]
    children.append(None)
    for i in range(k):
        cid = children[i]
        nodes[cid][0] = nid
        nodes[cid][2] = children[i+1]

def get_depth(nid):
    if depths[nid] is not None:
        return depths[nid]
    elif nodes[nid][0] == -1:
        depths[nid] = 0
        return 0
    else:
        depths[nid] = get_depth(nodes[nid][0]) + 1
        return depths[nid]
    

def get_children(nid):
    children = []
    cid = nodes[nid][1]
    while cid is not None:
        children.append(cid)
        cid = nodes[cid][2]
    return children

for nid in range(n):
    pid = nodes[nid][0]
    children = get_children(nid)
    depth = get_depth(nid)
    n_type = 'root' if pid == -1 else 'leaf' if len(children) == 0 else 'internal node'

    print('node {}: parent = {}, depth = {}, {}, {}'.format(nid, pid, depth, n_type, children))

Submission status: Accepted

Solution code:
# coding: utf-8

n = int(input())
prt = [-1 for i in range(n)]
chd = [[] for i in range(n)]
dpt = [0 for i in range(n)]

def putDepth(nodenum, d):
    dpt[nodenum] = d
    if len(chd[nodenum]) > 0:
        for i in chd[nodenum]:
            putDepth(i, d + 1)

for i in range(n):
    ipt = list(map(int, input().split()))
    idx = 0
    for j in ipt:
        idx += 1
        if idx < 3:
            continue
        prt[j] = ipt[0]
        chd[ipt[0]].append(j)

for i in range(n):
    if prt[i] == -1:
        putDepth(i, 0)
        break
    
for i in range(n):
    if dpt[i] == 0:
        nodetype = 'root'
    elif len(chd[i]) == 0:
        nodetype = 'leaf'
    else:
        nodetype = 'internal node'
    print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(i, prt[i], dpt[i], nodetype, chd[i]))

Submission status: Accepted

Solution code:
class tree:
    def __init__(self, node, children):
        self.node = node
        self.children = children
        self.feature = None
        self.parent = None
        self.depth = 0


def set_feature(info_list):
    for info in info_list:
        if info.depth == 0:
            info.feature = 'root'
        else:
            if len(info.children) == 0:
                info.feature = 'leaf'
            else:
                info.feature = 'internal node'

def get_root_node(info_list):
    cand_nodes = []
    remove_node = []
    for info in info_list:
        if len(info.children) != 0:
            cand_nodes.append(info.node)
            remove_node.extend(info.children)
    if len(cand_nodes) == 1:
        return cand_nodes[0]
    elif len(cand_nodes) == 0:
        return info_list[0].node
    else:
        co_value = (set(cand_nodes) ^ set(remove_node)) & set(cand_nodes)
    return co_value.pop()
    
def set_parent(info_list):
    for info in info_list:
        if info.feature == 'root':
            info.parent = -1
        children = info.children
        for child in children:
            info_list[child].parent = info.node

def set_depth(child, depth, node_infos):
    if len(node_infos[child].children) == 0:
        node_infos[child].depth = depth
    else:
        depth += 1
        children = node_infos[child].children
        for child in children:
            info_list[child].depth = depth
            set_depth(child, depth, node_infos)
        

N = int(input())
info_list = [0] * N
for i in range(N):
    info = [int(i) for i in input().split()] 
    node_num = info.pop(0)
    nchild = info.pop(0)
    info_list[node_num] = tree(node_num, info)

root_node = get_root_node(info_list)
set_depth(root_node, 0, info_list)

for info in info_list:
    if info.depth == 0:
        info.feature = 'root'
    else:
        if len(info.children) == 0:
            info.feature = 'leaf'
        else:
            info.feature = 'internal node'

for info in info_list:
    if info.feature == 'root':
        info.parent = -1
    children = info.children
    for child in children:
        info_list[child].parent = info.node

for info in info_list:
    print('node {}: parent = {}, depth = {}, {}, {}'.format(
        info.node, info.parent, info.depth, info.feature, info.children
    )
)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

class Tree():
    def __init__(self, parent, child, sibling):
        self.parent = parent
        self.child = child  # 最も左の子left child
        self.sibling = sibling  # すぐ右の兄弟right sibling
        self.depth = -1

    def gettreetype(self):
        if self.parent == -1:
            return "root"
        if self.child == -1:
            return "leaf"
        return "internal node"


def setdepth(id, depth, trees):
    trees[id].depth = depth
    child = trees[id].child
    if child >= 0:
        setdepth(child, depth + 1, trees)
    sibling = trees[id].sibling
    if sibling >= 0:
        setdepth(sibling, depth, trees)


def getroot(trees, n):
    for i in range(n):
        if trees[i].parent == -1:
            return i


def getsiblings(tree, trees):
    siblings = []
    sibling = tree.sibling
    while sibling > -1:
        siblings.append(sibling)
        sibling = trees[sibling].sibling
    return siblings


def getchildren(tree, trees):
    children = []
    child = tree.child
    if child > -1:
        children.append(child)
        sibling = trees[child].sibling
        while sibling > -1:
            children.append(sibling)
            sibling = trees[sibling].sibling
    return children


def settree(node_info, trees):
    id = node_info[0]
    dim = node_info[1]
    children = node_info[2:]
    trees[id].child = children[0]
    for i in range(dim):
        trees[children[i]].parent = id
        trees[children[i]].sibling = children[i + 1]


def printtrees(trees, n):
    for i in range(n):
        tree = trees[i]
        parent = tree.parent
        depth = tree.depth
        tree_type = tree.gettreetype()
        children = getchildren(tree, trees)
        print("node {}: parent = {}, depth = {}, {}, [{}]".format(
            i, parent, depth, tree_type, ", ".join(map(str, children))))


def main():
    n = int(input())
    trees = [Tree(-1, -1, -1) for _ in range(n)]
    for _ in range(n):
        node_info = input().split(" ")
        node_info = list(map(int, node_info)) + [-1]
        settree(node_info, trees)
    root = getroot(trees, n)
    setdepth(root, 0, trees)
    printtrees(trees, n)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
cn = [0 for i in range(n)]
p = [-1 for i in range(n)]
d = [0 for i in range(n)]
for i in range(n):
  id, k, *c = list(map(int, input().split()))
  for j in c:
    p[j] = id
  cn[id] = c

for i in range(n):
  print("node " + str(i) + ": parent = " + str(p[i]) + ", ", end = "")
  j=i
  while p[j] != -1:
    d[i] += 1
    j=p[j]
  if p[i] == -1:
    print("depth = 0, root, ", end = "")
    print(cn[i])
  else:
    if cn[i] == []:
      print("depth = " + str(d[i]) + ", leaf, ", end = "")
      print(cn[i])
    else:
      print("depth = " + str(d[i]) + ", internal node, ", end = "")
      print(cn[i])