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:
n=int(input())
nil=-1
sn=[[-1,-1,-1]for _ in range(n)]
child=[[]for _ in range(n)]
def getdepth(u):
	d=0
	while sn[u][0] != nil:
		u=sn[u][0]
		d+=1
	return d
aa=[]
for i in range(n):
	a=list(map(int,input().split()))
	aa.append(a)
aa.sort()
for i in range(n):
	a=aa[i]
	for j in range(a[1]):
		sn[a[j+2]][0]=a[0]
		if j==0:
			sn[a[0]][1]=a[j+2]
		if j!=a[1]-1:
			sn[a[j+2]][2]=a[j+1]
		child[i].append(a[j+2])
for i in range(n):
	ans1="node "+str(i)+":"
	ans2="parent = "+str(sn[i][0])+","
	ans3="depth = "+str(getdepth(i))+","
	if sn[i][0]==nil:
		ans4="root"
	elif sn[i][1]==nil:
		ans4="leaf"
	else:
		ans4="internal node"
	ans4+=","
	print(ans1,ans2,ans3,ans4,child[i])

Submission status: Accepted

Solution code:
N = int(input())
childs = [[] for _ in range(N)]
parent = [-1 for _ in range(N)]
isleaf = [True for _ in range(N)]
for _ in range(N):
    i, k, *c = map(int, input().split())
    childs[i].extend(c)
    if k != 0:
        isleaf[i] = False
    for child in c:
        parent[child] = i

depth = [0 for _ in range(N)]


def dfs(cur):
    for child in childs[cur]:
        depth[child] = depth[cur] + 1
        dfs(child)


root = 0
while root < N:
    if parent[root] == -1:
        break
    else:
        root += 1
dfs(root)

for i in range(N):
    print('node {}: parent = {}, depth = {}, {}, {}'.format(
        i, parent[i], depth[i],
        'root' if i == root else 'leaf' if isleaf[i] else 'internal node',
        childs[i]))

Submission status: Accepted

Solution code:
n=int(input())
root=[i for i in range(n)]
oya_ko={}
ko_oya={}




#result[node]={[parent,[child]]}
for _ in range(n):
    temp=list(map(int,input().split()))
    #print(temp)
    node=temp[0]
    if temp[1]==0:
        child=[]
    else:
        child=temp[2:]

    oya_ko[node]=child

    for item in child:
        #print(root)
        ko_oya[item]=node
        root.remove(item)

depth={}

def makeDepth(x,y):
    depth[x]=y
    if oya_ko[x]==[]:
        return 0
    else:
        for item in oya_ko[x]:
            makeDepth(item,y+1)

makeDepth(root[0],0)
ko_oya[root[0]]=-1
"""
print(depth)
print(ko_oya)
print(oya_ko)
"""
for i in range(n):

    if i==root[0]:
        typ="root"
    elif oya_ko[i]==[]:
        typ="leaf"
    else:
        typ="internal node"
    print("node",str(i)+": parent =",str(ko_oya[i])+", depth =",str(depth[i])+",",typ+",",str(oya_ko[i]))

Submission status: Accepted

Solution code:
class Node():
    def __init__(self, value):
        self.value = value
        self.deep = -1
        self.parent = None
        self.left = None
        self.right = None
        self.childs = []

def setdeep(tree, i, deep):
    tree[i].deep = deep
    for child in tree[i].childs:
        tree[child].parent = i
        if child < len(tree):
            setdeep(tree, child, deep + 1)

if __name__ == '__main__':
    n = int(input())
    tree = {}

    for _ in range(n):
        datas = [int(num) for num in input().split(' ')]
        nodeid = datas[0]
        if nodeid not in tree.keys():
            tree[nodeid] = Node(nodeid)

        if datas[1] > 0:
            tree[nodeid].childs = datas[2:]
            for child in tree[nodeid].childs:
                if child not in tree.keys():
                    tree[child] = Node(child)
                tree[child].parent = nodeid


    for i in range(n):
        curnode = tree[i]
        if curnode.parent is None:
            # this is root
            setdeep(tree, i, 0)
            break
            
    
    for i in range(n):
        curnode = tree[i]
        if len(curnode.childs) == 0:
            nodetype = 'leaf'
        else:
            nodetype = 'internal node'
        if curnode.parent == None:
            nodetype = 'root'
            parent = -1
        else:
            parent = curnode.parent
        
        childs = curnode.childs
        print('node %d: parent = %d, depth = %d, %s, %s' % (i, parent,curnode.deep, nodetype, childs) )

