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

nil = -1

def set_depth(v, depth):
    tree[v][2] = depth

    for child in tree[v][1]:
        set_depth(child, depth + 1)

n = int(input())

tree = [[nil, [], 0, 'leaf'] for i in range(n)]

for i in range(n):
    line = [int(i) for i in sys.stdin.readline().split()]
    t_id = line[0]
    children = line[2:]

    tree[t_id][1] = children

    if children:
        tree[t_id][3] = 'internal node'

    for child in children:
        tree[child][0] = t_id

for t_id in range(n):
    if tree[t_id][0] == nil:
        tree[t_id][3] = 'root'
        r = t_id
        break

# print(tree)

set_depth(r, 0)

for t_id in range(n):
    parent = tree[t_id][0]
    depth = tree[t_id][2]
    children = tree[t_id][1]
    type_t = tree[t_id][3]

    print('node {}: parent = {}, depth = {}, {}, {}'.format(
            t_id, parent, depth, type_t, children))

Submission status: Accepted

Solution code:


def main():
    N = int(input())
    A = [0] * N
    node_info = [[-1, 0, 'internal node', None] for _ in range(int(1E5 + 1))]
    for i in range(N):
        A[i] = [int(i) for i in input().strip().split()]
    for line in A:
        if line[1] != 0:
            node_info[line[0]][3] = line[2:]
            for c in line[2:]:
                node_info[c][0] = line[0]

    for line in A:
        pid = node_info[line[0]][0]
        if pid == -1:
            node_info[line[0]][2] = 'root'
        else:
            if node_info[line[0]][3] is None:
                node_info[line[0]][2] = 'leaf'
        if node_info[line[0]][3] is None:
            node_info[line[0]][3] = ['']

        depth = 0
        while pid != -1:
            depth += 1
            pid = node_info[pid][0]
        node_info[line[0]][1] = depth

    for line in sorted(A, key=lambda a: a[0]):
        print('node {}: parent = {}, depth = {}, {}, [{}]'.format(
            line[0], node_info[line[0]][0],
            node_info[line[0]][1], node_info[line[0]][2], ', '.join([str(i) for i in node_info[line[0]][3]]))
        )


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
NIL = -1

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

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

n = int(input())
T = [0]*n
for i in range(n):
    T[i] = Node()
    
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 range(len(c)):
            T[c[j]].parent = id
        T[id].left = c[0]
        for j in range(len(c)-1):
            T[c[j]].right = c[j+1]
            
for i in range(n):
    d = getDepth(i)
    c = getChildren(i)
    if d == 0:
        t = 'root'
    elif c == []:
        t = 'leaf'
    else:
        t = 'internal node'
    print('node ',i,': ','parent = ',T[i].parent,', depth = ',d,', ',t,', ',c,sep = '')

Submission status: Accepted

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

def getdepth(u):
    for i in range(N):
        depth = 0
        j = i
        while trees[j].parent != -1:
            j = trees[j].parent
            depth += 1
        depths[i] = depth


N = int(input())
# ?????????
trees = [Tree(-1,-1,-1) for i in range(N)]
for i in range(N):
    l = list(map(int, input().split()))
    no = l[0]
    jisu = l[1]
    # 2???????????????????????§???????´??????????
    childs = l[2:]
    for j in range(jisu):
        child = childs[j]
        if j == 0:
            trees[no].left = child

        if j != len(childs)-1:
            trees[child].right = childs[j+1]

        trees[child].parent = no

r = 0
for i in range(N):
    if trees[i].parent == -1:
        r = i

depths = [-1] * N
getdepth(r)

for i in range(N):
    type = ""
    if trees[i].parent == -1: type = "root"
    elif trees[i].left == -1: type = "leaf"
    else: type = "internal node"
    childs = "["
    child = trees[i].left
    while child != -1:
        childs += str(child)
        child = trees[child].right
        if child != -1: childs += ", "
    childs += "]"

    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(i, trees[i].parent, depths[i], type, childs))

Submission status: Accepted

Solution code:
class Node:
  def __init__(self, id, children):
    self.id = id
    self.children = children
    self.type = "root"
    self.parent = None
    self.depth = 0

  def set_parent(self, parent):
    self.parent = parent
    self.type = "leaf" if len(self.children) == 0 else "internal node"

  def get_depth(self):
    if self.depth: return self.depth
    if self.type == "root": return 0
    self.depth = self.parent.get_depth() + 1
    return self.depth

  def display(self):
    print("node {}: parent = {}, depth = {}, {}, {}".format(
      self.id,
      self.parent.id if self.parent else -1,
      self.get_depth(),
      self.type,
      self.children
      )
    )

