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:
from collections import deque
import sys
sys.setrecursionlimit(100000)

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

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

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

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

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

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

set_depth(root)

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

Submission status: Accepted

Solution code:
n = int(input())
nodes = [0 for i in range(n)]
output = [None for i in range(n)]
cnt = 0
root = set(range(n))
for i in range(n):
    id, _, *li = list(map(int, input().split(' ')))
    root -= set(li)
    nodes[id] = li

def rooted_tree(id, depth, parent):
    out = {}
    out['node'] = id
    out['parent'] = parent
    out['depth'] = depth
    out['c'] = nodes[id]
    if depth == 0:
        out['type'] = 'root'
    elif len(nodes[id]) == 0:
        out['type'] = 'leaf'
    else:
        out['type'] = 'internal node'
    output[id] = out
    for i in (nodes[id]):
        rooted_tree(i, depth+1, id)

rooted_tree(root.pop(), 0, -1)
for line in output:
    print("node {}: parent = {}, depth = {}, {}, {}".format(line['node'], line['parent'], line['depth'], line['type'], line['c']))

Submission status: Accepted

Solution code:
import sys

n = int(input())
ary = [[int(_) for _ in line.strip().split()] for line in sys.stdin]
# ary = [[int(_) for _ in input().split()] for i in range(n)]
ary.sort(key=lambda x: x[0])


def output(i, p, d, t, ch):

    print('node {}: parent = {}, depth = {}, {}, {}'.format(i, p, d, t, ch))


bry = [{
    'id': i,
    'parent': -1,
    'depth': 0,
    'type': 'root',
    'children': []
} for i in range(n)]
for node in ary:
    no = node[0]
    if node[1]:
        for cno in node[2:]:
            bry[no]['children'].append(cno)
            bry[cno]['parent'] = no
            if ary[cno][1]:
                bry[cno]['type'] = 'internal node'
            else:
                bry[cno]['type'] = 'leaf'
    else:
        if n > 1:
            bry[no]['type'] = 'leaf'

tmp = [(node['id'], node['parent']) for node in bry]
root = [min(tmp, key=lambda x: x[1])[0]]
flag = True
while flag:
    flag = False
    tmp = []
    for i in root:
        for cno in bry[i]['children']:
            bry[cno]['depth'] = bry[i]['depth'] + 1
            tmp.append(cno)
            flag = True
    root = tmp

for node in bry:
    output(node['id'], node['parent'], node['depth'], node['type'],
           node['children'])

Submission status: Accepted

Solution code:
class Tree:
    def __init__(self, ary):
        self.nodes = [
            Node(node, self) for node in sorted(ary, key=lambda x: x[0])
        ]
        [node.set() for node in self.nodes]
        for node in self.nodes:
            if node.parent == -1:
                node.set_depth(0)
                break

    def output(self):
        [node.output() for node in self.nodes]


class Node:
    def __init__(self, node, tree):
        self.tree = tree
        self.no = node[0]
        self.parent = -1
        self.right = False
        self.left = False
        self.children = node[2:]

    def set(self):
        if self.children:
            for i, child in enumerate(self.children):
                self.tree.nodes[child].parent = self.no
                if i < len(self.children) - 1:
                    self.tree.nodes[child].right = self.children[i + 1]
                self.left = self.children[0]

    def set_depth(self, d):
        self.depth = d
        if type(self.right) != bool:
            self.tree.nodes[self.right].set_depth(d)
        if type(self.left) != bool:
            self.tree.nodes[self.left].set_depth(d + 1)

    def output(self):
        if self.parent == -1:
            kind = 'root'
        elif not self.children:
            kind = 'leaf'
        else:
            kind = 'internal node'

        print('node {}: parent = {}, depth = {}, {}, {}'.format(
            self.no, self.parent, self.depth, kind, self.children))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10 ** 6)

    n = int(input())
    ary = [[int(_) for _ in line.strip().split()] for line in sys.stdin]
    # ary = [[int(_) for _ in input().split()] for i in range(n)]
    tree = Tree(ary)
    tree.output()

Submission status: Accepted

Solution code:
#coding:utf-8

n = int(input())
T = [list(map(int, input().split())) for i in range(n)]
A = []
def parentSearch():
    numList = []
    for t in T:
        if t[1] != 0:
            for num in t[2:]:
                numList.append(num)
    numList.sort()
    for i in range(n-1):
        if numList[i] != i:
            return i


def rootedTrees(node, parent, depth):
    t = T[node]
    if t[1] != 0:
        if parent == -1:
            kind = "root"
        else:
            kind = "internal node"
        A.append([t[0], parent, depth, kind, t[2:]])
        parent = node
        for i in t[2:]:
            rootedTrees(i, parent, depth+1)
    else:
        if parent == -1:
            kind = "root"
        else:
            kind = "leaf"
        A.append([t[0], parent, depth, kind, []])


def Merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append([510000])
    R.append([510000])
    i,j = 0,0
    for k in range(left,right):
        if L[i][0] <= R[j][0]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def MergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right)//2
        MergeSort(A, left, mid)
        MergeSort(A, mid, right)
        Merge(A, left, mid, right)

MergeSort(T, 0, n)
node = parentSearch()
if node == None:
    node = 0
depth = 0
parent = -1
rootedTrees(node, parent, depth)
MergeSort(A, 0, n)

for t in A:
    print("node {}: parent = {}, depth = {}, {}, {}".format(t[0],t[1],t[2],t[3],t[4]))

Submission status: Accepted

Solution code:
n = int(input())
node_info_list = [0 for i in range(n)]
for i in range(n):
    node_info_raw = list(map(int, input().split()))
    node_info_list[node_info_raw[0]] = {
        'degree': node_info_raw[1],
        'children_ids': [],
        'parent': -1,
        'depth': 0,
        'type': 'root'
    }
    if node_info_list[node_info_raw[0]]['degree'] >= 1:
        node_info_list[node_info_raw[0]]['children_ids'] = node_info_raw[2:]

def know_parent_type():
    for id, node_info in enumerate(node_info_list):
        for child_id in node_info['children_ids']:
            node_info_list[child_id]['parent'] = id
            node_info_list[child_id]['type'] = 'internal node'
            if node_info_list[child_id]['children_ids'] == []:
                node_info_list[child_id]['type'] = 'leaf'

def know_depth(id):
    if node_info_list[id]['parent'] == -1:
        return 0
    else:
        return (1 + know_depth(node_info_list[id]['parent']))

know_parent_type()
for id, node_info in enumerate(node_info_list):
    node_info['depth'] = know_depth(id)
    print('node {}: parent = {}, depth = {}, {}, {}'.format(
    id,
    node_info_list[id]['parent'],
    node_info_list[id]['depth'],
    node_info_list[id]['type'],
    node_info_list[id]['children_ids']
    )
    )

Submission status: Accepted

Solution code:
def search(ps, id):
    if ps[id] == -1:
        return 0
    else:
        return 1 + search(ps, ps[id])


n = int(input())
tree = [[] for _ in range(n)]
ps = [-1 for _ in range(n)]
for _ in range(n):
    s = input().split()
    id = int(s[0])
    k = int(s[1])
    children = [int(x) for x in s[2:]]
    tree[id] = children
    for child in children:
        ps[child] = id

for id in range(n):
    p = ps[id]
    d = search(ps, id)
    c = tree[id]
    if p == -1:
        type = "root"
    elif len(c) == 0:
        type = "leaf"
    else:
        type = "internal node"

    print("node " + str(id) + ": parent = " + str(p) + ", depth = " + str(d) + ", " + type + ",", c)

Submission status: Accepted

Solution code:
from typing import List

class Node:
    def __init__(self, node_id, parent_id):
        self.node_id = node_id
        self.parent_id = parent_id
        self.children = []
        
        self.depth = None
        self.node_type =None

    def __str__(self):
        return str(self.node_id)
    def __repr__(self):
        return self.__str__()
        
    
class Tree:
    def __init__(self, n):
        self.root = None
        self.n_node = n
        self.node_list = [None for _ in range(n)]
    
    def find_node(self, node_id: int):
        if self.node_list[node_id] != None:
            return self.node_list[node_id]
        return None
    
    def add_children_from_ids(self, node_id: int, children_ids: List[int]):
        # check parent already exists
        parent_node = self.find_node(node_id)
        if parent_node == None:
            # create new node from parent_id
            parent_node = Node(node_id = node_id, parent_id = -1)
            self.node_list[node_id] = parent_node
            
        if len(children_ids) > 0:
            # add all the children (unregistered)
            # register parent_id, node_id, children
            for child_id in children_ids:
                child_node = self.find_node(child_id)
                
                if child_node == None:
                    child_node = Node(node_id = child_id, parent_id = node_id)
                else:
                    child_node.parent_id = node_id
                    
                parent_node.children.append(child_node)
                self.node_list[child_id] = child_node
    
    def overwrite_node_type(self):
        # find root and overwrite node type
        
        for node in self.node_list:
            # root, internal node, leaf
            if node.parent_id == -1:
                node_type = "root"
                self.root = node
            else:
                if node.children != []:
                    node_type = "internal node"
                else:
                    node_type = "leaf"
                    
            node.node_type = node_type

    def overwrite_depth(self, node, depth):
        if node.children == []:
            node.depth = depth
            # print("node.id: ", node.node_id, ",  node.depth: ", node.depth)
            return None
        else:
            node.depth = depth
            for child_node in node.children:
                self.overwrite_depth(child_node, depth+1)
        return None

    def print_nodes(self):
        for node in self.node_list:
            print("node {}: parent = {}, depth = {}, {}, {}".format(
                node.node_id, node.parent_id, node.depth, node.node_type, node.children
            ))            
  
