結果

問題 No.1641 Tree Xor Query
ユーザー Navier_BoltzmannNavier_Boltzmann
提出日時 2022-10-10 12:14:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 414 ms / 5,000 ms
コード長 5,325 bytes
コンパイル時間 259 ms
コンパイル使用メモリ 87,248 KB
実行使用メモリ 113,816 KB
最終ジャッジ日時 2023-09-06 12:53:32
合計ジャッジ時間 5,896 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 105 ms
72,588 KB
testcase_01 AC 104 ms
72,708 KB
testcase_02 AC 108 ms
72,620 KB
testcase_03 AC 104 ms
72,600 KB
testcase_04 AC 106 ms
72,700 KB
testcase_05 AC 107 ms
72,360 KB
testcase_06 AC 106 ms
72,696 KB
testcase_07 AC 105 ms
72,720 KB
testcase_08 AC 104 ms
72,584 KB
testcase_09 AC 104 ms
72,784 KB
testcase_10 AC 105 ms
72,520 KB
testcase_11 AC 105 ms
72,448 KB
testcase_12 AC 105 ms
72,592 KB
testcase_13 AC 414 ms
106,644 KB
testcase_14 AC 406 ms
106,900 KB
testcase_15 AC 177 ms
80,308 KB
testcase_16 AC 246 ms
83,352 KB
testcase_17 AC 229 ms
81,668 KB
testcase_18 AC 188 ms
81,352 KB
testcase_19 AC 191 ms
79,920 KB
testcase_20 AC 399 ms
113,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
from collections import *
from itertools import *
from functools import *
import math,sys
input = sys.stdin.readline

class HL_Decomposition():
    
    
    ### HL分解をしてIDを振りなおしたものに対して、パスに含まれる区間を返す
    ### SegTreeにのせる配列はIDを並び替えたもの
    
    
    def __init__(self,e,root=0):
        
        
        self.N = len(e)
        self.e = e
        par = [-1]*N
        sub = [-1]*N
        self.root = root
        dist = [-1]*N
        v = deque()
        dist[root]=0
        v.append(root)
        while v:
            x = v.popleft()
            for ix in e[x]:
                if dist[ix] !=-1:
                    continue
                dist[ix] = dist[x] + 1
                v.append(ix)
        
        H = [(-dist[i],i) for i in range(N)]
        H.sort()
        for h,i in H:
            tmp = 1
            for ix in e[i]:
                if sub[ix] == -1:
                    par[i]= ix
                else:
                    tmp += sub[ix]
            sub[i] = tmp
        
        
        self.ID = [-1]*N
        self.ID[self.root]=0
        self.HEAD = [-1]*N
        head = [-1]*N
        self.PAR = [-1]*N
        visited = [False]*N
        self.HEAD[0]=0
        head[self.root]=0
        depth = [-1]*N
        depth[self.root]=0
        self.DEPTH = [-1]*N
        self.DEPTH[0]=0
        cnt = 0
        v = deque([self.root])
        self.SUB = [0]*N
        self.SUB[0] = N
        while v:
            x = v.popleft()
            visited[x]=True
            self.ID[x]=cnt
            cnt += 1
            n = len(self.e[x])
            tmp = [(sub[ix],ix) for ix in self.e[x]]
            tmp.sort()
            flg = 0
            if x==self.root:
                flg -= 1
            for _,ix in tmp:
                flg += 1
                if visited[ix]:
                    continue
                v.appendleft(ix)
                if flg==n-1:
                    head[ix] = head[x]
                    depth[ix] = depth[x]
                else:
                    head[ix] = ix
                    depth[ix] = depth[x]+1
        
        for i in range(self.N):
            self.PAR[self.ID[i]] = self.ID[par[i]]
            self.HEAD[self.ID[i]] = self.ID[head[i]]
            self.DEPTH[self.ID[i]] = depth[i]
            self.SUB[self.ID[i]] = sub[i]
        
    def path_query(self,l,r):
        L = self.ID[l]
        R = self.ID[r]
        res = []
        if self.DEPTH[L]<self.DEPTH[R]:
            L,R = R,L
        
        while self.DEPTH[L] != self.DEPTH[R]:
            tmp = (self.HEAD[L],L+1)
            res.append(tmp)
            L = self.PAR[self.HEAD[L]]
        
        while self.HEAD[L] != self.HEAD[R]:
            tmp = (self.HEAD[L],L+1)
            res.append(tmp)
            L = self.PAR[self.HEAD[L]]            
            tmp = (self.HEAD[R],R+1)
            res.append(tmp)
            R = self.PAR[self.HEAD[R]]        
        
        if L>R:
            L,R = R,L
            
        tmp = (L,R+1)
        res.append(tmp)
        
        return res
        
    def sub_query(self,k):
        
        K = self.ID[k]
        
        return (K,K+self.SUB[K])
class SegTree:
    """
    Segment Tree
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        初期化

        init_val: 配列の初期値
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新

        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る

        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

N,Q = map(int,input().split())
C = list(map(int,input().split()))
e = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)

hld = HL_Decomposition(e)
ID = hld.ID
A = [0]*N
for i in range(N):
    A[ID[i]] = C[i]

T = SegTree(A,lambda x,y:x^y,0)
for _ in range(Q):
    query = list(map(int,input().split()))
    if query[0]==1:
        x,y = query[1:]
        x -= 1
        x = ID[x]
        T.update(x,T.query(x,x+1)^y)
    else:
        x = query[1]
        x -= 1
        l,r = hld.sub_query(x)
        print(T.query(l,r))
0