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’
code:-
‘’’
t=int(input())
for _ in range(t):
n=int(input())
g=[[] for i in range(n+1)]
deg=[0]*(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=[0] # used as stack to store BUDS
ll=[0] # used as stack to store LEAVES
deg[1]=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[0]+=1
deg[i]=-1 # Already visited Leaves are avoided by putting their deg as -1
l+=1
while (ll[0]+bl[0])>0:
while (ll[0]>0):
j=ll.pop()
ll[0]-=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[0]+=1
while (bl[0]>0):
j=bl.pop()
bl[0]-=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[0]+=1
ll.append(i)
x=0 # stores no. of leaves connected to the Root
for i in g[1]: # 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)
‘’’