Python中默认的递归深度限制为$1000$，查看默认递归深度限制代码如下

import sys
print(sys.getrecursionlimit())

当然可以通过修改将递归深度限制增大一些，通过下面的代码

import sys
sys.setrecursionlimit(1000000000)

但是根据笔者的经验来讲，递归深度最大增大到$10^5$级别，然后再增大就没用了，这在解决图或者树上的问题的时候这点递归深度根本不够。
比如Acwing1207大臣的旅费和 Acwing3425左孩子右兄弟

这两题都是典型的树上的问题，因为树本身就是递归定义的，所以一般来讲树的算法经常涉及dfs和递归，但是Python对递归的支持又很不友好？怎么办呢？

方案1: dfs改bfs

树或图上的算法很多都分别有dfs和bfs的实现，比如说最短路问题和树的直径问题用bfs和dfs都可以解决。这个时候如果用Python写的话尽量用bfs实现
例如Acwing1207大臣的旅费
题意是求树的直径，跑两遍dfs或者bfs就可以解决

如果用仿C风格的dfs写法会发生Segmentation Fault，代码如下

# 仿C风格
import sys
sys.setrecursionlimit(100000000)
n = int(input())
E = [[]for i in range(n)]
maxlen = 0
maxfar = 0
def dfs(start, fa, length):
    global maxlen,maxfar
    for i in E[start]:
        if i[0] != fa:
            if maxlen < length + i[1]:
                maxlen = length+i[1]
                maxfar = i[0]
            dfs(i[0], start, length+i[1])
for i in range(n-1):
    a, b, c = map(int, input().split())
    E[a - 1].append([b - 1, c])
    E[b - 1].append([a - 1, c])
dfs(0, -1, 0)
dfs(maxfar, -1, 0)
print(int(maxlen*10+(maxlen+1)*maxlen/2))

但是我们可以改成非递归的bfs就可以通过本题啦

# 仿C风格
import sys
from collections import deque
sys.setrecursionlimit(100000000)
n = int(input())
E = [[]for i in range(n)]

def bfs(st):
    q = [0 for i in range(n)]
    d = [-1 for i in range(n)]
    hh, tt = 0, -1
    tt += 1;
    q[tt] = st
    d[st] = 0
    while hh <= tt:
        t = q[hh]
        hh += 1
        for item in E[t]:
            if d[item[0]] == -1:
                d[item[0]] = d[t] + item[1];
                tt += 1;
                q[tt] = item[0]
                # q.append(item[0])
    maxfar, maxlen = 0, -1
    for i in range(n):
        if(d[i] > maxlen):
            maxlen = d[i]
            maxfar = i
    return maxfar, maxlen

for i in range(n-1):
    a, b, c = map(int, input().split())
    E[a - 1].append([b - 1, c])
    E[b - 1].append([a - 1, c])
maxfar, maxlen = bfs(0)
maxfar, maxlen = bfs(maxfar)
print(int(maxlen*10+(maxlen+1)*maxlen/2))

方案2: 用手写栈代替系统栈

很多时候很多的类似树形dp的问题无法用bfs解决，只能用bfs解决，这个时候怎么办呢？
递归的过程实际上是通过系统栈进行的，我们可以用手写栈模拟递归的调用过程。
举例Acwing3425左孩子右兄弟

dfs写法非常好写但是会发生Segmentation Fault，代码如下

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

def dfs(u):
    maxv = max([dfs(e) for e in g[u]]) if len(g[u]) else 0
    return maxv + len(g[u])

n = int(input())
g = [[] for i in range(n + 1)]
for i in range(2, n + 1):
    x = int(input())
    g[x].append(i)
print(dfs(1))

我们用手写栈模拟系统栈的调用，dfs过程中每个结点都会遇到两次，第一次是往下递归的时候，第二次是回溯的时候，dfs过程中的操作可能是在递归的时候做，也可能是在回溯的时候做。即我们每次处理栈顶元素，如果我们是第一次遇到的这个结点，说明当前是递归过程，我们把递归的时候该做的事情都做了，然后把当前结点所有的儿子加到栈中，如果是第二次遇到这个结点，那么我们就完成回溯过程需要做的事情然后把元素出栈。这样我们就用手写栈模拟了递归的过程。代码如下。

import sys
input = sys.stdin.readline

n = int(input())
g = [[] for i in range(n + 1)]
for i in range(2, n + 1):
    x = int(input())
    g[x].append(i)
f = [0 for i in range(n + 1)]
v = [0 for i in range(n + 1)]
stk = [1]
while stk:
    top = stk[-1]
    if not v[top]:
        v[top] = 1
        stk += g[top]
    else:
        stk.pop()
        f[top] = len(g[top]) + (max(f[e] for e in g[top]) if g[top] else 0)
print(f[1])