結果
問題 | No.1928 Make a Binary Tree |
ユーザー |
![]() |
提出日時 | 2021-12-09 10:27:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,747 ms / 3,000 ms |
コード長 | 3,110 bytes |
コンパイル時間 | 359 ms |
コンパイル使用メモリ | 82,436 KB |
実行使用メモリ | 143,412 KB |
最終ジャッジ日時 | 2024-11-06 04:22:47 |
合計ジャッジ時間 | 55,320 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
class SegTree:def __init__(self,op,e,v):self._op=opself._e=eif isinstance(v,int):v=[e]*vself._n=len(v)self._log=self.ceil2()self._size=1<<self._logself._d=[e]*(2*self._size)for i in range(self._n):self._d[self._size+i]=v[i]for i in range(self._size-1,0,-1):self._update(i)returndef ceil2(self):x=0while (1<<x)<self._n:x+=1return xdef set(self,p,x):p+=self._sizeself._d[p]=xfor i in range(1,self._log+1):self._update(p>>i)returndef get(self,p):return self._d[p+self._size]def prod(self,left,right):sml=self._esmr=self._eleft+=self._sizeright+=self._sizewhile left<right:if left&1:sml=self._op(sml,self._d[left])left+=1if right&1:right-=1smr=self._op(self._d[right],smr)left>>=1right>>=1return self._op(sml,smr)def all_prod(self):return self._d[1]def max_right(self,left,target):self.target=targetif left==self._n:return self._nleft+=self._sizesm=self._efirst=Truewhile first or (left & -left)!=left:first=Falsewhile left%2==0:left>>=1if not self._f(self._op(sm,self._d[left])):while left<self._size:left*=2if self._f(self._op(sm,self._d[left])):sm=self._op(sm,self._d[left])left+=1return left-self._sizesm=self._op(sm,self._d[left])left+=1return self._ndef min_left(self,right,target):self.target=targetif right==0:return 0right+=self._sizesm=self._efirst=Truewhile first or (right&-right)!=right:first=Falseright-=1while right>1 and right%2:right>>=1if not self._f(self._op(self._d[right],sm)):while right<self._size:right=2*right+1if self._f(self._op(self._d[right],sm)):sm=self._op(self._d[right],sm)right-=1return right+1-self._sizesm=self._op(self._d[right],sm)return 0def _update(self,k):self._d[k]=self._op(self._d[2*k],self._d[2*k+1])returndef _f(self,u):return u<self.targetfrom collections import dequedef main():N=int(input())Graph=[[]for i in range(N)]for i in range(N-1):x,y=map(int,input().split())Graph[x-1].append(y-1)Graph[y-1].append(x-1)seg=SegTree(max,[-1,-1],N)que=deque()que.append(N)que.append(0)checked=[False]*Npre=[0]*Ncnt=[1]*Nsearched=0while que:q=que.pop()if q<N:pre[q]=searchedchecked[q]=Truefor to in Graph[q]:if not checked[to]:que.append(to+N)que.append(to)else:for j in range(2):tmp=seg.prod(pre[q-N],searched)if tmp[0]==-1:breakcnt[q-N]+=tmp[0]seg.set(tmp[1],[-1,-1])seg.set(searched,[cnt[q-N],searched])searched+=1print(cnt[0])returnmain()