結果

問題 No.1641 Tree Xor Query
ユーザー lam6er
提出日時 2025-03-20 19:03:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 237 ms / 5,000 ms
コード長 2,733 bytes
コンパイル時間 345 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 142,500 KB
最終ジャッジ日時 2025-03-20 19:03:30
合計ジャッジ時間 3,142 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N, Q = int(data[ptr]), int(data[ptr+1])
    ptr += 2
    C = list(map(int, data[ptr:ptr+N]))
    ptr += N

    # Build adjacency list
    adj = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a = int(data[ptr])
        b = int(data[ptr+1])
        ptr +=2
        adj[a].append(b)
        adj[b].append(a)
    
    # Compute in_time and out_time using iterative DFS
    in_time = [0] * (N +1)
    out_time = [0] * (N +1)
    time =0
    stack = [(1, False, -1)]  # node, visited, parent

    while stack:
        node, visited, parent = stack.pop()
        if not visited:
            # Mark in_time when first visiting
            time +=1
            in_time[node] = time
            # Push back as visited
            stack.append( (node, True, parent) )
            # Push children in reversed order (so that when popped, processed in order)
            # Collect children (excluding parent)
            children = []
            for neighbor in adj[node]:
                if neighbor != parent:
                    children.append(neighbor)
            # Push children in reversed order
            for child in reversed(children):
                stack.append( (child, False, node) )
        else:
            # Mark out_time when done with all children
            out_time[node] = time
    
    # Fenwick Tree implementation for XOR
    class FenwickTree:
        def __init__(self, size):
            self.n = size
            self.tree = [0]*(self.n +1)  # 1-based
        
        def update(self, idx, delta):
            # XOR delta to position idx
            while idx <= self.n:
                self.tree[idx] ^= delta
                idx += idx & -idx
        
        def query(self, idx):
            # Compute XOR from 1 to idx
            res =0
            while idx >0:
                res ^= self.tree[idx]
                idx -= idx & -idx
            return res
    
    # Initialize Fenwick Tree
    ft = FenwickTree(N)
    for i in range(1, N+1):
        pos = in_time[i]
        ft.update(pos, C[i-1])
    
    # Process queries
    output = []
    for _ in range(Q):
        T_j = int(data[ptr])
        x_j = int(data[ptr+1])
        y_j = int(data[ptr+2])
        ptr +=3
        
        if T_j ==1:
            pos = in_time[x_j]
            ft.update(pos, y_j)
        else:
            l = in_time[x_j]
            r = out_time[x_j]
            xor_r = ft.query(r)
            xor_l_1 = ft.query(l-1) if l >1 else 0
            res = xor_r ^ xor_l_1
            output.append(str(res))
    
    print('\n'.join(output))

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