We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#!/bin/python3importmathimportosimportrandomimportreimportsysfromfractionsimportFraction## Complete the 'storyOfATree' function below.## The function is expected to return a STRING.# The function accepts following parameters:# 1. INTEGER n# 2. 2D_INTEGER_ARRAY edges# 3. INTEGER k# 4. 2D_INTEGER_ARRAY guesses#defstoryOfATree(n,edges,k,guesses):#Write your code hereadj=[[]for_inrange(n)]foru,vinedges:u,v=u-1,v-1adj[u].append(v)adj[v].append(u)guess=set((u-1,v-1)foru,vinguesses)base=0np=[0]*nvisit=[False]*ndefrec(node,point):nonlocalbasevisit[node]=Truenp[node]=pointforainadj[node]:ifvisit[a]:continuepositive=(node,a)inguessnegative=(a,node)inguessifpositiveandnegative:base+=1rec(a,point)elifpositive:base+=1rec(a,point-1)elifnegative:rec(a,point+1)else:rec(a,point)rec(0,0)count=0forpinnp:ifp+base>=k:count+=1ifcount==0:return"0/1"elifcount==n:return"1/1"else:returnstr(Fraction(count,n))if__name__=='__main__':fptr=open(os.environ['OUTPUT_PATH'],'w')q=int(input().strip())for_inrange(q):n=int(input().strip())edges=[list(map(int,input().rstrip().split()))for_inrange(n-1)]g,k=map(int,input().rstrip().split())guesses=[list(map(int,input().rstrip().split()))for_inrange(g)]result=storyOfATree(n,edges,k,guesses)fptr.write(result+'\n')fptr.close()
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
The Story of a Tree
You are viewing a single comment's thread. Return to all comments →
Python 3 solution: