結果

問題 No.1787 Do Use Dynamic Tree
ユーザー lam6er
提出日時 2025-03-31 17:51:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,544 bytes
コンパイル時間 258 ms
コンパイル使用メモリ 82,880 KB
実行使用メモリ 105,692 KB
最終ジャッジ日時 2025-03-31 17:52:42
合計ジャッジ時間 20,233 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(stdin.readline())
    adj = [[] for _ in range(N+1)]  # 1-based

    for _ in range(N-1):
        a, b = map(int, stdin.readline().split())
        adj[a].append(b)
        adj[b].append(a)

    val = list(range(N+1))  # val[i] is the value of node i

    Q = int(stdin.readline())
    prev_x = 0
    for _ in range(Q):
        ui, vi = map(int, stdin.readline().split())
        # Compute encrypted u and v
        mod = N
        u = ((ui + (N - 1) + prev_x) % mod) + 1
        v = ((vi + (N - 1) + prev_x) % mod) + 1

        # Swap values
        val[u], val[v] = val[v], val[u]

        # Simulate the path to find ans
        current = u
        prev_node = -1
        ans = current
        while True:
            next_nodes = [node for node in adj[current] if node != prev_node]
            if not next_nodes:
                break
            # Find max val and the candidates
            max_val = -1
            candidates = []
            for node in next_nodes:
                if val[node] > max_val:
                    max_val = val[node]
                    candidates = [node]
                elif val[node] == max_val:
                    candidates.append(node)
            # Choose the candidate with largest node number
            next_node = max(candidates)
            prev_node = current
            current = next_node
            ans = current

        print(ans)
        prev_x = ans

if __name__ == "__main__":
    main()
0