以下問題についてです。
atcorder 270 問題3
https://atcoder.jp/contests/abc270/tasks/abc270_c
提出したところ10問のテストが時間切れとなってしまいます。
現在pythonでatcorderに取り組んでいるのはpython力をつけたいという目的もあり、他の言語は使いたくないと考えています。
pythonでかつ再帰処理を使って時間切れとならずに解く方法はありますでしょうか?
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()