Submission status: Accepted

Solution code:
N = int(input())

def get_parent(node):
    parent = -1
    if "parent" in node:
        return node["parent"]
    return parent

def get_depth(node):
    depth = 0
    while "parent" in node:
        depth += 1
        parent = node["parent"]
        node = rooted_tree[parent]
    return depth

def get_node_type(node):
    if "parent" not in node:
        return "root"
    if "left" not in node:
        return "leaf"
    return "internal node"

def get_children(node):
    if "left" not in node:
        return "[]"
    left = node["left"]
    siblings = []
    siblings.append(str(left))
    while rooted_tree[left]["right"] > -1:
        right = rooted_tree[left]["right"]
        siblings.append(str(right))
        left = right
    return "[{}]".format(", ".join(siblings))

        
rooted_tree = [{} for i in range(N)]
for _ in range(N):
    row = input() #0 3 1 4 10みたいにid k c1,...,ckが与えられる。
    id, k, *c = list(map(int, row.split()))
    if k > 0:
        #まずleftになる子供を設定。
        rooted_tree[id]["left"] = c[0]
        #親(id)から見て、各子供のrightになる兄弟を設定していく。さらにparentも親(id)と設定する。
        for i in range(len(c)):
            child_id = c[i]
            right = -1
            if i < len(c) - 1:
                right = c[i+1]
            rooted_tree[child_id]["right"]  = right
            rooted_tree[child_id]["parent"] = id

for id in range(N):
    node = rooted_tree[id]
    parent = get_parent(node)
    depth = get_depth(node)
    node_type = get_node_type(node)
    children = get_children(node)
    print("node {}: parent = {}, depth = {}, {}, {}".format(id, parent, depth, node_type, children))

Submission status: Accepted

Solution code:
def rootedTrees(node,parent,depth,name,root):
    A.append([node,parent,depth,name,root])
    for i in root:
        if len(B[i][1])!=0:
            rootedTrees(i,node,depth+1,"internal node",B[i][1])
        else:
            rootedTrees(i,node,depth+1,"leaf",B[i][1])

n=int(input())
A,B=[],[]
start=[i for i in range(n)]
for i in range(n):
    node,*root=map(int,input().split())
    B.append([node,root[1:]])
    for j in root[1:]:start.remove(j)

add=start[0]
B=sorted(B, key=lambda x:x[0])
rootedTrees(add,-1,0,"root",B[add][1])
for node,parent,depth,name,root in sorted(A):
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}"
    .format(node,parent,depth,name,root))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n=int(input())
    par=[-1]*n
    dep=[-1]*n
    typ=["internal node"]*n
    chi=[[] for _ in range(n)]
    for _ in range(n):
        u,deg,*child=map(int,input().split())
        if deg==0:typ[u]="leaf"
        chi[u]=child
        for cu in child:
            par[cu]=u
    root=par.index(-1)
    typ[root]="root"
    d=0
    now=[root]
    while now:
        nxt=[]
        for u in now:
            dep[u]=d
            nxt+=chi[u]
        now=nxt
        d+=1
    #print(par)
    #print(dep)
    #print(typ)
    #print(chi)
    for u in range(n):
        print("node {}: parent = {}, depth = {}, {}, {}".format(u,par[u],dep[u],typ[u],chi[u]))

main()

Submission status: Accepted

Solution code:

