結果

問題 No.2258 The Jikka Tree
ユーザー gew1fw
提出日時 2025-06-12 17:12:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,447 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 82,764 KB
実行使用メモリ 90,972 KB
最終ジャッジ日時 2025-06-12 17:13:07
合計ジャッジ時間 20,063 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7 WA * 12 TLE * 1 -- * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

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

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

    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        u = int(data[ptr])
        v = int(data[ptr+1])
        ptr +=2
        edges[u].append(v)
        edges[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) )

    # Precompute Euler Tour and depth, parent
    parent = [0]*N
    depth = [0]*N
    entry = [0]*N
    exit_ = [0]*N
    time = 0
    visited = [False]*N

    def dfs(u, p):
        nonlocal time
        visited[u] = True
        parent[u] = p
        entry[u] = time
        time +=1
        for v in edges[u]:
            if not visited[v]:
                depth[v] = depth[u] +1
                dfs(v, u)
        exit_[u] = time -1

    dfs(0, -1)

    # Build a segment tree for the Euler Tour
    class SegmentTree:
        def __init__(self, size):
            self.n = 1
            while self.n < size:
                self.n <<=1
            self.size = size
            self.tree = [0]*(2*self.n)
        
        def update(self, pos, val):
            pos += self.n
            self.tree[pos] = val
            while pos >1:
                pos >>=1
                self.tree[pos] = self.tree[2*pos] + self.tree[2*pos+1]
        
        def query(self, l, r):
            res =0
            l += self.n
            r += self.n
            while l <= r:
                if l %2 ==1:
                    res += self.tree[l]
                    l +=1
                if r %2 ==0:
                    res += self.tree[r]
                    r -=1
                l >>=1
                r >>=1
            return res

    # Prepare for each query
    X = []
    sum_X = 0
    for q in range(Q):
        a_prime, b_prime, k_prime, delta = queries[q]
        if q ==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

        T = 0
        sum_A_plus_k = 0
        st = SegmentTree(N)
        for w in range(l, r):
            c = A[w] + k
            T += c
            st.update(entry[w], c)
        
        # Now find the weighted median
        def find_median(v):
            total = T
            visited = {}
            stack = [v]
            while stack:
                u = stack.pop()
                if u in visited:
                    continue
                visited[u] = True
                max_sub = 0
                for child in edges[u]:
                    if child == parent[u]:
                        continue
                    s = st.query(entry[child], exit_[child])
                    if s > T/2:
                        stack.append(child)
                        break
                else:
                    return u
            return v
        
        v = find_median(0)
        X.append(v)
        sum_X += v

    for x in X:
        print(x)

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