結果
問題 | No.1641 Tree Xor Query |
ユーザー |
![]() |
提出日時 | 2021-08-19 17:42:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 291 ms / 5,000 ms |
コード長 | 5,450 bytes |
コンパイル時間 | 862 ms |
コンパイル使用メモリ | 82,216 KB |
実行使用メモリ | 116,680 KB |
最終ジャッジ日時 | 2024-10-12 18:32:24 |
合計ジャッジ時間 | 4,408 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
class HLD:def __init__(self, g):self.g = gself.n = len(g)self.parent = [-1]*self.nself.size = [1]*self.nself.head = [0]*self.nself.preorder = [0]*self.nself.k = 0self.depth = [0]*self.nfor v in range(self.n):if self.parent[v] == -1:self.dfs_pre(v)self.dfs_hld(v)def dfs_pre(self, v):g = self.gstack = [v]order = [v]while stack:v = stack.pop()for u in g[v]:if self.parent[v] == u:continueself.parent[u] = vself.depth[u] = self.depth[v]+1stack.append(u)order.append(u)# 隣接リストの左端: heavyな頂点への辺# 隣接リストの右端: 親への辺while order:v = order.pop()child_v = g[v]if len(child_v) and child_v[0] == self.parent[v]:child_v[0], child_v[-1] = child_v[-1], child_v[0]for i, u in enumerate(child_v):if u == self.parent[v]:continueself.size[v] += self.size[u]if self.size[u] > self.size[child_v[0]]:child_v[i], child_v[0] = child_v[0], child_v[i]def dfs_hld(self, v):stack = [v]while stack:v = stack.pop()self.preorder[v] = self.kself.k += 1top = self.g[v][0]# 隣接リストを逆順に見ていく(親 > lightな頂点への辺 > heavyな頂点 (top))# 連結成分が連続するようにならべるfor u in reversed(self.g[v]):if u == self.parent[v]:continueif u == top:self.head[u] = self.head[v]else:self.head[u] = ustack.append(u)def for_each(self, u, v):# [u, v]上の頂点集合の区間を列挙while True:if self.preorder[u] > self.preorder[v]:u, v = v, ul = max(self.preorder[self.head[v]], self.preorder[u])r = self.preorder[v]yield l, r # [l, r]if self.head[u] != self.head[v]:v = self.parent[self.head[v]]else:returndef for_each_edge(self, u, v):# [u, v]上の辺集合の区間列挙# 辺の情報は子の頂点にwhile True:if self.preorder[u] > self.preorder[v]:u, v = v, uif self.head[u] != self.head[v]:yield self.preorder[self.head[v]], self.preorder[v]v = self.parent[self.head[v]]else:if u != v:yield self.preorder[u]+1, self.preorder[v]breakdef subtree(self, v):# 頂点vの部分木の頂点集合の区間 [l, r)l = self.preorder[v]r = self.preorder[v]+self.size[v]return l, rdef lca(self, u, v):# 頂点u, vのLCAwhile True:if self.preorder[u] > self.preorder[v]:u, v = v, uif self.head[u] == self.head[v]:return uv = self.parent[self.head[v]]class SegTree:def __init__(self, init_val, ide_ele, segfunc):self.n = len(init_val)self.num = 2**(self.n-1).bit_length()self.ide_ele = ide_eleself.segfunc = segfuncself.seg = [ide_ele]*2*self.num# set_valfor i in range(self.n):self.seg[i+self.num] = init_val[i]# builtfor i in range(self.num-1, 0, -1):self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])def update(self, k, x):k += self.numself.seg[k] = xwhile k:k = k >> 1self.seg[k] = self.segfunc(self.seg[2*k], self.seg[2*k+1])def query(self, l, r):if r <= l:return self.ide_elel += self.numr += self.numlres = self.ide_elerres = self.ide_elewhile l < r:if r & 1:r -= 1rres = self.segfunc(self.seg[r], rres)if l & 1:lres = self.segfunc(lres, self.seg[l])l += 1l = l >> 1r = r >> 1res = self.segfunc(lres, rres)return resdef __str__(self): # for debugarr = [self.query(i,i+1) for i in range(self.n)]return str(arr)def segfunc(x, y):return x^yimport sysimport io, osinput = io.BytesIO(os.read(0,os.fstat(0).st_size)).readlinen, q = map(int, input().split())C = list(map(int, input().split()))edge = [[] for i in range(n)]for i in range(n-1):a, b = map(int, input().split())a, b = a-1, b-1edge[a].append(b)edge[b].append(a)hld = HLD(edge)toid = {}for v, i in enumerate(hld.preorder):toid[v] = iA = [0]*nfor v, c in enumerate(C):i = toid[v]A[i] = cseg = SegTree(A, 0, segfunc)for i in range(q):t, x, y = map(int, input().split())x -= 1if t == 1:x = toid[x]s = seg.query(x, x+1)seg.update(x, s^y)else:l, r = hld.subtree(x)print(seg.query(l, r))