class Node:
    id = None
    depth = None
    degree = None
    parent = None
    children = None

    def __init__(self, id):
        self.id = id

    def __str__(self):
        if self.degree == 0:
            children_str = '[]'
        else:
            children_id = []
            for child in self.children:
                children_id.append(child.id)
            children_str = '[' + ', '.join(map(str, children_id)) + ']'

        return 'node {}: parent = {}, depth = {}, {}, {}'.format(self.id, self.parent, self.depth, self.get_type(), children_str)

    def get_type(self):
        if self.depth == 0:
            return 'root'
        elif self.degree == 0:
            return 'leaf'
        else:
            return 'internal node'

    def add_child(self, child):
        if self.children is None:
            self.children = []
            self.children.append(child)
        else:
            self.children.append(child)


def set_children_depth(node):
    if node.degree != 0:
        for child in node.children:
            child.depth = node.depth + 1
            set_children_depth(child)


n = int(input())

nodes = []
for i in range(n):
    nodes.append(Node(i))
# nodes[0].depth = 0
# nodes[0].parent = -1
#
# for i in range(n):
#     _ = list(map(int, input().split()))
#     nodes[i].degree = _[1]
#
#     if _[1] >= 1:
#         nodes[i].children = _[2:]
#         for j in range(_[1]):
#             nodes[_[j+2]].depth = nodes[i].depth + 1
#             nodes[_[j+2]].parent = i
#
# for i in range(n):
#     print(nodes[i])

for i in range(n):
    _ = list(map(int, input().split()))
    # print(_)
    id = _[0]
    nodes[id].degree = _[1]
    if _[1] >= 1:
        for j in range(_[1]):
            nodes[id].add_child(nodes[_[j+2]])
            nodes[_[j+2]].parent = id
    # print(nodes[i])

root_id = -1
for i in range(n):
    if nodes[i].parent is None:
        nodes[i].parent = -1
        nodes[i].depth = 0
        root_id = i
        break

# for i in range(n):
#     print(nodes[i])
#     print(nodes[i].degree)

set_children_depth(nodes[root_id])

for i in range(n):
    print(nodes[i])

Submission status: Accepted

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

nodes.sort(key=lambda x:int(x[0]))
ans={}
#parent
for i in range(n):
    if int(nodes[i][1]) >=1:
        for j in nodes[i][2:]:
            ans[j]=[nodes[i][0]]

for i in range(n):
    if str(i) not in ans:
        ans[str(i)]=[str(-1)]
        
#depth
for key,value in ans.items():
    depth=0
    x=value[0]
    while int(x) != -1:
        x=ans[x][0]
        depth+=1
    ans[key].append(str(depth))


#type,c
for key in ans.keys():
    ans[key].append(nodes[int(key)][2:])
    if ans[key][0] == '-1':ans[key].append('root')
    elif ans[key][2] == []:ans[key].append('leaf')
    else:ans[key].append('internal node')


for i in range(n):
    I=str(i)
    print('node '+I+': parent = '+ans[I][0]+', depth = '+str(ans[I][1])+', '+ans[I][3]+', ['+', '.join(ans[I][2])+']')

Submission status: Accepted

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


n = int(input())

node = {k: Node(-1, -1, -1) for k in range(n)}

for u in range(n):
    tmp = list(map(int, input().split()))
    if tmp[1] == 0:
        continue
    node[tmp[0]].left = tmp[2]
    node[tmp[2]].parent = tmp[0]
    prev_sibling = tmp[2] 
    for sib in tmp[3:]:
        node[prev_sibling].right = sib
        node[sib].parent = tmp[0]
        prev_sibling = sib

def get_depth(node, u):
    d = 0
    while node[u].parent is not -1:
        u = node[u].parent
        d += 1
    return d


def list_children(node, u):
    chilren = []
    c = node[u].left
    while c is not -1:
        chilren.append(c)
        c = node[c].right
    return chilren


for i in range(n):
    node_id = i
    node_parent = node[i].parent
    node_depth = get_depth(node, i)
    node_children = list_children(node, i)
 
    if node_parent == -1:
        node_type = "root"
    elif len(node_children) > 0 :
        node_type = "internal node"
    else:
        node_type = "leaf"

    print("node {}: parent = {}, depth = {}, {}, {}".format(node_id, node_parent, node_depth, node_type, node_children))

