Problem:
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.  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**

Incorrect submission (verdict: Wrong Answer):
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_A&lang=jp
class RootedTree:
    def __init__(self, node, parent_node):
        self.id = node[0]
        self.parent = parent_node
        self.item = node[2:]
        self.children = []
        self.depth = 0
        self.type = None
        self.next_id_node = None
        
        if parent_node == None:
            self.type = "root"
        else:
            parent_node.type = "internal node"
            self.type = "leaf"
            self.depth = parent_node.depth + 1
            
    def filled(self):
        return len(self.children) == len(self.item)
    
    def show_self(self):
        if self.parent == None:
            parent_id = -1
        else:
            parent_id = self.parent.id
        print("node " + str(self.id) + ":" + " parent = " + str(parent_id) + ", depth = " + str(self.depth)+ ", " + self.type + ", " + str(self.item))

def make_tree(trees):
    root = None
    target_node = None
    for node in trees:
        if target_node == None:
            root = RootedTree(node, None)
            target_node = root
            root.show_self()
        else:
            child = RootedTree(node, target_node)
            child.show_self()
            target_node.next_id_node = child
            target_node.children.append(child)
            target_node = child
            while target_node.filled():
                target_node = target_node.parent
                if not target_node:
                    break
                
    return root
def main():
    n_trees = int(input())
    trees = [[int(a) for a in input().split()] for i in range(n_trees)]

    make_tree(trees)
    
if __name__ == "__main__":
    main()

Fixed, accepted submission:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_A&lang=jp
"""
class RootedTree:
    def __init__(self):
        self.id = None
        self.child = []
        self.parent = -1
        self.node_type = "root"
        self.depth = 0

    def show(self):
        print("node {}: parent = {}, depth = {}, {}, {}".format(self.id, self.parent, self.depth, self.node_type, self.child))

def cal_depth(tree, node, cur_depth):
    node.depth += cur_depth
    #node.show()
    for index in node.child:
        cal_depth(tree, tree[index], cur_depth + 1)
        
def make_tree(tree_data):#?????????,?¨???????n^2
    tree = [RootedTree() for i in range(len(tree_data))]
    
    for data in tree_data:
        focus = tree[data[0]]
        focus.id = data[0]
        
        if data[2:]:
            focus.child = data[2:]
            
            for child_index in data[2:]:
                tree[child_index].parent = data[0]
                
                if tree_data[[a[0] for a in tree_data].index(child_index)][2:]:
                    tree[child_index].node_type = "internal node"
                else:
                    tree[child_index].node_type = "leaf"
            
    root_index = [n.node_type for n in tree].index("root")
    cal_depth(tree, tree[root_index], 0)
    return tree
"""
def set_tree_data(tree, target, parent, depth):
    tree[target]["depth"] += depth
    tree[target]["parent"] = parent

    for c in tree[target]["child"]:
        set_tree_data(tree, c, target, depth + 1)

def make_tree_revision(tree_data, n_tree):
    tree = [{"parent": None, "depth":0, "child" : None} for i in range(n_tree)]
    root = sum(range(n_tree))
    
    for node_data in tree_data:
        tree[node_data[0]]["child"] = node_data[2:]
        root -= sum(node_data[2:])

    set_tree_data(tree, root, -1, 0)
    return tree

def main():
    n_tree = int(input())
    tree_data = [[int(a) for a in input().split()] for i in range(n_tree)]
    
    for i, node in enumerate(make_tree_revision(tree_data, n_tree)):
        category = "root"
        if (not node["parent"] == -1) and node["child"]:
            category = "internal node"
        elif not node["parent"] == -1:
            category = "leaf"

        print("node {}: parent = {}, depth = {}, {}, {}".format(i, node["parent"], node["depth"], category, node["child"]))
if __name__ == "__main__":
    main()