This indeed works, the maximum sequence of nodes that is not divisible by p would be p-2 which satisfies the conditions. I am curious if the setter (@sjshohag ) was not aware of this solution, as it would imply that N could be increased to around 10^7.
How to choose p1 and p2 anyone? I tried adding alternate primes in each set but it exceeds 2e18
@rajarshi_basu This should be explained in the editorial. Both the setter and tester use a “greedy” approach that might not be entirely obvious
3 Likes
can you please explain your logic…on what basis you are assigning the values
Thanks in advance…
How did you make these products? What are the primes of p1? Thanks in advance.
This is how rds_98’s solution works
We assign each node a value based on it’s distance from a root node.
Because of this case we need to make sure that roughly every p/2 levels of depth will have a value divisble by p (where p prime). The formula (2d)(2d+1) will satisfy this condition.
Suppose p divides 2d(2d+1). Then p divides 2d or p divides 2d+1. This can be rewritten as np = 2d or np=2d+1. With some rewriting we then get d=n\frac p2 or d=n\frac p2 -\frac12. From this we can see that every p/2 depths will be divisble by p.
In particular the maximum depth difference between nodes that are divisible by p will be \frac {p+1}2 which ensures that the maximum path of nodes not divisible by p will be p-2
2 Likes
I specifically left that part out for readers to think on it. It’s not hard at all to figure out a way (or even hardcode it), but will maybe make newbies think a bit. IMO good editorials should keep some parts of the problem for the reader to put a bit of thought into.
2 Likes
@rajarshi_basu please explain me that the two values p1=1816798556036292277
p2=1269027849171992910 which we get after some precomputation, the product of these two numbers is not divisible by 4,8,16,64,9,27,81,25,49 so how the solution is valid if |S| takes these values. It would be very helpful if you can please explain it to me! 
I had the same thing in mind. So I used another approach . I thought of assigning every value x to every x-th node. So for eg. Every 3rd node will have a value of
node_val *=3. So now if we consider any simple path of length 3 , we have the product to be divisible by 3.But I am still getting a WA. Can someone tell me what is wrong in my logic .
Link.
Yeah 
Nope u did wrong man , if u wanna divide it by 4 what it means , it means there is a path whose length is 4 right?
consider this graph-
1
/ | \
2 3 4
\
5
now assign values to nodes for even level assign P1 and for odd level assign p2
consider path from 2 to 5 ie . 2 -> 1- > 4 - > 5 (length is 4 ) u can check now product of all nodes is divisible by 4 .
Hope u understand.
and what if path length is 37 ?
So one of every 37 nodes will have a value that will be a multiple of 37.
Input
2
6
1 2
2 3
1 4
5 1
6 5
2
1 2
Output
1 2 3 24 30 6
1 2
As u can see one of every 5th node has a multiple of 5, One of every 6th node has a multiple of 6 and so on!!
isn’t it will overflow ?
lets take a graph like this
1-2-3-4-5-6-7-8-9-------97 ?
now what’s your answer ?
how did you divided prime numbers to get these two p1 and p2?
thanks
I did the same and got AC. Was this approach not intended to get accepted?
[My submission] (CodeChef: Practical coding for everyone)
Going backwards works. Iterate from 100 to 1, and each time multiply the prime to the smaller value of p1 and p2.
2 Likes
@abc1233 CodeChef: Practical coding for everyone
Can u pls check this soln, I’ve used dfs instead but getting WA
1 Like