nodelist = {}
for i in range(int(input())):
  p = input().split()
  id = int(p[0])
  nodelist[id] = Node(id, list(map(int, p[2:])) if len(p) >= 3 else [])

for i in nodelist:
  n = nodelist[i]
  for cid in n.children:
    nodelist[cid].set_parent(n)

for i in sorted(nodelist): nodelist[i].display()

Submission status: Accepted

Solution code:
N = int(input())

tree = [{'p': -1, 'c': list(), 'd': 0} for _ in range(N)]

for _ in range(N):
    l = list(map(int, input().split()))
    tree[l[0]]['c'] = l[2:]
    for i in l[2:]:
        tree[i]['p'] = l[0]


def calcDepth(tree, root, curDepth=0):
    tree[root]['d'] = curDepth
    [calcDepth(tree, c, curDepth + 1) for c in tree[root]['c']]


r = 0
for i, t in enumerate(tree):
    if t['p'] == -1:
        r = i
        break
calcDepth(tree, r)

for i in range(N):
    state = 'leaf'
    if tree[i]['p'] == -1:
        state = 'root'
    elif len(tree[i]['c']):
        state = 'internal node'
    print('node {i}: parent = {p}, depth = {d}, {state}, {ch}'.format(
        i=i, p=tree[i]['p'], d=tree[i]['d'], state=state, ch=tree[i]['c']
    ))

Submission status: Accepted

Solution code:
import operator

class Tree:
    """??¨????????????"""

    def __init__(self, node_num):
        self.node_num = node_num
        self.node_list = list()
        self.root_node = -1

    def set_tree(self):
        for _ in range(self.node_num):
            input_str = [int(i) for i in input().split()]
            node_tmp = Node(input_str[0], input_str[1], input_str[2:])
            self.node_list.append(node_tmp)
        self.node_list.sort(key=operator.attrgetter('id'))

    def set_node_element(self):
        for tn in self.node_list:
            if tn.children is not None:
                for child in tn.children:
                    self.node_list[child].parent = tn.id
                    if self.node_list[child].degree == 0:
                        self.node_list[child].type = 'leaf'
                    else:
                        self.node_list[child].type = 'internal node'
        self.set_root()
        self.set_depth(self.node_list[self.root_node])

    def set_depth(self, node, dep = -1):
        node.depth = dep + 1
        for child in node.children:
            self.set_depth(self.node_list[child], node.depth)

    def set_root(self):
        for tn in self.node_list:
            if tn.type == 'root':
                self.root_node = tn.id
                break

    def show_tree(self):
        for tn in self.node_list:
            print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(tn.id, tn.parent, tn.depth, tn.type, tn.children))


class Node:
    """?????????????????????"""

    def __init__(self, id, degree, children):
        self.id = id
        self.degree = degree
        self.children = children
        self.parent = -1
        self.depth = 0
        self.type = 'root'

if __name__ == '__main__':
    n = int(input())
    tree = Tree(n)
    tree.set_tree()
    tree.set_node_element()
    tree.show_tree()

Submission status: Accepted

Solution code:
NIL = -1


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


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


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

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 range(len(c)):
            T[c[j]].parent = id
        T[id].left = c[0]
        for j in range(len(c) - 1):
            T[c[j]].right = c[j + 1]

for i in range(n):
    d = getDepth(i)
    c = getChildren(i)
    if d == 0:
        t = 'root'
    elif c == []:
        t = 'leaf'
    else:
        t = 'internal node'
    print('node ', i, ': ', 'parent = ', T[i].parent, ', depth = ', d, ', ', t, ', ', c, sep='')

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, num, parent, children):
        self.id = num
        self.parent = -1
        self.depth = 0
        self.type = None
        self.children = children
          
    def show(self):
        print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(self.id,self.parent,self.depth,self.type,self.children))
  
  
def set_node(node_data):
    L = list(map(int, node_data.split()))
    num = L[0]
    children = L[2:]
    node = Node(num, -1, children)
    T[num] = node
    for n in children:
        T[-1] -= n
  
def set_pdt(n_i, parent, depth):
    node = T[n_i]
    node.parent = parent
    node.depth = depth
    if node.children:
        node.type = 'internal node'
        for n in node.children:
            set_pdt(n, n_i, depth + 1)
    else:
        node.type = 'leaf'
  
