結果
問題 | No.1641 Tree Xor Query |
ユーザー |
![]() |
提出日時 | 2021-12-03 00:31:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 317 ms / 5,000 ms |
コード長 | 1,287 bytes |
コンパイル時間 | 286 ms |
コンパイル使用メモリ | 82,240 KB |
実行使用メモリ | 171,940 KB |
最終ジャッジ日時 | 2024-07-05 02:54:06 |
合計ジャッジ時間 | 3,827 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
from sys import stdinn, q, *indata = map(int, stdin.read().split())c = [indata[i] for i in range(n)]g = [[] for i in range(n+1)]offset = nfor i in range(n-1):s, t = indata[offset + 2*i],indata[offset + 2*i+1]g[s].append(t)g[t].append(s)offset += (n-1)*2intime = [0 for i in range(n+1)]outtime = [0 for i in range(n+1)]que = [(1,0)]check = [False for i in range(n+1)]time = 1while que:now, inout = que.pop()if inout == 0:intime[now] = timetime += 1check[now] = Trueque.append((now,1))for i in g[now]:if not check[i]:que.append((i,0))else:outtime[now] = timetime += 1n = n * 2 + 1bitree = [0 for i in range(n+1)]def btadd(ind,x):global bitreewhile ind <= n:bitree[ind] = bitree[ind] ^ xind += ind & (-ind)def btsum(ind):val = 0while ind > 0:val = val ^ bitree[ind]ind -= ind & (-ind)return valfor i in range(len(c)):btadd(outtime[i+1],c[i])for i in range(q):t, x, y = indata[offset + 3*i],indata[offset + 3*i+1],indata[offset + 3*i+2]if t == 1:btadd(outtime[x],y)else:ans = btsum(outtime[x]) ^ btsum(intime[x])print("{}".format(ans))