def main():
    n = int(input())
    tree = Tree(n)
    for _ in range(n):
        node_id, k, *children = map(int, input().split())
        tree.add_children_from_ids(node_id = node_id, children_ids = children)
    tree.overwrite_node_type()

    tree.overwrite_depth(tree.root, 0)
    tree.print_nodes()    
main()

Submission status: Accepted

Solution code:
Parent = 0
Lchild = 1
Rsibling = 2
Clist = 3

def depth(n):
    i = node[n][Parent]
    if i == -1:
        return 0
    else:
        return depth(i) + 1

def nt(n):
    if node[n][Parent]== -1:
        return 'root'
    elif node[n][Lchild]== -1:
        return 'leaf'
    else:
        return 'internal node'
    return

n = int(input())
node = [[-1, -1, -1, []] for i in range(n)]
for i in range(n):
    tmp = map(int, raw_input().split())
    j = tmp[0]
    rank = tmp[1]
    if rank > 0:
        childs = tmp[2:]
        node[j][Clist] = childs
        p1 = 0
        c1 = childs[p1]
        node[j][Lchild] = c1
        node[c1][Parent] = j
        for p2 in range(1, rank):
            c2 = childs[p2]
            node[c2][Parent] = j
            node[c1][Rsibling] = c2
            c1 = c2

for i in range(n):
    msg = 'node {0}: parent = {1}, depth = {2}, {3}, {4}'
    print msg.format(i, node[i][Parent], depth(i), nt(i), node[i][Clist])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin

FORMAT = ('node {0.id}: parent = {0.parent}, depth = {0.depth},'
          ' {0.kind}, {0.childs}').format


class Node(object):
    def __init__(self, node):
        self.depth = 0
        self.parent = -1
        self.id = node[0]
        self.degree = node[1]
        self.kind = 'internal node' if node[1] else 'leaf'
        self.childs = node[2:]

    def __str__(self):
        return FORMAT(self)


def calc_depth(tree, i):
    for j in tree[i].childs:
        tree[j].depth += 1
        calc_depth(tree, j)


n = int(stdin.readline())
tree = [-1] * n
#assert 1 <= n <= 100000
for _ in range(n):
    node = Node([int(s) for s in stdin.readline().split()])
    i = node.id
    node.parent = tree[i]
    for j in node.childs:
        if isinstance(tree[j], int):
            tree[j] = i
        else:
            tree[j].parent = i
    tree[i] = node

for i in range(n):
    calc_depth(tree, i)

for i, node in enumerate(tree):
    if node.parent == -1:
        node.kind = 'root'
    print(node)

Submission status: Accepted

Solution code:
n = int(input())
def getDepth(n):
    p = n[0]
    c = 0
    while p != -1:
        c += 1
        p = lst[p][0]

    return str(c)


lst = []
for i in range(n):
    lst.append([-1])
for i in range(n):
    s = list(map(int, input().split()))
    for j in s[2:2+s[1]]:
        lst[j][0] = s[0]
        lst[s[0]].append(j)

for i in range(n):
    k = ', internal node'
    if len(lst[i]) == 1:
        k = ', leaf'

    if lst[i][0] == -1:
        k = ', root'

    print('node ' + str(i) + ': parent = ' + str(lst[i][0]) + ', depth = ' + getDepth(lst[i]) + k + ',', end= ' ')
    print(lst[i][1:])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2**20)

class Node():
    def __init__(self):
        self.p = None
        self.l_ch = None
        self.r_si = None

def SetDepth(u, p):
    D[u] = p
    if T[u].r_si != None:
        SetDepth(T[u].r_si, p)
    if T[u].l_ch != None:
        SetDepth(T[u].l_ch, p+1)

def SetAttribute():
    for i in range(n):
        if T[i].p == -1:
            A[i] = 'root'
        elif T[i].l_ch == None:
            A[i] = 'leaf'
        else:
            A[i] = 'internal node'

n = int(input())
T = [None] * n
for i in range(n):
    temp = Node()
    T[i] = temp
C = [[] for i in range(n)]

for i in range(n):
    L = [int(x) for x in input().split()]
    v, d = L[0], L[1]
    C[v] = L[2:]
    for j, c in enumerate(L[2:]):
        if j == 0:
            T[v].l_ch = c
        else:
            T[l].r_si = c
        l = c
        T[c].p = v

D = [0] * n
for i in range(n):
    if T[i].p == None:
        T[i].p = -1
        r = i
SetDepth(r, 0)

