結果

問題 No.2258 The Jikka Tree
ユーザー gew1fw
提出日時 2025-06-12 17:14:58
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,960 bytes
コンパイル時間 402 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 96,556 KB
最終ジャッジ日時 2025-06-12 17:15:08
合計ジャッジ時間 9,334 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 1 TLE * 1 -- * 71
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict, deque

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read().split()
    ptr = 0

    N = int(input[ptr])
    ptr += 1

    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        u = int(input[ptr])
        v = int(input[ptr+1])
        ptr += 2
        edges[u].append(v)
        edges[v].append(u)

    A = list(map(int, input[ptr:ptr+N]))
    ptr += N

    Q = int(input[ptr])
    ptr += 1

    queries = []
    for _ in range(Q):
        a_prime = int(input[ptr])
        b_prime = int(input[ptr+1])
        k_prime = int(input[ptr+2])
        delta = int(input[ptr+3])
        ptr +=4
        queries.append( (a_prime, b_prime, k_prime, delta) )

    # Precompute distance from each node to all others
    dist = [ [0]*N for _ in range(N) ]
    for i in range(N):
        q = deque()
        q.append(i)
        visited = [False]*N
        visited[i] = True
        while q:
            u = q.popleft()
            for v in edges[u]:
                if not visited[v]:
                    dist[i][v] = dist[i][u] + 1
                    visited[v] = True
                    q.append(v)

    X = []
    sum_X = 0
    for q_idx in range(Q):
        a_prime, b_prime, k_prime, delta = queries[q_idx]

        if q_idx ==0:
            a = a_prime
            b = b_prime
            k = k_prime
        else:
            a = (a_prime + sum_X) % N
            b = (b_prime + 2 * sum_X) % N
            k = (k_prime + (sum_X **2)) % 150001

        l = min(a, b)
        r = max(a, b) + 1

        min_f = float('inf')
        best_v = -1
        for v in range(N):
            total = 0
            for w in range(l, r):
                total += (A[w] + k) * dist[v][w]
            if total < min_f:
                min_f = total
                best_v = v

        X.append(best_v)
        sum_X += best_v

    for x in X:
        print(x)

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