Link : My solution
We want to assign values to node in such a way the product of all nodes is always divisible by the path length, but how we can do it?
Let think in term of prime suppose a path has prime length (lets take 7) now the product of all node is divisible by 7 (prime) , means there is any node which is multiple of 7 .
One can think ( I also think ) we can assign a node 2 and for remaining node all prime number products less than 100 , but it will be wrong as
primes less than 100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
and product of them is so high ( > 2* 1018)
Now the main idea is just reduced to -
we have to divide above array into two parts x and y such that product of x is less than 2* 1018 and product of y is less than 2* 1018
So after lot of efforts -
X = [ 3 , 7 , 13 , 29 , 37 , 43 , 53 , 61 , 71 , 79 , 89 , 97] , product = 1971894656414957547
Y = [2, 5 , 11 ,17 , 19 , 23 ,31 , 41 ,47 ,59 ,67 ,73 ,83 ] , product = 1169214570588269810
Now we do bfs over tree and find level of all node and simple for even level node assign value “X” and for odd level nodes assign value " Y " or vice versa
Link : My solution
Ask queries in comments
Drop a like if u able to understand my approach.