Advertisement
Iam_Sandeep

Untitled

Aug 8th, 2022
675
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.36 KB | None | 0 0
  1. class TreeAncestor:
  2.  
  3.     def __init__(self, n: int, p: List[int]):
  4.         adj=self.adj=defaultdict(set)
  5.         for i in range(n):
  6.             adj[i].add(p[i])
  7.             adj[p[i]].add(i)
  8.        
  9.        
  10.         self.d=d={}
  11.         d[1]=p[:]#storing height and parents respectively
  12.        
  13.         def height(u):
  14.             q=deque()
  15.             q.append(u)
  16.             vis={u}
  17.             ans=0
  18.             while q:
  19.                 for _ in range(len(q)):
  20.                     ans+=1
  21.                     t=q.popleft()
  22.                     for v in adj[u]:
  23.                         if v not in vis:
  24.                             vis.add(v)
  25.                             q.append(v)
  26.             return ans
  27.        
  28.         self.ht=ht=height(0)
  29.         s=2
  30.         while s<=ht:
  31.             d[s]=[None]*n
  32.             for i in range(n):
  33.                 first=d[s>>1][i]
  34.                 if first<0:
  35.                     d[s][i]=-1
  36.                 else:
  37.                     d[s][i]=d[s>>1][first]
  38.             s=s<<1
  39.        
  40.  
  41.        
  42.         print(d)
  43.        
  44.  
  45.     def getKthAncestor(self, node: int, k: int) -> int:
  46.         d=self.d
  47.         bins=bin(k)[2:][::-1]
  48.         if k>self.ht:return -1
  49.        
  50.         for i,j in enumerate(bins):
  51.             if j=='1':
  52.                 node=d[1<<i][node]
  53.        
  54.        
  55.         return node
  56.        
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement