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:
# ALDS1_7_A Rooted Trees
import sys


class Node:
    def __init__(self):
        self.child = []
        self.parent = -1
        self.type = 'root'


def calc_depth(node):
    global depth_num
    if node.parent != -1:
        depth_num += 1
        calc_depth(tree[node.parent])
    return depth_num


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

for i in range(n):
    A = list(map(int, sys.stdin.readline().strip().split()))
    if A[2:]:
        tree[A[0]].child = A[2:]
    else:
        tree[A[0]].type = 'leaf'

    for j in A[2:]:
        tree[j].parent = A[0]
        if tree[j].type != 'leaf':
            tree[j].type = 'internal node'

for i in range(n):
    depth_num = 0
    depth = calc_depth(tree[i])
    if n == 1:
        type = 'root'
    else:
        type = tree[i].type
    print('node {}: parent = {}, depth = {}, {}, {}'.format(i, tree[i].parent, depth, type, tree[i].child))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)


class Node:

    def __init__(self, _id):
        self.id = _id
        self.children = []
        self.parent = None
        self.__depth = 0
    
    def add(self, node):
        node.parent = self
        self.children.append(node)

    def parent_id(self):
        if self.parent is None:
            return -1
        else:
            return self.parent.id

    def node_type(self):
        if self.parent is None:
            return 'root'
        elif len(self.children) == 0:
            return 'leaf'
        else:
            return 'internal node'

    def children_ids(self):
        return list(map(lambda n: n.id, self.children))

    def depth(self):
        if self.parent is None:
            return 0
        else:
            return self.parent.depth() + 1

    def __repr__(self):
        return 'node {}: parent = {}, depth = {}, {}, {}'.format(
            self.id, self.parent_id(), self.depth(), self.node_type(), self.children_ids())


def main():
    n = int(input())
    nodes = [Node(i) for i in range(n)]
    for _ in range(n):
        ID, _, *c_s = map(int, input().split(' '))
        for c in c_s:
            nodes[ID].add(nodes[c])
    for n in nodes:
        print(n)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from enum import Enum
import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

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

global nodes

def calc_depth(node_id,arg_depth):

    nodes[node_id].depth = arg_depth
    for child in nodes[node_id].children:
        calc_depth(child, arg_depth+1)


V = int(input())

nodes = []
#あらかじめ、V個のノードを用意しておく
for loop in range(V):
    node = Node()
    nodes.append(node)

#親子関係の取得
for loop in range(V):

    table = list(map(int,input().split()))
    node_id = table[0]
    num = table[1]

    for i in range(num):
        child_id = table[2+i]
        nodes[node_id].children.append(child_id)
        nodes[child_id].parent_id = node_id


#根を探して、深さを計算する
for i in range(V):
    if nodes[i].parent_id == -1:
        calc_depth(i,0)
        break


for i in range(V):

    print("node %d: parent = %d, depth = %d, "%(i,nodes[i].parent_id,nodes[i].depth),end = "")

    if nodes[i].parent_id == -1:
        print("root,",end = "")
    else:
        if len(nodes[i].children) == 0: #葉
            print("leaf,",end = "")
        else: #節
            print("internal node,",end = "")

    print(" [",end = "")
    print(', '.join(map(str,nodes[i].children)),end = "")
    print("]")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class Node:
    def __init__(self):
        self.parent = -1
        self.typ = "leaf"

def dfs(G, v, d=0):
    G[v].depth = d
    for child in G[v].childlen:
        dfs(G, child, d+1)

def main():
    N = int(input())
    G = [Node() for _ in range(N)]
    for _ in range(N):
        idx, k, *childlen = map(int, input().split())
        G[idx].childlen = childlen
        if k:
            G[idx].typ = "internal node"
        for child in childlen:
            G[child].parent = idx
    root = [i for i, x in enumerate(G) if x.parent == -1][0]
    G[root].typ = 'root'
    dfs(G, root)
    for i, x in enumerate(G):
        print('node {}: parent = {}, depth = {}, {}, [{}]'.format(i, x.parent, x.depth, x.typ, ', '.join(list(map(str, x.childlen)))))

if __name__ == '__main__': main()

Submission status: Accepted

Solution code:
class treeNode:
    def __init__(self, x):
        self.val = x
        self.children = []
    
n = int(input())
rootL = list(range(n))
hashMap = {}
index = 0
while index < n:
    listI = list(map(int, input().split()))
    if listI[0] in hashMap:
        node = hashMap[listI[0]]
        childrenL = []
        if listI[1] == 0:
            pass
        else:
            for child in listI[2:]:
                rootL.remove(child)
                if child in hashMap:
                    childN = hashMap[child]
                else:
                    childN = treeNode(child)
                childrenL.append(childN)
                hashMap[child] = childN
        node.children = childrenL
    else:
        hashMap[listI[0]] = treeNode(listI[0])
        childrenL = []
        for child in listI[2:]:
            rootL.remove(child)
            if child in hashMap:
                childN = hashMap[child]
            else:
                childN = treeNode(child)
            childrenL.append(childN)
            hashMap[child] = childN
        hashMap[listI[0]].children = childrenL
    index+=1

root = hashMap[rootL[0]]
answerL = ['']*n

def lookNode(node, parentV, depth):
    answer = ''
    answer+='node '+str(node.val)+': '
    answer+='parent = '+str(parentV)+', '
    answer+='depth = '+str(depth)+', '
    if depth == 0:
        answer+='root,'
    elif node.children == []:
        answer+='leaf,'
    else:
        answer+='internal node,'
    childrenL = []
    for child in node.children:
        childrenL.append(child.val)
    answerL[node.val] = [answer, childrenL]
    for child in node.children:
        lookNode(child, node.val, depth+1)
lookNode(root, -1, 0)
for ans in answerL:
    print(ans[0], ans[1])

Submission status: Accepted

Solution code:
import sys

class Node():

	def __init__(self,id,k,children):
		
		self.id = id
		self.k = k
		self.children = children
		self.parent = -1
		self.depth = 0

def find_root(Nodes,node):

	if node.parent == -1:
		return node.id

	return find_root(Nodes,Nodes[node.parent])

def define_depth(Nodes,node):

	if node.k == 0: #leaf
		return True

	for child in node.children: #internal node
		Nodes[child].depth = node.depth + 1
		define_depth(Nodes,Nodes[child])

def sort(Nodes):

	for i in range(len(Nodes)-1):
		for j in range(i+1,len(Nodes)):

			if Nodes[i].id > Nodes[j].id:

				Nodes[i],Nodes[j] = Nodes[j],Nodes[i]

def test():

	n = int(sys.stdin.readline())
	child = []
	Nodes = [Node(0,0,child)] * n
	root = 0

	# Reading inputs
	for i in range(n):

		inputs = list(map(int,sys.stdin.readline().split()))
		id = inputs[0]
		k = inputs[1]
		child = []
		for j in range(k):
			child.append(inputs[2+j])

		tmp_node = Node(id,k,child)
		Nodes[id] = tmp_node

	#sort(Nodes)

	# Add "parent" attribute
	for node in Nodes:

		for i in range(node.k):
			
			Nodes[node.children[i]].parent = node.id
	
	# Find "root"
	root = find_root(Nodes,Nodes[0])

	#print(root)

	# Define depth from root
	define_depth(Nodes,Nodes[root])

	for i in range(n):

		print(f"node {Nodes[i].id}: parent = {Nodes[i].parent}, depth = {Nodes[i].depth}, ",end='')

		if Nodes[i].parent == -1:
			print(f"root, [",end='')
		elif Nodes[i].k == 0:
			print(f"leaf, [",end='')
		else:
			print(f"internal node, [",end='')

		for j in range(Nodes[i].k - 1):
			print(f"{Nodes[i].children[j]}, ",end='')
		if Nodes[i].k != 0:
			print(f"{Nodes[i].children[Nodes[i].k-1]}]")
		else:
			print("]")


if __name__ == "__main__":
	test()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
P = [-1]*n
C = [[] for i in range(n)]
D = [[] for i in range(n)]
T = [[] for i in range(n)]

for i in range(n):
  s = [int(i) for i in input().split()]
  id = s[0]
  k = s[1]
  if k >= 1:
    c = s[2:]
    C[id] = c
    for j in range(k):
      P[c[j]] = id
  else:
    T[id] = "leaf"

for i in range(n):
  if P[i] == -1:
    root = i
    T[i] = "root"
  elif T[i] == []:
    T[i] = "internal node"

H = deque()
H.append(root)
D[root] = 0

while H:
  x = H.popleft()
  for nx in C[x]:
    H.append(nx)
    D[nx] = D[x] + 1

for i in range(n):
  print("node {}: parent = {}, depth = {}, {}, {}".format(i,P[i],D[i],T[i],C[i]))

Submission status: Accepted

Solution code:
import sys

n = int(input())

"""子情報を入れる'c'、親情報を入れる'p'、深さを記録する'd'の、3つの辞書を作る"""
c, p, d = {}, {}, {}

"""根のid, depthを引数とすることで、全てのnodeの深さを'd'に記録する関数"""
def checkdepth(id, depth):
    d[id] = depth
    for child in c[id]:
        checkdepth(child, depth+1)

for i in sys.stdin:
    i = i.split()
    """i[0]=id, i[1]=k, i[2:]=children"""
    c[i[0]] = i[2:]
    for j in i[2:]:
        p[j] = i[0]

"""親の集合から子の集合を差し引いて残ったものは根（root）になる"""
root = (set(c) - set(p)).pop()
p[root] = '-1'
checkdepth(root, 0)

for i in range(n):
    i = str(i)
    if p[i] == '-1':
        nodetype = 'root'
    else:
        if c[i]:
            nodetype = 'internal node'
        else:
            nodetype = 'leaf'
    children = ', '.join(c[i])
    print('node {}: parent = {}, depth = {}, {}, [{}]'.format(i, p[i], d[i], nodetype, children))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
n=int(input())
inp=[list(map(int,input().split())) for i in range(n)]
inp.sort(key=lambda tup:tup[0])
data=[[-1]*3 for i in range(n)]
D=[-1]*n

for e in inp:
    for i in range(2,len(e)):
        data[e[i]][0]=e[0]
        if i==2:
            data[e[0]][1]=e[i]
        else:
            data[l][2]=e[i]
        l=e[i]

for i in range(n):
    if data[i][0]==-1:
        r=i

def defth(node,p):
    D[node]=p
    if data[node][1]!=-1:
        defth(data[node][1],p+1)
    if data[node][2]!=-1:
        defth(data[node][2],p)

defth(r,0)

for i in range(n):
    if i==r:sta='root'
    elif len(inp[i])==2:sta='leaf'
    else: sta='internal node'
    print(f'node {i}: parent = {data[i][0]}, depth = {D[i]}, {sta}, {inp[i][2:]}')

Submission status: Accepted

Solution code:
#left child right siberings representation
#left : index of the most left children
#right : index of the nearest right siberings


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


class tree:
    #give some list to define the tree structure
    def __init__(self, list):
        #root initialization
        self.root=None
        self.T=[]
        self.insert(list)

    #parse data to tree structure
    def insert(self,list):
        nnodes=len(list)
        for i in range(nnodes):
            self.T.append(node(None, None, None))
        for i in range(nnodes):
            #n=node index
            n=int(list[i][0])
            nch=list[i][1]
            for j in range(nch):
                chnode=list[i][2+j]
                #set the parent in the each child node
                self.T[chnode].parent=n
                if (j==0):
                    #most left children
                    self.T[n].left=chnode

                #define the nearest right siberings in the child node
                if (j < nch-1):
                    self.T[chnode].right=list[i][j+3]

    def getDepth(self, index):
        d=0
        u=index
        while self.T[u].parent !=None:
            u=self.T[u].parent
            d=d+1

        return d

    def getChildrens(self, index):
        ch=[]
        c=self.T[index].left
        ic=c
        while ic!=None:
            ch.append(ic)
            ic=self.T[ic].right

        return ch

    def printNode(self, index):
        print("parent="+str(self.T[index].parent)+",depth="+str(self.getDepth(index)) +\
              ",right="+str(self.T[index].right)+ ",left="+str(self.T[index].left))
        print(self.getChildrens(index))
        return

    def stringForAOJ(self,index):
        #node index
        strs=""
        strs=strs+"node "+str(index)+":"

        #parent
        if self.T[index].parent==None:
            strs=strs+" parent = -1,"
        else:
            strs = strs + " parent = "+str(self.T[index].parent)+","

        #depth
        strs=strs+" depth = "+str(self.getDepth(index))+","

        #type
        if self.T[index].parent==None:
            strs=strs+" root,"
        elif self.T[index].left==None:
            strs = strs + " leaf,"
        else:
            strs = strs + " internal node,"

        #childrens
        strs=strs+" ["
        ch=self.getChildrens(index)
        for i in range(len(ch)):
            strs=strs+str(ch[i])
            if (i < len(ch)-1):
                strs=strs+", "

        strs=strs+"]"

        return strs





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

#print(dlist)
t=tree(dlist)

for i in range(n):
    print(t.stringForAOJ(i))

Submission status: Accepted

Solution code:
class Node():
    def __init__(self, id, children):
        self.id = id
        self.children = children

N = int(raw_input())
nodes = {}
for _ in range(N):
    d = map(int, raw_input().split())
    id,k,cs = d[0],d[1],d[2:]
    nodes[id] = Node(id, cs)

roots = range(N)
for i in range(N):
    [roots.remove(j) for j in nodes[i].children]
    nodes[i].children = [nodes[j] for j in nodes[i].children]

data = []
def traverse(node, p, d):
    id = node.id
    cs = map(lambda x:x.id, node.children)
    if p == -1:
        t = "root"
    elif len(cs) == 0:
        t = "leaf"
    else:
        t = "internal node"
    s = "node {}: parent = {}, depth = {}, {}, {}".format(id,p,d,t,cs)
    data.append((id, s))
    
    for child in node.children:
        traverse(child, id, d+1)

root = roots[0]
traverse(nodes[root], -1, 0)
for _,s in sorted(data, key=lambda x:x[0]):
    print s

Submission status: Accepted

Solution code:
n=int(input())

C=[[] for i in range(n+1)]
P=[-1 for i in range(n+1)]
D=[0 for i in range(n+1)]
T=["" for i in range(n+1)]
#入力の取得
for i in range(n):
    data=list(map(int,input().split( )))
    C[data[0]]=data[2:]
#親
for i in range(n):
    if len(C[i])>0:
        for nodes in C[i]:
            P[nodes]=i
#深さと種類
for i in range(n):
    d=0
    v=i
    while P[v]!=-1:
        v=P[v]
        d+=1
    D[i]=d
    if d==0:
        T[i]="root"
    elif len(C[i])>0:
        T[i]= "internal node"
    else:
        T[i]="leaf"
for i in range(n):
    print(f"node {i}: parent = {P[i]}, depth = {D[i]}, {T[i]}, [",end="")
    if len(C[i])>0:
        str_i=", ".join((map(str,C[i])))
        print(str_i,end="")
    print("]")

Submission status: Accepted

Solution code:
# coding: utf-8

NULL = -1

class Node():
    def __init__(self):
        self.parent =  NULL # parent node
        self.left = NULL    # first child node
        self.right = NULL   # brother node
        self.depth = NULL   # depth of node
        self.type = ""      # type of node(root, internal node, leaf)

