蓝桥杯左儿子右兄弟（不用树和DFS）

作为初学者我不太会用python来实现树结构，所以想了一个不用树和dfs的方法。

n=int(input())
father=[0 for i in range(n+5)]        #father[i]为i的父节点序号
depth=[0 for i in range(n+5)]        #该节点的最大深度，叶节点为0，题目所求为depth[1]
son=[0 for i in range(n+5)]        #i节点儿子个数
for i in range(2,n+1):        
    m=int(input())
    father[i]=m
    son[m]+=1
for i in range(n,0,-1):        
    f=father[i]        
    deep=depth[i]+son[f]        
    if deep>depth[f]:        
        depth[f]=deep        
print(depth[1])     

第一个for循环确定father和son的个数

第二个for循环反向遍历节点，根据题目的条件，父节点序号小于子节点，于是子节点总是比父节点先遍历。

然后根据 depth[father]=son个数+max{depth[son1],depth[son2]......}

在遍历i节点时将(depth[i]+son[father[i]])与目前的depth[father[i]]比较，若更大，就更新depth[father[i]]的值。

最后输出depth[1]即可。