[zerojudge] c463: apcs 樹狀圖分析 (Tree Analyses)

class node:
    def __init__(self):
        self.index = 0
        self.parent = 0
        self.height = 0
        self.child = False
    
from sys import stdin
n = int(stdin.readline())
nodes = {k: node() for k in range(1, n+1)} 
# 初始化節點   
for i in range(1, n+1):
    s = stdin.readline().strip()
    nodes[i].index = i
    if(s != '0'):
        tmp = [int(x) for x in s.split()][1:]
        nodes[i].child = True
        for x in tmp: nodes[x].parent = i
    # 依序讀入測資，紀錄每個 node 的屬性
    
root = [v for v in nodes.values() if v.parent == 0][0]
print(root.index)
# 尋找 root , root 沒有 parent
  
leaves = [v for v in nodes.values() if not v.child]
# 尋找 leaf , leaf 沒有 child
# 由 leaf 往上數，並記錄 height  
for leaf in leaves:
    cnt = 1
    nxt = leaf.parent
    while(1):
        if(cnt <= nodes[nxt].height): break
        nodes[nxt].height = cnt
        '''
        數到某一個 node 發現有 height
        如果 cnt > height 表示這個深度較深，
        繼續往上，反之脫離。
        '''
        nxt = nodes[nxt].parent
        if(nxt == 0): break
        # 繼續往上推
        cnt += 1
ans = sum([v.height for v in nodes.values()])
# 加總每個節點的高度
print(ans)