結果
問題 | No.899 γatheree |
ユーザー | ああいい |
提出日時 | 2022-03-04 18:09:48 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,951 bytes |
コンパイル時間 | 316 ms |
コンパイル使用メモリ | 86,780 KB |
実行使用メモリ | 110,212 KB |
最終ジャッジ日時 | 2023-09-25 19:14:54 |
合計ジャッジ時間 | 40,159 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 92 ms
72,392 KB |
testcase_01 | AC | 123 ms
77,252 KB |
testcase_02 | AC | 133 ms
77,444 KB |
testcase_03 | AC | 126 ms
77,124 KB |
testcase_04 | AC | 124 ms
77,268 KB |
testcase_05 | AC | 128 ms
77,288 KB |
testcase_06 | AC | 1,907 ms
106,708 KB |
testcase_07 | AC | 1,989 ms
109,444 KB |
testcase_08 | AC | 1,936 ms
110,212 KB |
testcase_09 | AC | 1,948 ms
108,296 KB |
testcase_10 | AC | 1,987 ms
105,804 KB |
testcase_11 | AC | 1,950 ms
107,588 KB |
testcase_12 | TLE | - |
testcase_13 | AC | 1,942 ms
107,880 KB |
testcase_14 | AC | 1,860 ms
106,672 KB |
testcase_15 | AC | 1,964 ms
109,000 KB |
testcase_16 | AC | 1,908 ms
106,544 KB |
testcase_17 | AC | 1,850 ms
106,640 KB |
testcase_18 | AC | 1,918 ms
107,096 KB |
testcase_19 | TLE | - |
testcase_20 | AC | 1,970 ms
108,292 KB |
testcase_21 | AC | 1,795 ms
108,372 KB |
testcase_22 | AC | 1,793 ms
108,264 KB |
testcase_23 | AC | 1,866 ms
108,852 KB |
ソースコード
#頂点は1-index,下段は0-index class LazySegTree: #単位元と結合と作用をここで定義 Xunit = 0 Aunit = -1 def Xf(self,x,y): return x + y #Xf = max def Af(self,a,b): if b == self.Aunit: return a return b #AのXへの作用 def operate(self,x,a): if a == self.Aunit: return x return a def __init__(self,N): self.N = N self.X = [self.Xunit] * (N + N) self.A = [self.Aunit] * (N + N) def build(self,seq): for i,x in enumerate(seq,self.N): self.X[i] = x for i in range(self.N-1,0,-1): self.X[i] = self.Xf(self.X[i<<1],self.X[i<<1 | 1]) def eval_at(self,i): return self.operate(self.X[i],self.A[i]) def propagate_at(self,i): self.X[i] = self.eval_at(i) self.A[i<<1] = self.Af(self.A[i<<1],self.A[i]) self.A[i<<1 | 1] = self.Af(self.A[i<<1 | 1],self.A[i]) self.A[i] = self.Aunit def propagate_above(self,i): H = i.bit_length() - 1 for h in range(H,0,-1): self.propagate_at(i >> h) def recalc_above(self,i): while i > 1: i >>= 1 self.X[i] = self.Xf(self.eval_at(i << 1),self.eval_at(i << 1 | 1)) def update(self,i,x): i += self.N self.propagate_above(i) self.X[i] = x self.A[i] = self.Aunit self.recalc_above(i) def fold(self,L = 0,R = -1): if R == -1:R = self.N L += self.N R += self.N self.propagate_above(L // (L & -L)) self.propagate_above(R // (R & -R) -1) vL = self.Xunit vR = self.Xunit while L < R: if L & 1: vL = self.Xf(vL,self.eval_at(L)) L += 1 if R & 1: R -= 1 vR = self.Xf(self.eval_at(R),vR) L >>= 1 R >>= 1 return self.Xf(vL,vR) def operate_range(self,L,R,x): #区間全体に作用させる L += self.N R += self.N L0 = L // (L & -L) R0 = R // (R & -R) - 1 self.propagate_above(L0) self.propagate_above(R0) while L < R: if L & 1: self.A[L] = self.Af(self.A[L],x) L += 1 if R & 1: R -= 1 self.A[R] = self.Af(self.A[R],x) L >>= 1 R >>= 1 self.recalc_above(L0) self.recalc_above(R0) def write(self): print(self.X) def change(self,Xf,Xunit,Af,Aunit,operate): self.Xf = Xf self.Xunit = Xunit self.Af = Af self.Aunit = Aunit self.operate = operate N = int(input()) G = [[] for _ in range(N)] for _ in range(N-1): u,v = map(int,input().split()) G[u].append(v) G[v].append(u) A = list(map(int,input().split())) from collections import deque parent = [-1] * N pos = [-1] * N q = deque() q.append((0,-1)) l1 = [-1] * N r1 = [-2] * N l2 = [-1] * N r2 = [-2] * N count = 0 while q: now,p = q.popleft() if now >= 0: pos[now] = count count += 1 for v in G[now]: if v == p:continue parent[v] = now q.append((v,now)) q.append((0,-1)) while q: now,p = q.popleft() for v in G[now]: if v == p:continue q.append((v,now)) if True: for v in G[now]: if v == p:continue l1[now] = pos[v] break for v in reversed(G[now]): if v == p:continue r1[now] = pos[v] break for v in G[now]: if v == p:continue if l2[now] >= 0:break for u in G[v]: if u == now:continue l2[now] = pos[u] break for v in reversed(G[now]): if v == p:continue if r2[now] >= 0:break for u in reversed(G[v]): if u == now:continue r2[now] = pos[u] break seg = LazySegTree(N) seq = [0] * N for i in range(N): seq[pos[i]] = A[i] seg.build(seq) Q = int(input()) for _ in range(Q): x = int(input()) ans = 0 p = parent[x] if p >= 0: ans += seg.fold(pos[p],pos[p]+1) seg.operate_range(pos[p],pos[p]+1,0) ans += seg.fold(l1[p],r1[p]+1) seg.operate_range(l1[p],r1[p]+1,0) if parent[p] >= 0: pp = parent[p] ans += seg.fold(pos[pp],pos[pp]+1) seg.operate_range(pos[pp],pos[pp]+1,0) else: ans += seg.fold(pos[x],pos[x] +1) seg.operate_range(pos[x],pos[x]+1,0) if l1[x] >= 0: ans += seg.fold(l1[x],r1[x] + 1) seg.operate_range(l1[x],r1[x]+1,0) if l2[x] >= 0: ans += seg.fold(l2[x],r2[x]+1) seg.operate_range(l2[x],r2[x]+1,0) print(ans) seg.update(pos[x],ans)