Submission status: Accepted

Solution code:
n=int(input())
c_list=[[]]*n
p_list=[-1]*n
for _ in range(n):
    id,k,*c=map(int,input().split())
    c_list[id]=c
    for i in c:
        p_list[i]=id
root=p_list.index(-1)
depth=[0]*n
next=c_list[root].copy()
while next:
    now=next.pop()
    depth[now]=depth[p_list[now]]+1
    next+=c_list[now]
for i in range(n):
    if i==root:
        type="root"
    elif c_list[i]==[]:
        type="leaf"
    else:
        type="internal node"
    print("node {}: parent = {}, depth = {}, {}, {}".format(i,p_list[i],depth[i],type,c_list[i]))

Submission status: Accepted

Solution code:
n = int(input())
lst = [list(map(int,input().split())) for i in range(n)]
B = [lst[i][0] for i in range(n)]
node = [[] for i in range(n)]

def Insertion_Sort(lst,B,n):
    for i in range(1,n):
        v = B[i]
        w = lst[i]
        j = i-1
        while j>=0 and B[j]>v:
            B[j+1]=B[j]
            lst[j+1]=lst[j]
            j-=1
        B[j+1]=v
        lst[j+1]=w
        
def find_root():
    A = []
    for i in range(n):
        A.extend(lst[i][2:])
    for i in range(n):
        if not i in A:
            return i

def make_node(arg_parent,arg_num, arg_depth):
    if arg_num == root:
        type = "root"
    elif lst[arg_num][1] == 0:
        type = "leaf"
    else:
        type = "internal node"
    children_lst = lst[arg_num][2:]
    node[arg_num] = [arg_parent, arg_depth, type, children_lst]
    for i in children_lst:
        make_node(arg_num, i, arg_depth+1)

Insertion_Sort(lst, B, n)
root = find_root()
make_node(-1, root, 0)

for i in range(n):
    parent, depth, type, children_lst = node[i]
    print(f"node {i}: parent = {parent}, depth = {depth}, {type}, {children_lst}")

Submission status: Accepted

Solution code:
class node:
    def __init__(self, parent, left, right, depth):
        self.p = parent
        self.l = left
        self.r = right
        self.d = depth

def getDepth(u):
    depth = 0
    c = u
    while T[c].p != -1:
        depth += 1
        c = T[c].p
    T[u].d = depth

def getChildren(u):
    c = T[u].l
    children = []
    while c != -1:
        children.append(c)
        c = T[c].r
    return children

n = int(input())
T = [node(-1, -1, -1, 0) for _ in range(n)]
for i in range(n):
    info = list(map(int, input().split(" ")))
    for j in range(info[1]):
        if j == 0:
            T[info[0]].l = info[2 + j]
        else:
            T[info[2 + j - 1]].r = info[2 + j]
        T[info[2 + j]].p = info[0]

for i in range(n):
    print("node", end = ' ')
    print(i, end = ': ')
    print("parent =", end = ' ')
    print(T[i].p, end = ', ')
    print("depth =", end = ' ')
    getDepth(i)
    print(T[i].d, end = ', ')
    if T[i].p == -1: print("root", end = ', ')
    elif T[i].l == -1: print("leaf", end = ', ')
    else: print("internal node", end = ', ')
    print(getChildren(i))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

tree = []
root_index = []
depths = []


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

    # 初期化
    for i in range(n):
        tree.append(Node(i, None, None))
        root_index.append(i)
        depths.append(0)

    for i in range(n):
        node_number, _, *c_list = list(map(int, input().split()))
        tree[node_number].child = c_list

        for c in c_list:
            tree[c].parent = tree[node_number]
            root_index.remove(c)

    root = tree[root_index[0]]
    root.parent = Node(-1, None, None)

    setDepth(root, 0)
    showTree(root)


def setDepth(node, d):
    depths[node.number] = d
    for c in node.child:
        setDepth(tree[c], d + 1)


def getDepth(node_number):
    return depths[node_number]


