結果

問題 No.1641 Tree Xor Query
ユーザー titiatitia
提出日時 2021-08-06 22:41:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 298 ms / 5,000 ms
コード長 3,867 bytes
コンパイル時間 243 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 123,572 KB
最終ジャッジ日時 2024-09-17 02:53:52
合計ジャッジ時間 3,303 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

E=[[] for i in range(N+1)]

for i in range(N-1):
    a,b=map(int,input().split())
    #a-=1
    #b-=1
    E[a].append(b)
    E[b].append(a)

# 木のHL分解+LCA

N+=1 # ROOTの親の点を一つ余計に見るため、総ノード数を一つ増やしておく

ROOT=1

QUE=[ROOT] 
Parent=[-1]*(N+1)
Parent[ROOT]=N # ROOTの親を定めておく.
TOP_SORT=[] # トポロジカルソート

while QUE: # トポロジカルソートと同時に親を見つける
    x=QUE.pop()
    TOP_SORT.append(x)
    for to in E[x]:
        if Parent[to]==-1:
            Parent[to]=x
            QUE.append(to)

Children=[1]*(N+1)

for x in TOP_SORT[::-1]: #（自分を含む）子ノードの数を調べる
    Children[Parent[x]]+=Children[x]

USE=[0]*N
Group=[i for i in range(N+1)]

for x in TOP_SORT: # HL分解によるグループ分け
    USE[x]=1
    MAX_children=0
    select_node=0

    for to in E[x]:
        if USE[to]==0 and Children[to]>MAX_children:
            select_node=to
            MAX_children=Children[to]

    for to in E[x]:
        if USE[to]==0 and to==select_node:
            Group[to]=Group[x]

def LCA(a,b): # HL分解を利用してLCAを求める
    while Group[a]!=Group[b]:
        if Children[Parent[Group[a]]]<Children[Parent[Group[b]]]:
            a=Parent[Group[a]]
        else:
            b=Parent[Group[b]]

    if Children[a]>Children[b]:
        return a
    else:
        return b

# 以下、セグ木に乗せる場合

def PATH(a,b): # HL分解を利用してa,b間のpathを出力する. LCAとやることは同じ. log個の閉区間に分割する.
    while Group[a]!=Group[b]:
        if Children[Parent[Group[a]]]<Children[Parent[Group[b]]]:
            yield (a,Group[a])
            a=Parent[Group[a]]
        else:
            yield (b,Group[b])
            b=Parent[Group[b]]

    if Children[a]>Children[b]:
        yield (b,a)
    else:
        yield (a,b)

END_node=[-1]*(N+1) # HL分解したときの終点ノード
select_child=[[] for i in range(N+1)] # 子グループの代表ノード

for x in TOP_SORT:
    END_node[Group[x]]=x
    if Group[Parent[x]]!=Group[x]:
        select_child[Group[Parent[x]]].append(x)

def children_PATH(x): # HL分解を利用してx以下のchildren全てをpathとして出力する.
    Q=[x]
    while Q:
        x=Q.pop()
        yield (END_node[Group[x]],x)

        for to in select_child[Group[x]]:
            if Children[Parent[to]]<=Children[x]:
                Q.append(to)
    
SEG_to_NODE=sorted(list(range(N)),key=lambda x:((Group[x]+1)<<30)+Children[x]) # Segment treeに載せるため, Groupごとに並べる.子ノードが少ないものが先に来るようにしている.
NODE_to_SEG=[-1]*N #その逆関数. NODE_to_SEG[ind]をセグ木に乗せる.
for ind,x in enumerate(SEG_to_NODE):
    NODE_to_SEG[x]=ind

seg_el=1<<((N+1).bit_length()) # Segment treeの台の要素数
SEG=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def getvalue(n,seg_el): # 一点の値を取得
    i=n+seg_el
    ANS=0
    
    ANS^=SEG[i]
    i>>=1# 子ノードへ
    
    while i!=0:
        ANS^=SEG[i]
        i>>=1

    return ANS

def updates(l,r,x):
    L=l+seg_el
    R=r+seg_el

    while L<R:
        if L & 1:
            SEG[L]^=x
            L+=1

        if R & 1:
            R-=1
            SEG[R]^=x
        L>>=1
        R>>=1

for x in TOP_SORT[::-1][:-1]:
    C[Parent[x]]^=C[x]

for i in range(1,N):
    updates(NODE_to_SEG[i],NODE_to_SEG[i]+1,C[i])

for queries in range(Q):
    c,x,y=map(int,input().split())
    if c==2:
        print(getvalue(NODE_to_SEG[x],seg_el))
    else:
        for l,r in PATH(x,1):
            updates(NODE_to_SEG[l],NODE_to_SEG[r]+1,y)
0