[白俊]21738号:氷を砕いたペンギンの答え

質問する
道度は退屈にテーブルゲームカフェに行きました.ちょうど普段から好きな氷を割るペンギンのアップグレード版で、特殊な氷を割るペンギンの将棋ゲームが出てきて、自分で遊ぶことにしました.特殊破氷ペンギンゲームには特殊メガネがあり、特殊メガネをかけて氷を見ると、氷の間の接続関係が見えます.
特殊破氷ペンギンゲームでは氷の種類をサポートする氷と普通の氷の2種類があります.支えの役割を果たす氷には、赤で仕切られています
普通の氷を支えて、普通の氷が砕けないように手伝ってみることができます.一般的には、1つのブラケットだけがつながっていても氷は砕けませんが、ペンギンが登った氷は2つ以上のブラケットの役割を果たす氷を接続しなければなりません.氷は砕けません.この場合、ブラケット接続とは、ブラケットから異なる通常の氷で接続されることを意味する.特殊破氷ペンギンゲームで、高島はペンギンを落とさずに最大何枚の氷を破ることができますか?

入力
1行目は、氷の個数N(N(3<=N<=328000)と、支持作用を果たす氷の個数S(S(2<=S<=N−1)、ペンギンが存在する氷の番号PPP(S<=P<=N)を与える.支持する氷の個数がSSSの場合、111番からSSS番までの氷が支持する.
2行目からN−1 N−1 N−1行には2つの整数AAA,BBBがある.これはAAA号氷とBBB号氷がつながっていることを意味し、同じ接続は何度も与えられない.
ゲームが始まると、ペンギンは普通の氷の上にあり、氷が砕けていない状態で始まります.各氷は111番からNNN番まで整数で、2つの異なる氷を結ぶ経路は1つしかありません.また、ペンギンが登った氷を通らずに異なるブラケットがつながっている場合はありません.
しゅつりょく
プレイヤーがペンギンを破って落ちない氷の最大数を求める.支えの役割を果たす氷も破れる氷だ.
初回アクセス

ペンギンはそれぞれ立っている氷とつながっている6つの氷を探索した.

6個の氷から柱氷までの個数を求めます.

6個の氷のうち、最も少ない2個の氷の数の和を除いて、すべての氷が破砕します.

2回目のアクセス

柱氷の上を一つ一つ探索し、ペンギンがいる位置まで数えます.

個の数が最小の2個で、すべての氷を除く.

ペンギンが立っている氷を考慮して1を追加.

完全なコード

import sys

input = sys.stdin.readline
# 재귀함수 횟수 제한을 늘려줌
sys.setrecursionlimit(999999)

N, S, P = map(int, input().split())
graph = [[] for i in range(N + 1)]

# 각각 얼음이 연결된 관계를 그래프로 저장
for i in range(N - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

iceBroken = []
# 방문한 얼음
visited = [0] * (N+1)


def dfs(n, cnt):
    # 현재 방문한 얼음이 펭귄이 서있는 곳이면
    # 해당 기둥의 연결 얼음 갯수 반환
    if n == P:
        iceBroken.append(cnt)
        return
    visited[n] = 1
    for i in graph[n]:
        # 해당 얼음과 연결된 얼음 탐색
        if not visited[i]:
            dfs(i, cnt + 1)

# 6개의 얼음 기둥 탐색
for i in range(1, S+1):
    dfs(i, 0)

iceBroken.sort()

# 전체 얼음 - 가장 연결갯수가 적은 기둥 2개 - 펭귄이 서있는 얼음
print(N - iceBroken[0] - iceBroken[1] - 1)

再帰関数を使用せずにキューのみを使用して検索する場合、答えは正しいが、タイムアウトの問題は解決できない.再帰関数にはもっと演算時間がかかると思いますが、必ずしもそうではありません...