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:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def get_depth(parent, node):
    depth = 0
    n = node
    while True:
        if parent[n] == -1: break
        n = parent[n]
        depth += 1

    return depth


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    parent = [-1] * N
    children = collections.defaultdict(list)

    for n in range(N):
        id, k, *C = il()
        for c in C:
            children[id].append(c)
            parent[c] = id

    for node in range(N):
        depth = get_depth(parent, node)
        type = ''
        if parent[node] == -1:
            type = 'root'
        elif len(children[node]) > 0:
            type = 'internal node'
        else:
            type = 'leaf'

        print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(node, parent[node], depth, type, children[node]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class RootedTree:
    class Node:
        def __init__(self):
            self.parent = -1
            self.depth = 0
            self.children = []
            
            
    def __init__(self, n):
        self.nodes_num = n
        self.nodes = [None] * n
        for i in range(self.nodes_num):
            node = self.Node()
            self.nodes[i] = node


    def load(self, node_info):
        for _node_info in node_info:
            node_num = _node_info[0]
            if len(_node_info) > 2:
                self.nodes[node_num].children = _node_info[2:]
            else:
                self.nodes[node_num].children = []
            for child in self.nodes[node_num].children:
                self.nodes[child].parent = node_num


    def _calc_depth(self, p):
        if self.nodes[p].parent == -1:
            return 0
        return 1 + self._calc_depth(self.nodes[p].parent) 

    
    def calc_depth(self):
        for i in range(self.nodes_num):
            self.nodes[i].depth = self._calc_depth(i)

    
    def print_nodes(self):
        for i in range(self.nodes_num):
            if self.nodes[i].parent == -1:
                type = 'root'
            elif len(self.nodes[i].children) == 0:
                type = 'leaf'
            else:
                type = 'internal node'
            print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(i, self.nodes[i].parent, self.nodes[i].depth, type, self.nodes[i].children))



if __name__ == '__main__':
    n = int(input())
    rt = RootedTree(n)
    node_info = []
    for _ in range(n):
        node_info.append(list(map(int, input().rstrip().split())))
    rt.load(node_info)
    rt.calc_depth()
    rt.print_nodes()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


def main():
    n = int(input().strip())
    tree = defaultdict(list)
    parent = [-1] * n

    for i in range(n):
        line = [int(j) for j in input().strip().split()]
        tree[line[0]] += line[2:]
        for j in line[2:]:
            parent[j] = line[0] 

    depth = [9999] * n
    _root = parent.index(-1)
    depth[_root] = 0

    def fill_depth(tree, n, d):
        depth[n] = d
        links = tree[n]
        for l in links:
            fill_depth(tree, l, d + 1)
    
    fill_depth(tree,_root,0)
    
    def get_attr(tree, n, root):
        if n == root:
            return "root"
        elif len(tree[n]) > 0:
            return "internal node"
        else:
            return "leaf"
    
    for i in range(n):
        print("node {}: parent = {}, depth = {}, {},".format(i,parent[i],depth[i],get_attr(tree,i,_root)),tree[i])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import queue
from collections import namedtuple
U = namedtuple("U", "id parent depth type children")
n = int(input())

dic, link = [dict() for _ in range(2)]
se = set([int(x) for x in range(n)])

for i in range(n):
    tmp = list(map(int, input().split()))
    tmp.reverse()

    a, k = [tmp.pop() for _ in range(2)]
    link[a] = []
    for j in range(k):
        b = tmp.pop()
        link[a].append(b)

        se.remove(b)


def bfs(s):
    q = queue.Queue()
    q.put(U(s, -1, 0, "root", link[s]))

    while q.qsize() != 0:
        u0 = q.get()
        dic[u0.id] = u0

        for u1 in u0.children:
            children = link[u1]
            node_type = "leaf" if children == [] else "internal node"
            q.put(U(u1, u0.id, u0.depth + 1, node_type, children))


bfs(se.pop())

for i in range(n):
    print("node", dic[i].id, end="")
    print(": parent =", dic[i].parent, end="")
    print(", depth =", dic[i].depth, end="")
    print(",", dic[i].type, end="")
    print(",", dic[i].children)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