n = int(input())
  
T = [None] * n
  
T.append(int(n * (n - 1) / 2))
  
for i in range(n):
    x = input()
    set_node(x)
  
set_pdt(T[-1], -1, 0)
  
T[T[-1]].type ='root'
  
for n in T[:-1]:
    n.show()

Submission status: Accepted

Solution code:
# coding=utf-8

class Node:
    def __init__(self, idx, degree, children=None):
        self.id = idx
        self.parent = -1 #??????
        self.depth = 0 #??????
        self.type = None #??????
        self.children = children

n = int(input())
data = [list(map(int, input().split())) for x in range(n)]
node_list = [None for i in range(n)]

for data_row in data:
    idx, degree, *children = data_row
    node = Node(idx, degree, children)
    node_list[idx] = node

### set parent & type ###
for node in node_list:
    i = node.id
    if node.children:
        node.type = "internal node"
        for child in node.children:
            node_list[child].parent = i
    else:
        node.type = "leaf"

### calc depth ###
for i, node in enumerate(node_list):
    depth = 0
    parent = node.parent
    #?????\???type
    if parent == -1:
        node.type = "root"
    while parent != -1:
        parent = node_list[parent].parent
        depth += 1
    node.depth = depth

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

Submission status: Accepted

Solution code:
import sys


def dep(u, p):
    D[u] = p
    for i in tree[u][3]:
        dep(i, p+1)


def print_ans():
    for i in range(n):
        print("node {}: parent = {}, depth = {}, {}, {}"
              .format(i, tree[i][0], D[i],
                      "root" if tree[i][0] == NIL else "leaf" if tree[i][1] == NIL else "internal node",
                      tree[i][3]))


if __name__ == "__main__":
    NIL = -1
    n = int(sys.stdin.readline())
    tree = [[NIL, NIL, NIL] for i in range(n)]
    D = [0 for i in range(n)]
    root = set(range(n))
    for a in sys.stdin.readlines():
        a = list(map(int, a.split()))
        tree[a[0]].append(a[2:])
        if a[1] > 0:
            tree[a[0]][1] = a[2]    # ???????????????
            for i in range(a[1]):
                tree[a[i+2]][0] = a[0] # ????????????
                if i != a[1] - 1:
                    tree[a[i+2]][2] = a[i+3] # ??????????????????
        root -= set(a[2:])
    dep(root.pop(), 0)
    print_ans()

Submission status: Accepted

Solution code:
def main():
    n = input()
    tree = MyTree(n)
    for i in range(n):
        id_k_cn = map(int,raw_input().split())
        id_node = id_k_cn.pop(0)
        k = id_k_cn.pop(0)
        tree.add(id_node,k,None,id_k_cn)
    
    tree.search_children()
    tree.set_depth(tree.nodes[tree.id_root],0)
    
    for node in tree.nodes:
        print "node {0}: parent = {1}, depth = {2}, {3}, {4}".format(node.id_self, node.id_parent, node.depth, node.node_type, node.id_children)


class MyTree():
    def __init__(self,num_nodes):
        self.nodes = [MyNode() for i in range(num_nodes)]
        self.id_root = None

    def add(self,id_node,n_children,id_parent,id_children):
        self.nodes[id_node].id_self = id_node
        self.nodes[id_node].n_children = n_children
        self.nodes[id_node].id_parent = id_parent
        self.nodes[id_node].id_children = id_children
    
    def search_children(self):
        for node in self.nodes:
            if node.n_children == 0:
                node.node_type = "leaf"
            else:
                node.node_type = "internal node"
            for j in node.id_children:
                self.nodes[j].id_parent = node.id_self

        for node in self.nodes:
            if node.id_parent == None:
                node.id_parent = -1
                node.node_type = "root"
                self.id_root = node.id_self
                break

    def set_depth(self,node,depth):
        node.depth = depth
        node.id_children
        for item in node.id_children:
            self.set_depth(self.nodes[item],depth+1)


class MyNode():
    def __init__(self):
        self.id_self = None
        self.id_parent = None
        self.id_children = None
        self.depth = None
        self.node_type = None
        self.n_children = 0
        


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n = input()
    tree = MyTree(n)
    for i in range(n):
        id_k_cn = map(int,raw_input().split())
        id_node = id_k_cn.pop(0)
        k = id_k_cn.pop(0)
        tree.add(id_node,k,None,id_k_cn)
    
    tree.search_children()
    tree.set_depth(tree.nodes[tree.id_root],0)
    
    for node in tree.nodes:
        print "node {0}: parent = {1}, depth = {2}, {3}, {4}".format(node.id_self, node.id_parent, node.depth, node.node_type, node.id_children)


