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:
# -*- coding:utf-8 -*-
import sys
from collections import OrderedDict


def cleate_node_dict(children):
    node_dict = OrderedDict()
    for val in children:
        node_dict[val] = OrderedDict()
    return node_dict


def cleate_tree(nodes):
    tree = nodes.copy()
    for node, children in nodes.items():
        for key in children.keys():
            children[key] = nodes[key]
            del tree[key]

    return tree


def rec(current, acc, parent=-1, depth=0):
    if current == {}:
        return
    for node, children in current.items():
        cld_lst = list(children.keys())
        acc[node] = "node {0}: parent = {1}, depth = {2}, {3}, {4}".format(
                node, parent, depth, node_type(parent, children), cld_lst)
        rec(children, acc, node, depth+1)


def node_type(parent, children):
    if parent == -1:
        return "root"
    elif children != {}:
        return "internal node"
    else:
        return "leaf"


if __name__ == "__main__":
    n = int(input())
    lst = [[int(n) for n in val.split()] for val in sys.stdin.readlines()]
    nodes = {val[0]: cleate_node_dict(val[2:]) for val in lst}
    tree = cleate_tree(nodes)
    node_info = {}
    rec(tree, node_info)
    for key, val in sorted(node_info.items()):
        print(val)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, x, y):
        self.id = x
        self.k = y
        self.children = []
        self.type = ''
        self.depth = 20
        self.parent = '-1'

def findRoot(tree):
    for x in tree:
        for y in x.children:
            tree[int(y)].parent = x.id
            if tree[int(y)].k == 0:
                tree[int(y)].type = 'leaf'
            else:
                tree[int(y)].type = 'internal node'
            '''for a in tree:
                if y == a.id:
                    if a.k == 0:
                        a.type = 'leaf'
                    else:
                        a.type = 'internal node'
                    a.parent = x.id
            '''
    for i,x in enumerate( tree):
        if x.type == 'root':
            return i


def setd(tree,node,d):
    node.depth = d
    if node.k == 0:
        return
    else:
        for tmp in node.children:
            setd(tree,tree[int(tmp)],d+1)
            '''for x in tree:
                if x.id == tmp:
                    setd(tree,x,d+1)
            '''


if __name__ == '__main__':
    n = (int)(input())
    tree = [None]*n
    for i in range(0,n):
        tmp = input().split()
        a = Node(tmp[0],(int)(tmp[1]))
        a.children=tmp[2:]
        a.type = 'root'
        tree[int(a.id)] = a
    ri = findRoot(tree)
    setd(tree,tree[ri],0)
    
    for tmp in tree:
        print("node {}: parent = {}, depth = {}, {}, {}".format(tmp.id, tmp.parent,tmp.depth,tmp.type,list(map(int,tmp.children))))

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
import sys
from collections import OrderedDict


def cleate_node_dict(children):
    node_dict = OrderedDict()
    for val in children:
        node_dict[val] = None
    return node_dict


def cleate_tree(nodes):
    tree = nodes.copy()
    for node, children in nodes.items():
        for key in children.keys():
            children[key] = nodes[key]
            del tree[key]

    return tree


def rec(current, acc, parent=-1, depth=0):
    if current == {}:
        return
    for node, children in current.items():
        cld_lst = list(children.keys())
        acc[node] = "node {0}: parent = {1}, depth = {2}, {3}, {4}".format(
                node, parent, depth, node_type(parent, children), cld_lst)
        rec(children, acc, node, depth+1)


def node_type(parent, children):
    if parent == -1:
        return "root"
    elif children != {}:
        return "internal node"
    else:
        return "leaf"


def rooted_trees(lst, n):
    nodes = {val[0]: cleate_node_dict(val[2:]) for val in lst}
    tree = cleate_tree(nodes)
    node_info = [None] * n
    rec(tree, node_info)
    print("\n".join(node_info))


if __name__ == "__main__":
    n = int(input())
    lst = [[int(n) for n in val.split()] for val in sys.stdin.readlines()]
    rooted_trees(lst, n)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(200000)

class Node():
    def __init__(self, ID, parent=-1, left=-1, right=-1, depth=0, children=[]):
        self.id = ID
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
        self.children = children


