Python で再帰処理を高速化するには？


以下問題についてです。

atcorder 270 問題3  
<https://atcoder.jp/contests/abc270/tasks/abc270_c>

提出したところ10問のテストが時間切れとなってしまいます。

現在pythonでatcorderに取り組んでいるのはpython力をつけたいという目的もあり、他の言語は使いたくないと考えています。

pythonでかつ再帰処理を使って時間切れとならずに解く方法はありますでしょうか？

[code]

    import sys
    def trace(l,traced,x,y):
        # nodeが持つリンクを全て調査
        flg = 0
        for i in l[x]:
            # 追跡済みじゃなければ値を追加
            if i not in traced:
                traced.append(i)
                flg+=1
                # 目標に到達したら終了
                if i == y:
                    return True
                # 終了以外は追跡を継続
                if not trace(l,traced,i,y):
                    traced.pop()
                    flg -= 1
        # ノードが次の接続先を持っていたかいなか
        return flg
    
    def resolve():
        input = sys.stdin.readline
    
        N,X,Y=map(int, input().split())
    
        l = [[] for _ in range(N+1)]
    
        for _ in [0]*(N-1):
            A,B = map(int,input().split())
            l[A].append(B)
            l[B].append(A)
    
        traced = [X]
        
        trace(l,traced,X,Y)
        
        print(' '.join([str(s) for s in traced]))
    resolve()
    
[/code]



[code]

    # 追跡済みじゃなければ値を追加
    if i not in traced:
    
[/code]

この部分で、追跡済みかどうかを毎回線形探索しているのは効率が悪いです。今回 N が最大 200000
まで達するので、この行で繰り返し行われている探索の時間が問題になります。追跡済みかどうかをすぐ判定できるようにフラグを配列で保持するのが良いでしょう。

