I had this problem in my Google Summer Intern On campus OA which I was not able to solve even till today.

problem description:-

Prime Tree You are given an undirected Tree T consisting of Nodes N rooted at node 1. You have to assign value to each node of the tree such that: - The assigned value must be prime number less than or equal to 100. - The sum of values assigned to any pair of adjacent nodes must not be a prime number.

Give the Number of valid assignments. (MOD the answer with 1e9+7)

My Approach:- - We know that besides 2 all prime Numbers are odd. and sum of 2 odd Numbers is always even, which means that they can not be prime. - If we take Number '2' out of the question than all permutations are valid. - In the case we consider '2', we know that if the other number be 7. then 2 + 7 = 9 which is not a prime. so there are some finite numbers which on adding with 2 gives None prime AND, some other finite numbers (like 3, 2+3 = 5) which give prime.

NOW, my idea is to place 2 at all nodes one by one (something like rerooting) and place its neighbours to be numbers that yield NON-PRIME.

I don't know if it's right or not, also I couldn't Implement it by myself.