if __name__ == '__main__':

    n = int(input())
    tree = [Node(i) for i in range(n)]

    for _ in range(n):
        line = [int(l) for l in input().split(" ")]
        ID = line[0]
        d = line[1]
        if d == 0:
            continue
        else:
            children = line[2:]
            tree[ID].children = children
            tree[ID].left = children[0]
            for j in range(0, d):
                tree[children[j]].parent = ID
                if j < d - 1:
                    tree[children[j]].right = children[j + 1]

    def setDepth(u, p):
        tree[u].depth = p
        if tree[u].right != -1:
            setDepth(tree[u].right, p)
        if tree[u].left != -1:
            setDepth(tree[u].left, p + 1)

    for node in tree:
        if node.parent == -1:
            root = node.id

    setDepth(root, 0)

    for node in tree:
        if node.parent == -1:
            n_type = "root"
        elif node.left != -1:
            n_type = "internal node"
        else:
            n_type = "leaf"

        print("node {}: parent = {}, depth = {}, {}, {}".format(
            node.id, node.parent, node.depth, n_type, node.children))

Submission status: Accepted

Solution code:
class Tree:
    def __init__(self):
        self.id = 0
        self.p = -1
        self.depth = -1
        self.type = "leaf"
        self.len_c = 0
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, depth = {self.depth}, {self.type}, {self.c}"
n = int(input())
li = [Tree() for _ in range(n)]
for _ in range(n):
    id, k, *c = map(int, input().split())
    if k == 0:
        c = []
    else:
        li[id].type = "internal node"
    li[id].id = id
    li[id].c = c
    for j in c:
        li[j].p = id
root = 0
while True:
    a = li[root].p
    if a == -1:
        li[root].type = "root"
        li[root].depth = 0
        break
    root = a
dp = [(root, 0)]
while dp:
    id, d = dp.pop()
    for i in li[id].c:
        li[i].depth = d + 1
        dp.append((i, d + 1))
for i in range(n):
    print(li[i])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
class Tree:
    def __init__(self):
        self.id = 0
        self.p = -1
        self.depth = -1
        self.type = "leaf"
        self.len_c = 0
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, depth = {self.depth}, {self.type}, {self.c}"
n = int(input())
li = [Tree() for _ in range(n)]
for _ in range(n):
    id, k, *c = map(int, readline().split())
    if k == 0:
        c = []
    else:
        li[id].type = "internal node"
    li[id].id = id
    li[id].c = c
    for j in c:
        li[j].p = id
root = 0
while True:
    a = li[root].p
    if a == -1:
        li[root].type = "root"
        li[root].depth = 0
        break
    root = a
dp = [(root, 0)]
while dp:
    id, d = dp.pop()
    for i in li[id].c:
        li[i].depth = d + 1
        dp.append((i, d + 1))
for i in range(n):
    print(li[i])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'depth', 'type', 'len_c', 'c']
    def __init__(self):
        self.id = 0
        self.p = -1
        self.depth = -1
        self.type = "leaf"
        self.len_c = 0
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, depth = {self.depth}, {self.type}, {self.c}"
n = int(input())
li = [Tree() for _ in range(n)]
for _ in range(n):
    id, k, *c = map(int, readline().split())
    if k == 0:
        c = []
    else:
        li[id].type = "internal node"
    li[id].id = id
    li[id].c = c
    for j in c:
        li[j].p = id
root = 0
while True:
    a = li[root].p
    if a == -1:
        li[root].type = "root"
        li[root].depth = 0
        break
    root = a
dp = [(root, 0)]
while dp:
    id, d = dp.pop()
    for i in li[id].c:
        li[i].depth = d + 1
        dp.append((i, d + 1))
for i in range(n):
    print(li[i])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'depth', 'type', 'c']
    def __init__(self):
        self.id = 0
        self.p = -1
        self.depth = -1
        self.type = "leaf"
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, depth = {self.depth}, {self.type}, {self.c}"
n = int(input())
li = [Tree() for _ in range(n)]
for _ in range(n):
    id, k, *c = map(int, readline().split())
    if k == 0:
        c = []
    else:
        li[id].type = "internal node"
    li[id].id = id
    li[id].c = c
    for j in c:
        li[j].p = id
root = 0
while True:
    a = li[root].p
    if a == -1:
        li[root].type = "root"
        li[root].depth = 0
        break
    root = a
dp = [(root, 0)]
while dp:
    id, d = dp.pop()
    d += 1
    for i in li[id].c:
        li[i].depth = d
        dp.append((i, d))
print(*li, sep="\n")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'depth', 'type', 'c']
    def __init__(self):
        self.id = 0
        self.p = -1
        self.depth = -1
        self.type = "leaf"
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, depth = {self.depth}, {self.type}, {self.c}"
n = int(input())
li = tuple(Tree() for _ in range(n))
for _ in range(n):
    id, k, *c = map(int, readline().split())
    if k == 0:
        c = []
    else:
        li[id].type = "internal node"
    li[id].id = id
    li[id].c = c
    for j in c:
        li[j].p = id
