再帰関数をループ処理に変換

Question

競プロ AOJ:Traffic Tree をpythonで全方位木DPを実装しています。
exp:23でエラー：再帰上限エラーだと思います。
なので、dfs1, dfs2をループ処理に変換したいのですがご教示おねがいします。

def resolve():
def dfs1(idx, par):
for to in G[idx]:
if to == par:
continue
dfs1(to, idx)
dist[idx] = max(dist[idx]+1, dist[to])

def dfs2(idx, d_par, par):
    d_child = []
    d_child.append((0, -1))
    for to in G[idx]:
        if to == par:
            d_child.append((d_par + 1, to))
        else:
            d_child.append((dist[to] + 1, to))
    d_child.sort(reverse=True)
    ans[idx] = d_child[0][0]
    for to in G[idx]:
        if to == par:
            continue
        nx_d_par = d_child[d_child[0][1] == to][0]
        dfs2(to, nx_d_par, idx)


N = int(input())

G = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(lambda x:int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)

dist = [0]*N
ans = [0]*N
dfs1(0,-1)
dfs2(0, 0, -1)
for i in range(N):
    print(2*(N-1) - ans[i])

Comments

[Penpen7]

コードの挿入を使ってコードを貼り付けてください。インデントが潰れるとコードが読めません。

Answer 1

解決しました。

    def dfs1(topo, par):
        for idx in reversed(topo):
            for to in G[idx]:
                if to == par[idx]:
                    continue
                dist[idx] = max(dist[idx], dist[to] + 1)

    def dfs2(idx, d_par, par):
        stack = [(idx,d_par, par)]
        while stack:
            idx, d_par, par = stack.pop()
            d_child = []
            d_child.append((0, -1))
            for to in G[idx]:
                if to == par:
                    d_child.append((d_par + 1, to))
                else:
                    d_child.append((dist[to] + 1, to))
            d_child.sort(reverse=True)
            ans[idx] = d_child[0][0]
            for to in G[idx]:
                if to == par:
                    continue
                nx_d_par = d_child[d_child[0][1] == to][0]
                stack.append((to, nx_d_par, idx))コード