class MyTree():
    def __init__(self,num_nodes):
        self.nodes = [MyNode() for i in range(num_nodes)]
        self.id_root = None

    def add(self,id_node,n_children,id_parent,id_children):
        node = self.nodes[id_node]
        node.id_self = id_node
        node.n_children = n_children
        node.id_parent = id_parent
        node.id_children = id_children
    
    def search_children(self):
        for node in self.nodes:
            if node.n_children == 0:
                node.node_type = "leaf"
            else:
                node.node_type = "internal node"
            for j in node.id_children:
                self.nodes[j].id_parent = node.id_self

        for node in self.nodes:
            if node.id_parent == None:
                node.id_parent = -1
                node.node_type = "root"
                self.id_root = node.id_self
                break

    def set_depth(self,node,depth):
        node.depth = depth
        node.id_children
        for item in node.id_children:
            self.set_depth(self.nodes[item],depth+1)


class MyNode():
    def __init__(self):
        self.id_self = None
        self.id_parent = None
        self.id_children = None
        self.depth = None
        self.node_type = None
        self.n_children = 0
        


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

I = 0
K = 1
C = 2
P = 3
D = 4

def setd(A, id, d):
    n = A[id]
#    print("depth d:{} n:{} {}".format(d,id,n))
    n[D] = d
    if n[K] > 0:
        for c in n[C]:
            setd(A, c, d + 1)

def setp(A, id, pid):
    n = A[id]
#    print("parent n:{} {}".format(id,n))
    if pid > -1:
        n[P] = pid
    if n[K] > 0:
        for c in n[C]:
            setp(A, c, n[I])

def getroot(A, id):
    if A[id][P] > -1:
        return getroot(A,A[id][P])
    return A[id][I]

def main():

    """ ????????? """
    num = int(input().strip())
    istr = sys.stdin.read()
    nlist = list(istr.splitlines())
    
    nodes = [[i,0,None,-1,0] for i in range(num)]

    for nstr in nlist:
        i = list(map(int,nstr.split()))
        id = i[0]
        n = nodes[id]
#        print("set n:{} {}".format(id,n))
        if i[K] != 0:
            n[K] = i[K]
            n[C] = i[2:]
            setp(nodes, i[0], -1)

    r = getroot(nodes, 0)
    setd(nodes,r, 0)

    for id in range(num):
        n = nodes[id]
#        print("print n:{} {}".format(id,n))
        type = "leaf"
        children = ""
        if n[K] > 0:
            type = "internal node"
            children = ", ".join(map(str,n[C]))
        if n[P] == -1:
            type = "root"
        print("node {0}: parent = {1}, depth = {2}, {3}, [{4}]".format(n[I], n[P], n[D], type, children))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Node():
    def __init__(self, id, num, child, nodetype=None, depth=-1, parent=-1):
        self.id = id
        self.num = num
        self.child = child
        self.nodetype = nodetype
        self.depth = depth
        self.parent = parent
    def showFinal(self):
        print 'node %d: parent = %d, depth = %d, %s,' % (self.id, self.parent, self.depth, self.nodetype), self.child
        
def calcDepth(node):
    if node.parent == -1:
        return 0
    return calcDepth(tree[node.parent]) + 1

n = int(raw_input())
dict = {}
tree = []

for i in range(n):
    a = map(int, raw_input().split())
    if len(a) > 2:
        dict[a[0]] = Node(a[0], a[1], a[2:])
    else:
        dict[a[0]] = Node(a[0], a[1], [], nodetype='leaf')

for i in range(n):
    tree.append(dict[i])

for i in range(n):
    children = tree[i].child
    for j in children:
        tree[j].parent = tree[i].id

for i in range(n):
    tree[i].depth = calcDepth(tree[i])
    if tree[i].parent != -1 and tree[i].child != []:
        tree[i].nodetype = 'internal node'
    elif tree[i].parent == -1:
        tree[i].nodetype = 'root'
        
for i in range(n):
    tree[i].showFinal()

Submission status: Accepted

Solution code:
import sys

NIL = -1

def set_depth(v, depth):
    tree[v][2] = depth
    
    for child in tree[v][1]:
        set_depth(child, depth + 1)

N = int(input())
tree = [[NIL, [], 0, 'leaf'] for _ in range(N)]

for _ in range(N):
    line = [int(i) for i in sys.stdin.readline().split()]
    t_id = line[0]
    children = line[2:]
    tree[t_id][1] = children
    
    if children:
        tree[t_id][3] = 'internal node'
    
    for child in children:
        tree[child][0] = t_id
        
for t_id in range(N):
    if tree[t_id][0] == NIL:
        tree[t_id][3] = 'root'
        r = t_id
        break

set_depth(r, 0)

for t_id in range(N):
    parent = tree[t_id][0]
    depth = tree[t_id][2]
    children = tree[t_id][1]
    type_t = tree[t_id][3]
    
    print('node {}: parent = {}, depth = {}, {}, {}'.format(t_id, parent, depth, type_t, children))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
tree = {n:{} for n in range(N)}
children = set()

for n in range(N):
    inp = [int(m) for m in input().split()]
    tree[inp[0]]["leaf"] = inp[2:]
    children.update(inp[2:])

parent = set([n for n in range(N)]).difference(children).pop()
tree[parent]["depth"] = 0
tree[parent]["parent"] = -1

siblings = tree[parent]["leaf"]
for c in siblings:
    tree[c]["depth"] = 1
    tree[c]["parent"] = parent

depth = 2
while len(children):
    children = children.difference(siblings)
    next_gen = []
    for s in siblings:
        next_gen.extend(tree[s]["leaf"])
        for c in tree[s]["leaf"]:
            tree[c]["depth"] = depth
            tree[c]["parent"] = s
    siblings = next_gen
    depth += 1

    
for n in range(N):
    if tree[n]["depth"] == 0:
        tree[n]["type"] = "root"
    elif tree[n]["leaf"] == []:
        tree[n]["type"] = "leaf"
    else:
        tree[n]["type"] = "internal node"
        
    print("node {}: parent = {}, depth = {}, {}, {}" \
              .format(n, tree[n]["parent"], tree[n]["depth"], tree[n]["type"], tree[n]["leaf"]))

Submission status: Accepted

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


N = int(input())
tree = {n:{"parent":-1, "left": -1, "right": -1} for n in range(N)} # left-child right-sibing
parent = set([n for n in range(N)])
for n in range(N):
    inp = [int(n) for n in input().split()]
    tree[inp[0]]["children"] = inp[2:]

    tree[inp[0]]["left"] = inp[2] if len(inp) > 2 else -1
    
    for ip in inp[2:]:
        tree[ip]["parent"] = inp[0]
    
    for i, ip in enumerate(inp[2:-1]):
        tree[inp[2+i]]["right"] = inp[3+i]
    parent = parent.difference(inp[2:])    

def set_depth(n, depth):
    print(depth)
    tree[n]["depth"] = depth
    if tree[n]["left"] != -1:
        set_depth(tree[n]["left"], depth+1)
    if tree[n]["right"] != -1:
        set_depth(tree[n]["right"], depth)

def get_depth(n):
    d = 0
    while tree[n]["parent"] != -1:
        d += 1
        n = tree[n]["parent"]
    return d

#set_depth(parent.pop(), 0)
        
for n in range(N):
    tree[n]["depth"] = get_depth(n)
    if tree[n]["parent"] == -1:
        tree[n]["type"] = "root"
    elif tree[n]["children"] != []:
        tree[n]["type"] = "internal node"
    else:
        tree[n]["type"] = "leaf"
        
    print("node {}: parent = {}, depth = {}, {}, {}"\
          .format(n, tree[n]["parent"], tree[n]["depth"], tree[n]["type"], tree[n]["children"]))

Submission status: Accepted

Solution code:
def rootedtrees():
    def set_depth(node_id):
        if tree[node_id]['parent'] == -1:
            return 0
        else:
            return set_depth(tree[node_id]['parent']) + 1

    n = int(input())

    tree = [{'parent': -1, 'depth': 0, 'node_type': 'leaf', 'children': []}
            for i in range(n)]

    for i in range(n):
        line = list(map(int, input().split()))
        node_id = line[0]
        children = line[2:]

        for child in children:
            tree[child]['parent'] = node_id

        if children:
            tree[node_id]['node_type'] = 'internal node'

        tree[node_id]['children'] = children

    for node_id in range(n):
        tree[node_id]['depth'] = set_depth(node_id)

        if tree[node_id]['parent'] == -1:
            tree[node_id]['node_type'] = 'root'

    for node_id in range(n):
        parent = tree[node_id]['parent']
        depth = tree[node_id]['depth']
        node_type = tree[node_id]['node_type']
        children = tree[node_id]['children']

        print('node {}: parent = {}, depth = {}, {}, {}'.format
            (node_id, parent, depth, node_type, children))