def showTree(root):
    for node in tree:
        type = ""
        if node.parent.number == -1:
            type = "root"
        elif len(node.child) == 0:
            type = "leaf"
        else:
            type = "internal node"

        print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(str(node.number), str(node.parent.number), str(depths[node.number]), type, node.child))


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/7/ALDS1_7_A
# 図参照
# 配列を3つ用意してもよいがここではクラスを定義する。
# 本ではNILを-1としていたがここではNoneとして実装する（どっちのほうがいいんだろう）

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: dict, u: int):
    '''
    Tは木の構造と見立てたdict
    uはTのノード
    '''
    d = 0
    while T[u].parent is not None:
        u = T[u].parent
        d += 1  # 親をたどりながら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):
    chilren = []
    c = T[u].left
    while c is not None:
        chilren.append(c)
        c = T[c].right
    return chilren

# 答え出力用


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}')


# この問題は入力をNoneに適する形に整形するのも少し難しい
n = int(input())

T = {k: Node(None, None, None) for k in range(n)}  # pythonぽくないけど初期化
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_sibling = tmp[2]  # 前のノード番号を覚えておく用
    for sib in tmp[3:]:
        T[prev_sibling].right = sib
        T[sib].parent = tmp[0]  # 子から親を与えている
        prev_sibling = sib

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

# print(n)
# print(T)
# print(D)

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

Submission status: Accepted

Solution code:
"""
根付き木の表現

 [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

[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, []
"""

class Node():
    def __init__(self, id, children):
        self.id = id
        self.children = children
        self.parent = -1
        self.type = "internal node"
        self.right_sibling = None
        self.depth = None
        # self.left_child = children[0] if children != None else None

    def set_parent(self):
        if len(self.children) != 0:
            for child_id in self.children:
                node_list[child_id].parent = self.id
        else:
            self.type = "leaf"
        
    def set_depth(self):
        depth = 0
        node = self
        while node.parent != -1:
            node = node_list[node.parent]
            depth += 1

        if depth == 0:
            self.type = "root"
        self.depth = depth

    # def print_children(self):
    #     child = self.left_child
    #     while child != None:
    #         print(child.id)
    #         child = child.right_sibling




if __name__=="__main__":
    N = int(input())
    node_list = [None] * N
    for i in range(N):
        input_list = list(map(int, input().split()))
        id = input_list[0]
        children_num = input_list[1]
        children = input_list[2:] if children_num != 0 else []
        node_list[id] = Node(id, children)

    for n in node_list:
        n.set_parent()

    for n in node_list:
        n.set_depth()

    # from pprint import pprint
    # for n in node_list:
    #     pprint(vars(n))

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

Submission status: Accepted

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

global nodes

def setDepth(id, depth):
	nodes[id].depth = depth
	for child_id in nodes[id].child:
		setDepth(child_id, depth + 1)

if __name__ == "__main__":
	n = int(input())
	nodes = []
	for _ in range(n):
		nodes.append(Node())
	for _ in range(n):
		table = list(map(int, input().split()))
		id = table[0]
		child_num = table[1]
		for k in range(child_num):
			child_id = table[k + 2]
			nodes[id].child.append(child_id)
			nodes[child_id].parent = id
	for i in range(n):
		if nodes[i].parent == -1:
			nodes[i].type = "root"
			rootid = i
		elif nodes[i].child == []:
			nodes[i].type = "leaf"
	setDepth(rootid, 0)

	for i in range(n):
		print(f"node {i}: parent = {nodes[i].parent}, depth = {nodes[i].depth}, {nodes[i].type}, {nodes[i].child}")

Submission status: Accepted

Solution code:
class node():
    def __init__(self, id, parent, child, depth, type_t):
        self.id = id
        self.parent = parent
        self.child = child
        self.depth = depth
        self.type_t = type_t


def add(t, d, i, parent, depth):
    type_t = 'internal node'
    if d[i][1] == 0:
        type_t = 'leaf'
    if depth == 0:
        type_t = 'root'

    child = []
    if not d[i][1] == 0:
        child = d[i][2:]
    new_node = node(i, parent, d[i][2:], depth, type_t)
    t.append(new_node)
    for c in child:
        add(t, d, c, i, depth + 1)


