Problem statement: CF global-E
Logic: I used a deg array to store the degree of all nodes. I traversed this array later to find the number of real leaves and stored these leaves in ll and marked their degree as -1(to avoid repetition). Then I popped the leaves from ll and if there is an unvisited node connected to the leaf ( currently popped from ll) are counted as buds, marked visited (we make their degree -2) and appended to bl. After all elements of ll has been popped, we go to bl start popping its elements and decrease of all unvisited node connected to it by 1. At some point, if we find any unvisited node (whose degree has been decreased currently) having degree 1 then we consider it as a leaf, mark it visited and put it inside ll.
Our final answer is:- l-b (if no. of leaves connected to root is not 0)
l-b+1 (if no. of leaves connected to root is 0)
My code is not working for large inputs, so I can’t make sure what mistake I made.
So, please help me to find my mistake’
for _ in range(t):
g=[ for i in range(n+1)] deg=*(n+1) # deg: contains degree of each node for i in range(n-1): u,v=map(int,input().split()) g[u].append(v) g[v].append(u) deg[u]+=1 deg[v]+=1 bl= # used as stack to store BUDS ll= # used as stack to store LEAVES deg=0 # to avoid root node being considered as bud or leaf l=0 # number of leaves found b=0 # # number of buds found for i in range(2,n+1): # Loop to find all the true leaves if (deg[i]==1): ll.append(i) ll+=1 deg[i]=-1 # Already visited Leaves are avoided by putting their deg as -1 l+=1 while (ll+bl)>0: while (ll>0): j=ll.pop() ll-=1 for i in g[j]: if deg[i]>0: # All nodes connected to a leaf (except the root) are buds deg[i]=-2 # Already visited Buds are avoided by putting their deg as -2 b+=1 bl.append(i) bl+=1 while (bl>0): j=bl.pop() bl-=1 for i in g[j]: if deg[i]>0: deg[i]-=1 # we simulate removal of a bud by decreasind deg. of all unvisited nodes connected to the bud if deg[i]==1: #after removal of bud if any unvisited node has deg.=1 then it is leaf deg[i]=-1 l+=1 ll+=1 ll.append(i) x=0 # stores no. of leaves connected to the Root for i in g: # loop to find number of leaves connected to the root if deg[i]==-1: x+=1 if x==0: print(l-b+1) else: print(l-b)