def set_depth(T: list, r: int, d: int):
    T[r].depth = d
    if T[r].left != NULL:
        set_depth(T, T[r].left, d + 1)

    if T[r].right != NULL:
        set_depth(T, T[r].right, d)

n = int(input())

T = []
for i in range(n):
    T.append(Node())

cur = 0
for i in range(n):
    nodeinfo = [int(x) for x in input().split()]
    for j in range(nodeinfo[1]):
        if j == 0:
            T[nodeinfo[0]].left = nodeinfo[2+j]
        else:
            T[cur].right = nodeinfo[2+j]
        cur = nodeinfo[2+j]
        T[cur].parent = nodeinfo[0]

# find root node
root = 0
for i, v in enumerate(T):
    if v.parent == NULL:
        root = i
        break

# set depth to all nodes
# set_depth(T, root, 0)

# set type
for v in T:
    if v.parent == NULL:
        v.type = "root"
    elif v.left == NULL:
        v.type = "leaf"
    else:
        v.type = "internal node"

for i, v in enumerate(T):
    childlen = []
    if T[i].left != NULL:
        child = T[i].left
        childlen.append(str(child))

        while T[child].right != NULL:
            child = T[child].right
            childlen.append(str(child))

    depth = 0
    cur = i
    while T[cur].parent != NULL:
        depth += 1
        cur = T[cur].parent
            
    print("node {}: parent = {}, depth = {}, {}, {}".format(i, v.parent, depth, v.type, "[" + ", ".join(childlen) + "]"))

Submission status: Accepted

Solution code:
class Node:
    '''
    p: parent node
    l: child node
    r: sibling node
    '''
    def __init__(self, p=-1, l=-1, r=-1):
        self._p = p
        self._l = l
        self._r = r

Depth = []
T = []

def rec(node, depth):
    global Depth
    global T
    Depth[node] = depth

    child = T[node]._l
    while child != -1:
        rec(child, depth + 1)
        child = T[child]._r


    # if T[node]._r != -1:
    #     rec(T[node]._r, depth)

    # if T[node]._l != -1:
    #     rec(T[node]._l, depth + 1)

def print_node(index):
    global Depth
    global T
    print('node %d: parent = %d, depth = %d, '%(index, T[index]._p, Depth[index]), end='')

    if T[index]._p == -1:
        print('root, [', end='')
    elif T[index]._l == -1:
        print('leaf, [', end='')
    else:
        print('internal node, [', end='')

    i = 0
    node = T[index]._l
    while node != -1:
        if i:
            print(', ', end='')
        print(node, end='')

        i += 1
        node = T[node]._r
    print(']')
    


if __name__ == '__main__':
    n = int(input())

    for i in range(n):
        T.append(Node())
    Depth = [-1]*n
    for i in range(n):
        parent_node, child_cnt, *child_node = map(int, input().split())
        for j in range(child_cnt):
            if j == 0:
                T[parent_node]._l = child_node[j]
            else:
                T[child_node[j - 1]]._r = child_node[j]
            T[child_node[j]]._p = parent_node

    root = 0
    for i in range(n):
        if T[i]._p == -1:
            root = i
            break
    
    rec(root, 0)

    for i in range(n):
        print_node(i)

Submission status: Accepted

Solution code:
def compute_depth(node: int, depth: int) -> None:
    global trees
    trees[node][1] = depth
    for child in trees[node][3]:
        compute_depth(child, depth + 1)


if __name__ == "__main__":
    node_num = int(input())
    trees = {idx: [-1, 0, "", [0]] for idx in range(node_num)}  # parent, depth, node_type, children

    for _ in range(0, node_num):
        node, _, *children = map(lambda x: int(x), input().split())
        trees[node][3] = children
        for child in children:
            trees[child][0] = node  # Add parent information to each child.

    for node, values in sorted(trees.items(), key=lambda x: x[1][0]):
        parent = values[0]
        children = values[3]
        if -1 == parent:
            trees[node][2] = "root"
            compute_depth(node, 0)
        else:
            # depth = trees[trees[node][0]][1] + 1  # Parents' depth + 1
            # trees[node][1] = depth
            if [] == children:
                trees[node][2] = "leaf"
            else:
                trees[node][2] = "internal node"

    for node, values in trees.items():
        parent = values[0]
        depth = values[1]
        node_type = values[2]
        children = values[3]
        print(f"node {node}: parent = {parent}, depth = {depth}, {node_type}, {children}")

