結果

問題 No.1790 Subtree Deletion
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2021-12-24 16:50:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 682 ms / 3,000 ms
コード長 1,430 bytes
コンパイル時間 136 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 114,092 KB
最終ジャッジ日時 2024-09-19 15:30:43
合計ジャッジ時間 8,414 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

"""
https://yukicoder.me/problems/no/1790
"""
import sys
from sys import stdin
from collections import deque
inf = float("inf")
N = int(stdin.readline())
lis = [ [] for i in range(N) ]
p = [ (None,None) for i in range(N) ]
for i in range(N-1):
L,R,A = map(int,stdin.readline().split())
L -= 1
R -= 1
lis[L].append( (R,A) )
lis[R].append( (L,A) )
dlis = [inf] * N
dlis[0] = 0
q = deque([0])
while q:
v = q.popleft()
for nex,na in lis[v]:
if dlis[nex] > dlis[v] + 1:
dlis[nex] = dlis[v] + 1
p[nex] = (v,na)
q.append(nex)
dv = [ (dlis[i],i) for i in range(N) ]
dv.sort()
dv.reverse()
nxor = [0] * N
for nd,nv in dv:
np,na = p[nv]
if np != None:
nxor[np] ^= na ^ nxor[nv]
exist = [True] * N
ans = []
Q = int(stdin.readline())
for loop in range(Q):
t,x = map(int,stdin.readline().split())
x -= 1
if t == 2:
if exist[x]:
ans.append(str(nxor[x]))
else:
ans.append("0")
else:
if not exist[x]:
continue
q = deque([x])
while q:
v = q.popleft()
exist[v] = False
for nex,na in lis[v]:
if dlis[nex] > dlis[v]:
q.append(nex)
v = x
plxor = nxor[x] ^ p[x][1]
while v != None:
nxor[v] ^= plxor
v = p[v][0]
print ("\n".join(ans))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0