root = 0
while True:
    a = li[root].p
    if a == -1:
        li[root].type = "root"
        li[root].depth = 0
        break
    root = a
dp = [(root, 0)]
while dp:
    id, d = dp.pop()
    d += 1
    for i in li[id].c:
        li[i].depth = d
        dp.append((i, d))
print(*li, sep="\n")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'depth', 'type', 'c']
    def __init__(self, id):
        self.id = id
        self.p = -1
        self.depth = -1
        self.type = "leaf"
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, depth = {self.depth}, {self.type}, {self.c}"
n = int(input())
li = tuple(Tree(i) for i in range(n))
for _ in range(n):
    id, k, *c = map(int, readline().split())
    if k != 0:
        li[id].type = "internal node"
        li[id].c = c
        for j in c:
            li[j].p = id
root = 0
while li[root].p != -1:
    root = li[root].p
li[root].type = "root"
li[root].depth = 0
def depth_check(id, d):
    d += 1
    for i in li[id].c:
        li[i].depth = d
        if li[i].type != "leaf":
            depth_check(i, d)
depth_check(root, 0)
print(*li, sep="\n")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'depth', 'type', 'c']
    def __init__(self, id):
        self.id = id
        self.p = -1
        self.depth = -1
        self.type = "leaf"
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, depth = {self.depth}, {self.type}, {self.c}"
n = int(input())
li = tuple(Tree(i) for i in range(n))
for _ in range(n):
    id, k, *c = map(int, readline().split())
    if k != 0:
        li[id].type = "internal node"
        li[id].c = c
        for j in c:
            li[j].p = id
root = 0
while li[root].p != -1:
    root = li[root].p
li[root].type = "root"
li[root].depth = 0
def depth_check(id, d):
    d += 1
    for i in li[id].c:
        li[i].depth = d
        if li[i].type != "leaf":
            depth_check(i, d)
depth_check(root, 0)
print("\n".join(map(str, li)))

Submission status: Accepted

Solution code:
class tree:
    def __init__(self,name,parent):
        self.name = name
        self.parent = parent
        
        
n = int(input())
trees = {str(i):tree(str(i),'-1') for i in range(n)}
child = {}

for i in range(n):
    s = [i for i in input().split()]
    p = s[0]
    child[p] = s[2:]
    s_t = s[2:]
    for j in range(len(s_t)):
        trees[s_t[j]] = tree(s_t[j],p)

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

def getChildren(u):
    c = []
    for i in trees.values():
        if i.parent == u:
            c.append(i.name)
    return c

for i in range(n):
    
    par = trees[str(i)].parent
    dep = getDepth(str(i))
    ch = [int(i) for i in child[str(i)]]
    
    if par == '-1':sit = 'root'
    elif len(ch) != 0:sit = 'internal node'
    else:sit = 'leaf'
    
    print('node {}: parent = {}, depth = {}, {}, {}'.format(i,par,dep,sit,ch))

Submission status: Accepted

Solution code:
import collections

def search(node, elems, tree, depth):
    elems[node].append(depth)
    if elems[node][0] == -1:
        state = 'root'
    elif not tree[node]:
        state = 'leaf'
    else:
        state = 'internal node'
    elems[node].append(state)
    elems[node].append(tree[node])
    depth += 1
    for c in tree[node]:
        search(c, elems, tree, depth)
    
if __name__ == '__main__':
    n = int(input())
    tree = collections.defaultdict(list)
    elems = collections.defaultdict(list)
    #elems key:id, value: parent, depth, state, children
    parents = list()
    node_list = list()
    for _ in range(n):
        hoge = [int(x) for x in input().split()]
        node_list.append(hoge[0])
        tree[hoge[0]]
        for childs in range(hoge[1]):
            tree[hoge[0]].append(hoge[childs+2])
    
    for key, value in tree.items():
        for v in value:
            elems[v].append(key)
    for node in node_list:
        if not elems[node]:
            parents.append(node)
            elems[node].append(-1)
    
    for p in parents:
        search(p, elems, tree, 0)
        
    for key, value in sorted(elems.items()):
        print('node {0}: parent = {1[0]}, depth = {1[1]}, {1[2]}, '.format(key, value), end='')
        print (value[-1])

Submission status: Accepted

Solution code:
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t={}
p={}
d={}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):i=str(i);print('node',i+':','parent =',p[i]+',','depth =',d[i]+',','root,'if'-1'==p[i]else'internal node,'if t[i]else'leaf,',list(map(int,t[i])))