Submission status: Accepted

Solution code:

class Node_information():
    def __init__(self):
        self.id = -1
        self.parent = -1
        self.depth = 0
        self.type = ""
        self.child = list()

def get_tree_id_child_and_parent(tree_id, tree_k, tree_information, node_information):
    for j in range(tree_k):
        tree_information[tree_id].child.append(node_information[j+2])
        tree_information[node_information[j+2]].parent = tree_id

def get_tree_id_type(number_of_child):
    if number_of_child == 0:
        return "leaf"
    else:
        return "internal node"

def depth_search(tree_information, now_depth, now_id):
    tree_information[now_id].depth = now_depth
    for i in range(len(tree_information[now_id].child)):
        depth_search(tree_information, now_depth+1,tree_information[now_id].child[i])
    
def print_tree_information(tree_information, N):
    for i in range(N):
        print("node {}: parent = {}, depth = {}, {}, [".format(tree_information[i].id,tree_information[i].parent,tree_information[i].depth,tree_information[i].type),end="")
        for j in range(len(tree_information[i].child)):
            if j != len(tree_information[i].child) - 1:
                print("{},".format(tree_information[i].child[j]),end=" ")
            else: 
                print("{}".format(tree_information[i].child[j]),end="")
        print("]")


def main():
    N = int(input())
    tree_information = list()
    for i in range(N):
        tree_information.append(Node_information())
    for i in range(N):
        node_information = [int(i) for i in input().split()]
        tree_id = node_information[0]
        tree_k = node_information[1]
        tree_information[tree_id].id = node_information[0]
        get_tree_id_child_and_parent(tree_id, tree_k, tree_information, node_information)
        tree_information[tree_id].type = get_tree_id_type(len(tree_information[tree_id].child))
    for i in range(N):
        if tree_information[i].parent == -1:
            tree_information[i].type = "root"
            depth_search(tree_information,0,i)
    print_tree_information(tree_information, N)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

def printChildren(u):
    c = Nodes[u].left
    output_list = []
    while c != -1:
        output_list.append(c)
        c = Nodes[c].right
    return output_list

# ノードの情報を出力する。
def printNodes(u):
    output_str = "node " + str(u) + ": parent = " + str(Nodes[u].parent) + ", depth = " + str(getDepth(u))
    if -1 == Nodes[u].parent:
        output_str = output_str + ", root, "
    elif Nodes[u].left != -1:
        output_str = output_str + ", internal node, "
    else:
        output_str = output_str + ", leaf, "
    # output_str += printChildren(u)
    print(output_str, "[{}]".format(", ".join(map(str, printChildren(u)))), sep="")

Nodes = []
for i in range(100000):
    tmp_obj = Node()
    Nodes.append(tmp_obj)

# 入力
n = int(input())


for tmp_count in range(n):
    input_val = list(map(int, input().split()))
    if 0 != input_val[1]:
        # 最も左の子の情報
        Nodes[input_val[0]].left = input_val[2]
        # 親の情報
        Nodes[input_val[2]].parent = input_val[0]
        
        for i in range(input_val[1] - 1):
            # 右の兄弟の情報
            Nodes[input_val[i+2]].right = input_val[i+3]
            # 親の情報
            Nodes[input_val[i+3]].parent = input_val[0]

for i in range(n):
    printNodes(i)

Submission status: Accepted

Solution code:
n = int(input())
nodes = [None] * n
rootIdx = None