class Tree:
    def __init__(self, parent, left_child, right_sib):
        self.left_child = left_child
        self.right_sib = right_sib
        self.parent = parent
    

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

def getChildren(T, u):
    Children = []
    c = T[u].left_child
    while c is not None:
        Children.append(str(c))
        c = T[c].right_sib
    if len(Children) != 0:
        return "[" + ", ".join(Children) + "]"
    else:
        return "[]"

n = int(input().rstrip())

T = []
for _ in range(n):
    T.append(Tree(None, None, None))

for _ in range(n):
    inputs = list(map(int, input().rstrip().split(" ")))
    u = inputs[0]
    k = inputs[1]
    children = inputs[2:] if k > 0 else [None]
    T[u].left_child = children[0]
    if k > 0:
        for i, child in enumerate(children):
            T[child].parent = u
            T[child].right_sib = children[i+1] if i+1 < len(children) else None

def print_info(T, u):
    parent = T[u].parent
    if parent is None:
        parent = -1
    depth = getDepth(T, u)
    children = getChildren(T, u)
    type_ = "root" if parent == -1 else "leaf" if children == "[]" else "internal node"
    
    print("node {}: parent = {}, depth = {}, {}, {}".format(u, parent, depth, type_ ,children if type_ != "leaf" else "[]"))

for u in range(n):
    print_info(T, u)

Submission status: Accepted

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

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

def get_depth(T:dict,u:int):
    d = 0
    while T[u] != -1:
        u = T[u].parent
        d += 1

D = {}

def get_all_depth(T:dict,u:int,p:int):
    D[u] = p
    if T[u].right != -1:
        get_all_depth(T, T[u].right, p)
    if T[u].left != -1:
        get_all_depth(T,T[u].left,p+1)

def ret_children(T,u):
    children = []
    c = T[u].left
    while c != -1:
        children.append(c)
        c = T[c].right
    return children

def print_for_a_node(T:dict,node:int,D:dict):
    node_type = "leaf" if T[node].left == -1 else "internal node"
    if T[node].parent == -1:
        node_type = "root"
    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(-1,-1,-1) 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 == -1:
        get_all_depth(T,node,0)
        break

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

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline().rstrip())  # 節点数

parents = [None] * N
depth = [None] * N
type_ = [None] * N
children = [None] * N

CHs = [None] * N


# ## DFS ## #


def dfs(u, d, r=-1):

    # u を訪れたときの処理
    # parents[u] = r
    depth[u] = d
    c = []
    tmp = "leaf"

    for v in CHs[u]:
        if v == r:
            continue  # 親は無視
        tmp = "internal node"
        dfs(v, d + 1, u)  # 子の探索
        c.append(v)

    # u を離れる前の処理
    if r == -1:
        tmp = "root"
    type_[u] = tmp
    children[u] = c


def main():
    for i in range(N):
        id, k, *ch = map(int, sys.stdin.readline().rstrip().split())
        for p in ch:
            parents[p] = id
        CHs[id] = ch

    # 根を見つける
    u = 0
    while True:
        if parents[u] is None:
            root = u
            parents[u] = -1
            break
        u = parents[u]

    dfs(root, 0)

    for i in range(N):
        print(f"node {i}: parent = {parents[i]}, depth = {depth[i]}, {type_[i]}, {children[i]}")


main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)

class Node:
  def __init__(self,p,l,r):
    self.p=p
    self.l=l
    self.r=r

def getDepth(u):
  #d=0
  #while T[u].parent!=None:
  #  u=T[u].parent
  #  d+=1
  #return d
  return D[u]

def setDepth(u,p):
  global D
  D[u]=p
  if T[u].r!=-1:
    #print("debug:",T[u].r)
    setDepth(T[u].r,p)
  if T[u].l!=-1:
    setDepth(T[u].l,p+1)

def getChildren(u):
#def printChildren(u):
  C=[]
  c=T[u].l
  while c!=-1:
    #print(c,end=', ')
    C.append(str(c))
    c=T[c].r
  return C