A = [''] * n
SetAttribute()

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

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: dict, u: int):
    """
    T: 木構造
    u: ノード番号
    """
    d = 0
    while T[u].parent is not None:
        u = T[u].parent
        d += 1

D = {} #深さを保存

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) #1つ深く潜る

def ret_children(T: dict, u: int):
    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):
    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)
        # 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)  # 再帰回数上限の向上 かなり多くしないと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):
    '''
    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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
class Node:
    def __init__(self):
        self.parentId=-1
        self.depth=0
        self.children=[]
n=int(input())
u=[[int(i)for i in input().split()]for j in range(n)]

nodes=[Node() for i in range(n)]
for i in u:
    for j in range(i[1]):
        nodes[i[0]].children.append(i[2+j])
        nodes[i[2+j]].parentId=i[0]

def calcDepth(id,depth):
    global nodes
    nodes[id].depth=depth
    for i in nodes[id].children:
        calcDepth(i,depth+1)

for i in range(n):
    if nodes[i].parentId==-1:
        calcDepth(i,0)
        break

for i in range(n):
    a="node "+str(i)+": parent = "+str(nodes[i].parentId)+", depth = "+str(nodes[i].depth)
    if nodes[i].depth==0:
        a=a+", root, ["+", ".join(map(str,nodes[i].children))+"]"
    elif len(nodes[i].children)==0:
        a=a+", leaf, []"
    else:
        a=a+", internal node, ["+", ".join(map(str,nodes[i].children))+"]"
    print(a)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, id_num):
        self.id = id_num
        self.parent = None
        self.children = []
    def get_type(self):
        if self.parent is None:
             return 'root'
        if self.children == []:
             return 'leaf'
        else:
             return 'internal node'
             
def get_depth(node, nodes):
    depth = 0
    parent = node.parent
    while parent is not None:
        depth += 1
        parent = nodes[parent].parent
    return depth
 
n = int(input())
nodes = {}
for i in range(n):
    input_line = list(map(int , input().split(' ')))
    id = input_line[0]
    children = input_line[2:]
    if id not in nodes:
        node = Node(id)
        node.children = children
        nodes[id] = node
    else:
        nodes[id].children = children
    for ch in children:
        if ch not in nodes:
            ch_node = Node(ch)
            nodes[ch] = ch_node
            nodes[ch].parent = id
        else:
            nodes[ch].parent = id
for id in sorted(nodes):
    node = nodes[id]
    parent = node.parent
    if node.parent is None:
         parent = -1
    depth = get_depth(node, nodes)
    type = node.get_type()
    print('node {}: parent = {}, depth = {}, {}, {}'.format(id, parent, depth, type, node.children))

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: dict, u: int):
    #Tは木の構造と見立てたdictで、uはTのノード
    d = 0
    while T[u].parent is not None:
        u = T[u].parent
        d += 1

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'
    #parentを決める
    if T[node].parent == 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)}
#全てのleft,right,parentを決める
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_sibiling = tmp[2] #前のノードを覚えておくよう
    #print (tmp)
    for sib in tmp[3:]:
        #print (prev_sibiling,sib)
        T[prev_sibiling].right = sib
        T[sib].parent = tmp[0]  # 子から親を与えている
        prev_sibiling = sib

#print(T[1].right)

for node in range(n):
    #rootからｋ考えなければいけない
    if T[node].parent == None:
        get_all_depth(T,node,0)
        break
    #Dに深さが入った

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.children = []

def cal_depth(node_id, d = 0):
    Tree[node_id].depth = d
    for child in Tree[node_id].children:
        cal_depth(child, d+1)
    
N = int(input())
Tree = [Node() for _ in range(N)]

#make_tree
for _ in range(N):
    #id, 子供の数k, c_0~c_k
    tree_info = list(map(int, input().split()))
    node_id = tree_info[0]
    k = tree_info[1]
    if k > 0:
        children = tree_info[2:]
        Tree[node_id].children = children
        Tree[node_id].type = "internal node"
    else:
        Tree[node_id].type = "leaf"
        
    for child in Tree[node_id].children:
        Tree[child].parent = node_id

#search_root
root_id =[i for i,t in enumerate(Tree) if t.parent == -1][0]
Tree[root_id].type = "root"
cal_depth(root_id)


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

Submission status: Accepted

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

global nodes

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

n = int(input())
nodes = []
for l in range(n):
    node = Node()
    nodes.append(node)
for l in range(n):
    a = list(map(int,input().split()))
    node_id = a[0]
    num = a[1]
    for i in range(num):
        child_id = a[2+i]
        nodes[node_id].children.append(child_id)
        nodes[child_id].parent_id = node_id
    
for i in range(n):
    if nodes[i].parent_id == -1:
        calc_depth(i,0)
        break

for i in range(n):
    print("node {0}: parent = {1}, depth = {2}, ".format(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("]")