class Node:
    parent = property
    node_type = property
    depth = property

    def __init__(self, ID, k, c):
        self.parent = -1
        self.ID = ID
        self.k = k
        self.c = c

    def print_self(self):
        print('node {}: parent = {}, depth = {}, {}, '.format(self.ID, self.parent, self.depth, self.node_type) + str(self.c))

def trace(node, depth):
    node.depth = depth
    if len(node.c) > 0:
        for i in range(len(node.c)):
            child = nodes[node.c[i]]
#            child.parent = node.ID
            trace(child, depth + 1)

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

    # if rootIdx in c:
    #     rootIdx = ID

#print(nodes)
#trace(nodes[0], 0)
for i in range(n):
    node = nodes[i]
    if len(node.c) > 0:
        for i in range(len(node.c)):
            child = nodes[node.c[i]]
            child.parent = node.ID

for i in range(n):
    node = nodes[i]
    if node.parent == -1:
        rootIdx = node.ID

trace(nodes[rootIdx], 0)

for i in range(n):
    node = nodes[i]

    if node.parent == -1:
        node.node_type = 'root'
    elif len(node.c) > 0:
        node.node_type = 'internal node'
    else:
        node.node_type = 'leaf'

for i in range(n):
    nodes[i].print_self()

Submission status: Accepted

Solution code:

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


def dfs(id, d):
    Nodes[id].depth = d
    for child in Nodes[id].children:
        dfs(child, d+1)


def main():
    n = int(input())
    global Nodes
    Nodes = [Node() for i in range(n)]

    for i in range(n):
        id, k, *c = map(int, input().split())
        Nodes[id].children = c
        if k == 0:
            Nodes[id].type = "leaf"
        else:
            Nodes[id].type = "internal node"
            for j in range(k):
                Nodes[c[j]].parent = id

    rootid = ""
    for i, node in enumerate(Nodes):
        if node.parent == -1:
            rootid = i
    Nodes[rootid].type = "root"
    dfs(rootid, 0)

    for i, node in enumerate(Nodes):
        print("node {}: parent = {}, depth = {}, {}, {}".format(
            i, node.parent, node.depth, node.type, node.children))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

list_tree = [[] for _ in range(n)]
list_parent = [None for _ in range(n)]

for _ in range(n):

    id, k, *C = map(int, input().split())

    list_tree[int(id)].extend(C)

    for c in C:
        list_parent[int(c)] = int(id)


for id in range(n):
    child = list_tree[id]

    if list_parent[id] == None:
        parent = -1
    else:
        parent = list_parent[id]

    depth = 0
    parent_now = list_parent[id]

    while parent_now != None:
        depth += 1
        parent_now = list_parent[parent_now]

    if depth == 0:
        type_node = "root"
    elif not child:
        type_node = "leaf"
    else:
        type_node = "internal node"

    print(f"node {id}: parent = {parent}, depth = {depth}, {type_node}, {child}")

Submission status: Accepted

Solution code:
n = int(input())

tree = []
for i in range(n):
  data = list(map(int,input().split()))
  node = data[0]
  depth = data[1]
  child = []
  parent = -1
  for j in data[2:]:
    child.append(j)
  tree.append([node,depth,child,parent])

tree.sort()

for i in range(len(tree)):
#  print(tree[i])
  for j in tree[i][2]:
    tree[j][3] = i

def rooting(tree,node,depth):
  tree[node][1] = depth
  if len(tree[node][2]) == 0:
    return
  for i in tree[node][2]:
    rooting(tree,i,depth+1)

for i in range(n):
  if tree[i][3] == -1:
    root = i
rooting(tree,root,0)


for i in range(n):
  print("node %d: parent = %d, depth = %d," %(tree[i][0],tree[i][3],tree[i][1]),end=" ")
  if tree[i][3] == -1:
    print("root,",end=" ")
  elif tree[i][3] != -1 and len(tree[i][2]) != 0:
    print("internal node,",end=" ")
  else:
    print("leaf,",end=" ")
  print(tree[i][2])