Submission status: Accepted

Solution code:
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):i=str(i);print('node',i+':','parent =',p[i]+',','depth =',d[i]+',','root,'if'-1'==p[i]else'internal node,'if t[i]else'leaf,',list(map(int,t[i])))

Submission status: Accepted

Solution code:
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):
 i=str(i)
 f='root'if'-1'==p[i]else'internal node'if t[i]else'leaf'
 print(f'node {i}: parent = {p[i]}, depth = {d[i]}, {f}, {list(map(int,t[i]))}')

Submission status: Accepted

Solution code:
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):i=str(i);print(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]")

Submission status: Accepted

Solution code:
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Submission status: Accepted

Solution code:
import sys
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
input()
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Submission status: Accepted

Solution code:
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
input()
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,sorted(map(int,t)))))

Submission status: Accepted

Solution code:
import sys
def q(a,h):
 d[a]=h
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
n=int(input())
for e in sys.stdin:
 e=e.split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
print('\n'.join(f"node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, [{', '.join(t[i])}]"for i in map(str,range(n))))

Submission status: Accepted

Solution code:
class Vertex:
    _id = -1
    _children = []
    _parent = -1
    _depth = 0
    _type = "root"

    def __init__(self, i, c):
        self._id = i
        self._children = c

    def getId(self):
        return self._id

    def getChildren(self):
        return self._children

    def getParent(self):
        return self._parent

    def getDepth(self):
        return self._depth

    def getType(self):
        return self._type

    def setParent(self, p):
        self._parent = p

    def setDepth(self, d):
        self._depth = d

    def setType(self, t):
        self._type = t

    def print(self):
        print("node {}: parent = {}, depth = {}, {}, {}".format(self._id, self._parent, self._depth, self._type, self._children))


n = int(input())
tree = [0 for i in range(n)]

# 節点
for i in range(n):
    u = list(map(int, input().split(' ')))
    tree[u[0]] = Vertex(u[0], u[2:u[1]+2])

# 親を設定
for w in tree:
    for c in w.getChildren():
        tree[c].setParent(w.getId())
        tree[c].setType("internal node")

# 葉と親を判定
for w in tree:
    if w.getChildren() == []:
        w.setType("leaf")
    if w.getParent() == -1:
        w.setType("root")

# DFS
def dfs(v, depth):
    v.setDepth(depth)
    for child in v.getChildren():
        dfs(tree[child], depth+1)

# 根を探す
root = tree[0]
for w in tree:
    if w.getType() == "root":
        root = w

dfs(root, 0)

# 回答を出力
for w in tree:
    w.print()

Submission status: Accepted

Solution code:
class Tree:
    nodes = []
    def __init__(self, root = None):
        None
    def insert(self, label, children = []):
        if children != []:
            for i in children:
                self.nodes[label].children.append(self.nodes[i])
                self.nodes[i].parent = self.nodes[label]
                self.nodes[i].type_ = "internal node"
    def depth(self, node):
        if node.children == []:
            node.type_ = "leaf"
        else:
            for i in node.children:
                i.depth = node.depth + 1
                self.depth(i)

class Node:
    def __init__(self, label, children = []):
        self.label = label
        self.type_ = "root"
        self.depth = 0
        self.parent = -1
        self.children = [] # self.children = childrenにするとハマる

tree = Tree()
n = int(input())
for i in range(n):
    tree.nodes.append(Node(i))
for i in range(n):
    children = []
    label, num, *children = map(int, input().split())
    tree.insert(label, children)
for i in tree.nodes:
    if i.parent == -1:
        tree.depth(i)
        None
if n == 1:
    tree.nodes[0].type_ = "root"
for i in tree.nodes:
    print("node {0:}: parent = {1:}, depth = {2:}, {3:}, ".\
            format(i.label, i.parent if i.parent == -1 else i.parent.label,\
            i.depth, i.type_), end = "")
    print([i.label for i in i.children])

Submission status: Accepted

Solution code:
NIL = -1

class Node:
    parent = NIL
    left = NIL
    right = NIL

n = int(input())
t = [Node() for i in range(n)]

for i in range(n):
    tmp = list(map(int, input().split()))
    id = tmp.pop(0)
    k = tmp.pop(0)
    c = tmp
    if k != 0:
        for j in c:
            t[j].parent = id
        t[id].left = c[0]
        for j in range(len(c)-1):
            t[c[j]].right = c[j+1]

def getdepth(u):
    d = 0
    while t[u].parent != NIL:
        u = t[u].parent
        d += 1
    return d