if __name__ == '__main__':
    rootedtrees()

Submission status: Accepted

Solution code:
N = int(input())
tree = [[-1, 0, []] for _ in [0]*N]

for _ in [0]*N:
    a = tuple(map(int, input().split()))
    v = a[0]
    n = a[1]
    children = list(a[2:])
    tree[v][2] = children
    for child in children:
        tree[child][0] = v

q = [a[2] for a in tree if a[0] == -1][0]
d = 1
while q:
    for v in q:
        tree[v][1] = d
    q = [n for v in q for n in tree[v][2]]
    d += 1

for i in range(N):
    v = tree[i]
    parent = v[0]
    depth = v[1]
    children = v[2]
    node_type = "root" if parent == -1 else "leaf" if len(children) == 0 else "internal node"
    print("node %d: parent = %d, depth = %d, %s, %s" % (i, parent, depth, node_type, str(children)))

Submission status: Accepted

Solution code:
def set_pdt(i, p, d):
    u = tree[i]
    u[0], u[1] = p, d
    for c in u[3]:
        set_pdt(c, i, d+1)
    else:
        if u[0] == -1:
            u[2] = "root"
        elif u[3]:
            u[2] = "internal node"
        else:
            u[2] = "leaf"

n = int(input())
#         p d t ch
tree = [[-1,0,0,0] for _ in range(n)]
root = set(range(n))

for _ in range(n):
    i, k, *c = map(int, input().split())
    tree[i][3] = c
    root -= set(c)
    
for u in root:
    set_pdt(u, -1, 0)

for i in range(n):
    u = tree[i]
    print("node {}: parent = {}, depth = {}, {}, {}".format(i, *u))

Submission status: Accepted

Solution code:
def set_pdt(i, p, d):
    u = tree[i]
    u[0], u[1] = p, d
    for c in u[3]:
        set_pdt(c, i, d+1)
    else:
        if u[0] == -1:
            u[2] = "root"
        elif u[3]:
            u[2] = "internal node"
        else:
            u[2] = "leaf"

n = int(input())
tree = [[-1,0,0,0] for _ in range(n)]
root = set(range(n))

for _ in range(n):
    i, k, *c = map(int, input().split())
    tree[i][3] = c
    root -= set(c)
    
set_pdt(root.pop(), -1, 0)

for i in range(n):
    u = tree[i]
    print("node {}: parent = {}, depth = {}, {}, {}".format(i, *u))

Submission status: Accepted

Solution code:
def set_info(a, i, p, d):
    a[i][1], a[i][2] = p, d
    for b in a[i][0]:
        set_info(a, b, i, d + 1)

n = int(input())
tree = [[None] for i in range(n)]
root = set(range(n))

for i in range(n):
    l = list(map(int, input().split()))
    tree[l[0]] = [l[2:], None, None]
    root -= set(l[2:])

set_info(tree, root.pop(), -1, 0)

for i in range(n):
    c, p, d = tree[i]
    if p == -1:
        t = "root"
    elif len(c) == 0:
        t = "leaf"
    else:
        t = "internal node"
    print("node ", i, ": parent = ", p, ", depth = ", d, ", ", t, ", ", c, sep="")

Submission status: Accepted

Solution code:
def dfs(here, p, connect, depth, parent, d):
    parent[here] = p
    depth[here] = d
    for c in connect[here]:
        dfs(c, here, connect, depth, parent, d + 1)

from collections import defaultdict
v_num = int(input())
connect = defaultdict(list)
parent = [-1 for n in range(v_num)]
in_v = [0 for n in range(v_num)]
depth = [0 for n in range(v_num)]
for _ in range(v_num):
    inp = [int(n) for n in input().split(" ")]
    connect[inp[0]].extend(inp[2:])
    for c in inp[2:]:
        in_v[c] += 1
for i, n in enumerate(in_v):
    if not n:
        root = i
dfs(root, -1, connect, depth, parent, 0)
for v in range(v_num):
    if v == root:
        is_type = "root"
    elif len(connect[v]) == 0:
        is_type = "leaf"
    else:
        is_type = "internal node"
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(v, parent[v], depth[v], is_type, connect[v]))