n=int(input())
#T=[Node(-1,-1,-1)]*n
T=[Node(-1,-1,-1) for _ in range(n)]
for _ in range(n):
  C=list(map(int,input().split()))
  if C[1]>0:
    T[C[0]].l=C[2]
  k=C[1]
  for i in range(2,k+2):
    T[C[i]].p=C[0]
    if i+1<k+2:
      T[C[i]].r=C[i+1]

#for i in range(n):
#  print(i,":",T[i].r)
#exit(0)

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

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

Submission status: Accepted

Solution code:
n = int(input())
depths = [0] * n
parents = [-1] * n
nodes = [0] * n
children = [0] * n
childs = []
parts = ['leaf'] * n
numall = []

for i in range(n):
    numall.append(list(map(int, input().split())))
    
numall.sort()
for i in range(n):
    nums = numall[i]
    nodes[i] = int(nums[0])
    children[i] = int(nums[1])
    child = [int(s) for s in nums[2:]]
    childs.append(child)
    if child != []:
        parts[i] = 'internal node'
        for j in child:
            parents[j] = i

root = 0
for i in range(n):
    if parents[i] == -1:
        parts[i] = 'root'
        root = i
        break

li = [root]
i = 0
while len(li) < n:
    for j in childs[li[i]]:
        li.append(j)
        depths[j] = depths[li[i]] + 1
    i += 1
      
answer = []
for i in range(n):
    answer.append([nodes[i], parents[i], depths[i], parts[i], childs[i]])
  
answer.sort()
for ans in answer:
    print(('node ' + str(ans[0]) + ': parent = ' + str(ans[1]) + ', depth = ' + str(ans[2]) + ', ' + ans[3] + ', '), end='')
    print(ans[4])

Submission status: Accepted

Solution code:
class Node:
    def __init__(self):
        self.parent = -1
        self.depth = 0
        self.children = []
    def setDepth(self, depth):
        global t
        self.depth = depth
        for no in self.children:
            t[no].setDepth(depth + 1)

n = int(input())
t = [Node() for i in range(n)]
for i in range(n):
    id, k, *lst = map(int, input().split())
    t[id].children = lst
    for j in lst:
        t[j].parent = id
for i in range(n):
    if t[i].parent == -1:
        t[i].setDepth(0)

for i in range(n):
    print('node {0}: parent = {1}, depth = {2}, '.\
        format(i, t[i].parent, t[i].depth), end='')
    if t[i].parent < 0:
        print('root', end='')
    elif len(t[i].children) == 0:
        print('leaf', end='')
    else:
        print('internal node', end='')
    print(', [', end='')
    print(', '.join(map(str, t[i].children)), end='')
    print(']')

Submission status: Accepted

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

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

D = {}  

def get_all_depth(T: dict, u: int, p: int):
    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, node, D):
    if T[node].left is not None: 
        node_type = 'internal node'
    else:
        node_type = '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:  
        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)  
        break

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
    
class Node:
    def __init__(self):
        self.parent = -1
        self.left = -1
        self.right = -1
        self.depth = -1
        self.c = []
        
T = [Node() for _ in range(100_000)]
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]

for i,a in enumerate(A):
    idx, k = a[:2]
    for j in range(k):
        c = a[2+j]
        T[idx].c.append(c)
        if j==0:
            T[idx].left = c
        else:
            T[left].right = c
        left = c
        T[c].parent = idx

for idx in range(n):
    if T[idx].parent == -1:
        root = idx
   
def set_depth(u,d):
    T[u].depth = d
    for c in T[u].c:
        set_depth(c,d+1)
        
set_depth(root, 0)
    
for idx in range(n):
    print('node {}: parent = {}, depth = {}, {}, {}'.format(idx, T[idx].parent, T[idx].depth, ('root' if T[idx].parent==-1 else 'leaf' if T[idx].left==-1 else 'internal node'), T[idx].c))

Submission status: Accepted

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

    def __str__(self):
        if self.parent == -1:
            self.type = "root"
        elif len(self.children) == 0:
            self.type = "leaf"
        else:
            self.type = "internal node"
        return "node {}: parent = {}, depth = {}, {}, {}".format(
            self.node, self.parent, self.depth, self.type, self.children)


