結果

問題 No.2258 The Jikka Tree
ユーザー gew1fw
提出日時 2025-06-12 21:45:01
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,644 bytes
コンパイル時間 386 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 276,004 KB
最終ジャッジ日時 2025-06-12 21:49:52
合計ジャッジ時間 19,001 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6 WA * 2 TLE * 1 -- * 66
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
sys.setrecursionlimit(1 << 25)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0

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

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

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

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

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

    X = []
    X_true = []

    in_time = [0]*N
    out_time = [0]*N
    time = 0
    parent = [ -1 ] * N
    visited = [False] * N

    def dfs(u):
        nonlocal time
        visited[u] = True
        in_time[u] = time
        time +=1
        for v in tree[u]:
            if not visited[v]:
                parent[v] = u
                dfs(v)
        out_time[u] = time -1

    dfs(0)

    def get_sum_subtree(v, l, r, A, k):
        pass

    for q in range(Q):
        a_prime, b_prime, k_prime, delta = queries[q]
        X_prev = X if q==0 else X

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

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

        T = 0
        for w in range(l, r):
            T += (A[w] + k)

        sum_subtree = [0] * N

        def compute_subtree(v):
            s = (A[v] + k) if l <= v < r else 0
            for child in tree[v]:
                if parent[child] == v:
                    compute_subtree(child)
                    s += sum_subtree[child]
            sum_subtree[v] = s

        compute_subtree(0)

        def find_median(v):
            max_child_sum = 0
            for child in tree[v]:
                if parent[child] == v:
                    if sum_subtree[child] > max_child_sum:
                        max_child_sum = sum_subtree[child]
            if max_child_sum > T / 2:
                for child in tree[v]:
                    if parent[child] == v and sum_subtree[child] > T/2:
                        return find_median(child)
            else:
                return v

        median = find_median(0)
        X.append(median)
        X_true.append(median)

    for x in X_true:
        print(x)

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