N = int(input())
tree = []
data = [[] for i in range(N)]
for i in range(N):
    data[i] = [int(i) for i in input().split()]

data.sort(key=lambda x: x[0])

root = [True for i in range(N)]
for d in data:
    for c in d[2:]:
        root[c] = False

for i in range(N):
    if root[i]:
        add(tree, data, i, -1, 0)

tree.sort(key=lambda x: x.id)

for t in tree:
    print(f'node {t.id}: parent = {t.parent}, depth = {t.depth}, {t.type_t}, {t.child}')

Submission status: Accepted

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

class Element:
    def __init__(self, node):
        self.node = node
        self.parent = -1
        self.depth = 0
        self.status = "internal node"
        self.children = None
    
    def display(self):
        print("node %d: parent = %d, depth = %d, %s, %s"
        %(self.node, self.parent, self.depth, self.status, str(self.children)))
        
N = int(input())

NODE_DICT = {}
ROOT_SEARCH = [True]*N

for loop in range(N):
    DATA = list(map(int, input().split()))
    node = DATA[0]    
    tmp = Element(node)
    tmp.children = DATA[2:]
    NODE_DICT[node] = tmp
    for i in tmp.children:
        ROOT_SEARCH[i] = False
    
#for node in NODE_DICT.keys():
#    for child in NODE_DICT[node].children:
#        ROOT_SEARCH[child] = False


for key in range(len(ROOT_SEARCH)):
    if ROOT_SEARCH[key]:
        root = key

def Process(parent):
    for child in parent.children:
        NODE_DICT[child].parent = parent.node
        NODE_DICT[child].depth = parent.depth + 1
    if parent.children == []:
        parent.status = "leaf"
    else:
        for child in parent.children:
            Process(NODE_DICT[child])
    

Process(NODE_DICT[root])
NODE_DICT[root].status = "root"

for i in range(N):
    NODE_DICT[i].display()

#for node in range(len(NODE_DICT)):
#    print("node %d: parent = %d, depth = %d, %s, %s"%(NODE_DICT[node].node, 
#    NODE_DICT[node].parent, NODE_DICT[node].depth, NODE_DICT[node].status, 
#   str(NODE_DICT[node].children)))

Submission status: Accepted

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

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())
global nodes
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:
n = int(input())

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

class Tree:
    def __init__(self, n):
        # n : ノード数
        self.nodes = {node: {'parent': None, 'children': [], 'depth': None} for node in range(n)}
        
    def add_node_with_child(self, node, childlen):
        for c in childlen:
            self.nodes[node]['children'].append(c)
            self.nodes[c]['parent'] = node
    
    def get_parent(self, node):
        return self.nodes[node]['parent']
    
    def get_children(self, node):
        return self.nodes[node]['children']
        
    def get_depth(self, node):
        if self.nodes[node]['depth'] != None:
            return self.nodes[node]['depth']
        elif self.nodes[node]['parent'] == None:
            self.nodes[node]['depth'] = 0
            return 0
        else:
            depth = self.get_depth(self.nodes[node]['parent']) + 1
            self.nodes[node]['depth'] = depth
            return depth

            
RootedTree = Tree(n)
for t in T:
    if t[1] == 0:
        continue
        
    node = t[0]
    childlen = t[2:]
    RootedTree.add_node_with_child(node, childlen)
    
#print(RootedTree.nodes)

for node in range(n):
    parent = RootedTree.get_parent(node)
    if parent == None:
        parent = -1
    depth = RootedTree.get_depth(node)
    childlen = RootedTree.get_children(node)
    childlen = ', '.join(list(map(str, childlen)))
    
    if parent == -1:
        node_type = 'root'
    elif childlen == '':
        node_type = 'leaf'
    else:
        node_type = 'internal node'
    
    print('node {}: parent = {}, depth = {}, {}, [{}]'.format(node, parent, depth, node_type, childlen))