def getchildren(u):
    c = t[u].left
    result = []
    while c != NIL:
        result.append(c)
        c = t[c].right
    return result

for i in range(n):
    d = getdepth(i)
    c = getchildren(i)
    if d == 0:
        v = "root"
    elif c == []:
        v = "leaf"
    else:
        v = "internal node"
    print('node {}: parent = {}, depth = {}, {}, [{}]'.format(i, t[i].parent, d, v, ', '.join(map(str, c))))

Submission status: Accepted

Solution code:

class TreeNode:
    def __init__(self, nodeid):
        self.nodeid = nodeid
        self.parent = None
        self.sibling = None
        self.child = None
        self.depth = 0

    def node_type(self):
        if self.parent is None:
            return 'root'
        elif self.child is None:
            return 'leaf'
        else:
            return 'internal node'

    def parent_nodeid(self):
        if self.parent is None:
            return -1
        else:
            return self.parent.nodeid

    def child_nodeids(self):
        if self.child is not None:
            yield self.child.nodeid
            yield from self.child.sibling_nodeids()

    def sibling_nodeids(self):
        s = self.sibling
        stack = []
        while s is not None:
            stack.append(s.nodeid)
            s = s.sibling
        while len(stack) > 0:
            yield stack.pop()

    def get_depth(self):
        if self.node_type() != 'root' and self.depth == 0:
            self.depth = self.parent.get_depth() + 1

        return self.depth

    def add_child(self, node):
        if self.child is None:
            self.child = node
            self.child.parent = self
        else:
            self.child.add_sibling(node)

    def add_sibling(self, node):
        node.parent = self.parent
        node.sibling = self.sibling
        self.sibling = node

    def __str__(self):
        return ('node {}: parent = {}, depth = {}, {}, [{}]'.format(
                self.nodeid, self.parent_nodeid(), self.get_depth(),
                self.node_type(),
                ", ".join([str(i) for i in self.child_nodeids()])))


class Tree:
    def __init__(self):
        self.nodes = {}

    def node(self, nodeid):
        if nodeid not in self.nodes:
            self.nodes[nodeid] = TreeNode(nodeid)

        return self.nodes[nodeid]

    def sorted_nodes(self):
        for nodeid in sorted(self.nodes.keys()):
            yield self.nodes[nodeid]


def run():
    c = int(input())
    tree = Tree()

    for _ in range(c):
        nodeid, deg, *cs = [int(i) for i in input().split()]
        node = tree.node(nodeid)
        for c in cs:
            node.add_child(tree.node(c))

    for node in tree.sorted_nodes():
        print(node)


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
n = int(input())
rt = {}
cs = [0 for i in range(n)]
for i in range(n):
    id, k, *c = list(map(int, input().split()))
    for j in c:
        rt[j] = id
    cs[id] = c

for i in range(n):
    print("node " + str(i) + ": parent = ", end = "")
    p = [i]
    while True:
        try:
            p.append(rt[p[-1]])
        except:
            break
    if len(p) == 1:
        print("-1, depth = 0, root, ", end = "")
        print(cs[i])
    else:
        print(str(p[1]) + ", depth = " + str(len(p) - 1), end = "")
        if cs[i] == []:
            print(", leaf, []")
        else:
            print(", internal node, ",end = "")
            print(cs[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

class Node:
    def __init__(self, parent = -1, left = -1, right = -1, depth = 0):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
    
def print_node(i):
    global node
    print("node " + str(i) + ": ", end = "")
    print("parent = " + str(node[i].parent) +", ", end = "")
    print("depth = " + str(node[i].depth) + ", ", end = "")
    if node[i].parent == -1:
        print("root, [", end = "")
    elif node[i].left != -1:
        print("internal node, [", end = "")
    else:
        print("leaf, [", end = "")
    if node[i].left != -1:
        print(str(node[i].left), end = "")
        j = node[i].left
        while node[j].right != -1:
            j = node[j].right
            print(", " + str(j), end = "")
    print("]")
            

n = int(input())
node = [Node() for i in range(n)]
def input_depth(i, n):
    global node
    node[i].depth = n
    if node[i].right != -1:
        input_depth(node[i].right, n)
    if node[i].left != -1:
        input_depth(node[i].left, n + 1)

for i in range(n):
    p, k, *c = list(map(int, input().split()))
    if k > 0:
        node[p].left = c[0]
    for j in range(k):
        node[c[j]].parent = p
        if j != k - 1:
            node[c[j]].right = c[j + 1]

for i in range(n):
    if node[i].parent == -1:
        input_depth(i, 0)
        break

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