def dfs(tree, v, p, d):
    from collections import deque
    que = deque()
    tree[v].parent = p
    tree[v].depth = d
    que.extend(tree[v].children)
    while len(que) > 0:
        c = que.pop()
        if tree[c].parent == -1:
            dfs(tree, c, v, d + 1)


def resolve():
    n = int(input())
    tree = [Node(i) for i in range(n)]
    V = [list(map(int, input().split())) for _ in range(n)]
    hasChild = set()
    childrens = set()
    for a, k, *c in V:
        if len(c) > 0:
            tree[a].children = c
            hasChild.add(a)
            childrens.update(c)
    root = hasChild - childrens
    if len(root) > 0:
        dfs(tree, root.pop(), -1, 0)
    print(*tree, sep="\n")


resolve()

Submission status: Accepted

Solution code:
n = int(input())

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

tree = []
for _ in range(n):
    tree.append(Node())

for _ in range(n):
    tmp = list(map(int, input().split()))
    id = tmp[0]
    degree = tmp[1]
    children = tmp[2:]
    if degree > 0:
        tree[id].left_child = children[0]
        for (cnt, child) in enumerate(children):
            tree[child].parent = id
            if cnt < degree - 1:
                tree[child].right_sibling = children[cnt + 1]
    
    
def get_depth(id):
    out = 0
    node = tree[id]
    while node.parent is not None:
        out += 1
        node = tree[node.parent]
    return out

def get_children(id):
    left_child_id = tree[id].left_child
    if left_child_id is None:
        return []
    node = tree[left_child_id]
    out = [left_child_id]
    while node.right_sibling is not None:
        out.append(node.right_sibling)
        node = tree[node.right_sibling]
    return out

def get_type(id):
    node = tree[id]
    if node.parent is None:
        return 'root'
    elif node.left_child is not None:
        return 'internal node'
    else:
        return 'leaf'
    
for id in range(n):
    print(f"node {id}: parent = {-1 if tree[id].parent is None else tree[id].parent}, depth = {get_depth(id)}, {get_type(id)}, {get_children(id)}")

Submission status: Accepted

Solution code:
ID     = 'id'
PARENT = 'parent'
DEPTH  = 'depth'
TYPE   = 'type'
POINT  = 'POINT'

n = int(input())
nodes = [{} for _ in range(n)]
for i in range(n):
  detail = list(map(int, input().split()))
  nodes[detail[0]][ID] = detail[0]
  nodes[detail[0]][PARENT] = -1
  nodes[detail[0]][DEPTH] = 0
  nodes[detail[0]][TYPE] = 'root'
  if detail[1] > 0:
    nodes[detail[0]][POINT] = detail[2:]
  else:
    nodes[detail[0]][POINT] = []
    nodes[detail[0]][TYPE] = 'leaf'

for node in nodes:
  if node[POINT]:
    for i in node[POINT]:
      nodes[i][PARENT] = node[ID]

for node in nodes:
  depth = 0
  parent = node[PARENT]
  while True:
    if parent == -1:
      break
    else:
      parent = nodes[parent][PARENT]
    depth += 1
  node[DEPTH] = depth

for node in nodes:
  if node[PARENT] == -1:
    node[TYPE] = 'root'
  elif len(node[POINT])>0:
    node[TYPE] = 'internal node'

for node in nodes:
  print ('node {id}: parent = {parent}, depth = {depth}, {type}, {point}'
    .format(id=node[ID], parent=node[PARENT], depth=node[DEPTH], type=node[TYPE], point=node[POINT]))

Submission status: Accepted

Solution code:
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    n = I()
    children = [[] for _ in range(n)]
    for _ in range(n):
        ikc = LI()
        id = ikc[0]
        # k = ikc[1]
        c = ikc[2:]
        children[id] = c

    parent = [-1]*n
    for i, e in enumerate(children):
        for j in e:
            parent[j] = i

    depth = [-1]*n
    root = parent.index(-1)
    depth[root] = 0
    que = collections.deque()
    que.append(root)
    while que:
        c = que.popleft()
        for i in children[c]:
            if depth[i]==-1:
                que.append(i)
                depth[i] = depth[c] + 1

    node_type = ['']*n
    for i in range(n):
        if parent[i]==-1:
            node_type[i] = 'root'
        elif not children[i]:
            node_type[i] = 'leaf'
        else:
            node_type[i] = 'internal node'

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

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
writelines = sys.stdout.writelines  
N = int(readline())

