結果
問題 | No.1790 Subtree Deletion |
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
"""https://yukicoder.me/problems/no/1790"""import sysfrom sys import stdinfrom collections import dequeinf = 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 -= 1R -= 1lis[L].append( (R,A) )lis[R].append( (L,A) )dlis = [inf] * Ndlis[0] = 0q = deque([0])while q:v = q.popleft()for nex,na in lis[v]:if dlis[nex] > dlis[v] + 1:dlis[nex] = dlis[v] + 1p[nex] = (v,na)q.append(nex)dv = [ (dlis[i],i) for i in range(N) ]dv.sort()dv.reverse()nxor = [0] * Nfor nd,nv in dv:np,na = p[nv]if np != None:nxor[np] ^= na ^ nxor[nv]exist = [True] * Nans = []Q = int(stdin.readline())for loop in range(Q):t,x = map(int,stdin.readline().split())x -= 1if t == 2:if exist[x]:ans.append(str(nxor[x]))else:ans.append("0")else:if not exist[x]:continueq = deque([x])while q:v = q.popleft()exist[v] = Falsefor nex,na in lis[v]:if dlis[nex] > dlis[v]:q.append(nex)v = xplxor = nxor[x] ^ p[x][1]while v != None:nxor[v] ^= plxorv = p[v][0]print ("\n".join(ans))