depth = [0]*N
PR = [-1]*N
G = [None]*N

for i in range(N):
    i, _, *cs, = map(int, readline().split())
    G[i] = cs
    for v in G[i]:
        PR[v] = i

def dfs(v, d):
    depth[v] = d
    for w in G[v]:
        dfs(w, d+1)

dfs(PR.index(-1), 0)
writelines(["node %d: parent = %d, depth = %d, %s, %s\n" % (i, PR[i], depth[i], ('root' if PR[i] == -1 else 'leaf' if len(G[i]) == 0 else 'internal node'), G[i]) for i in range(N)])

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:

n = int(input())

tree_info = {}
for i in range(n):
    row = input().split()
    tree_info[int(row[0])] = (int(row[1]), list(map(int, row[2:])))
tree_info

Nodes = [None] * n

class Node:
    
    def __init__(self, id, parent, depth, child):
        self.id = id
        self.parent = parent
        self.depth = depth
        if (parent == -1):
            self.tree_type = "root"
        elif(len(child) == 0):
            self.tree_type = "leaf"
        else:
            self.tree_type = "internal node"
            
        self.child = child
        
        if(self.tree_type != "leaf"):
            self.make_child()
    
    def make_child(self):
        for ch_id in self.child:
            Nodes[ch_id] = Node(ch_id, self.id, self.depth + 1, tree_info[ch_id][1])
        
    
    def __str__(self):
        return "node {}: parent = {}, depth = {}, {}, {}".format(self.id, self.parent, self.depth, self.tree_type, self.child)


for i in range(n):
    if(Nodes[i] == None):
        Nodes[i] = Node(i, -1, 0, tree_info[i][1])
        Nodes[i].make_child()

for root in Nodes:
    print(root)

Submission status: Accepted

Solution code:
n = int(input())
tree =[[] for _ in range(n)]
parent = [-1]*n
depth = [-1]*n

for i in range(n):
    temp = list(map(int,input().split()))
    tree[temp[0]].append(temp[1:])
    if temp[1] != 0:
        for j in range(temp[1]):
            parent[temp[2+j]] = temp[0]

def getDepth(u):
    if depth[u] != -1:
        return depth[u]
    if parent[u] == -1:
        depth[u] = 0
        return 0
    else:
        d = getDepth(parent[u]) + 1
        depth[u] = d
        return d

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


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

Submission status: Accepted

Solution code:
from collections import deque


def main():
    n = int(input())
    trees = [None for _ in range(n)]
    for i in range(n):
        tree = list(map(int, input().split()))
        trees[tree[0]] = tree[2:]

    # 根を探す
    candidates = set()
    have_parents = set()
    children = []
    for i in range(len(trees)):
        if len(trees[i]):
            candidates.add(i)
            children.extend(trees[i])
    children = set(children)
    have_parents = {c for c in candidates if c in children}

    if n == 1:
        root_node = 0
    else:
        root_node = list(candidates - have_parents)[0]

    depth = []
    q = deque()
    seen = [0]*n
    depth = [0]*n
    parents = [0]*n

    q.append(root_node)
    seen[root_node] = 1
    parents[root_node] = -1

    while len(q):
        v = q.pop()
        d = depth[v] + 1
        for t in trees[v]:
            if seen[t]:
                continue
            seen[t] += 1
            parents[t] = v
            q.append(t)
            depth[t] = d

    for i in range(n):
        if not depth[i]:
            print(
                "node {}: parent = {}, depth = {}, root, {}"
                .format(i, parents[i], depth[i], trees[i]))
        elif depth and len(trees[i]):
            print(
                "node {}: parent = {}, depth = {}, internal node, {}"
                .format(i, parents[i], depth[i], trees[i]))
        else:
            print(
                "node {}: parent = {}, depth = {}, leaf, {}"
                .format(i, parents[i], depth[i], trees[i]))


if __name__ == '__main__':
    main()