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.
You can solve it using DP on tree. Let $$$A$$$ be the set of odd primes which on adding $$$2$$$ again give a prime, and let $$$B$$$ be the set of odd primes which on adding $$$2$$$ become non prime. Let their sizes be $$$a$$$ and $$$b$$$ respectively.
Let $$$dp_{i,k} (1\leq i\leq n, 0\leq k\leq 2)$$$ denote the answer for subtree of $$$i$$$ where:
$$$dp_{i,0}$$$ represents when $$$i$$$ th node is $$$2$$$
$$$dp_{i,1}$$$ represents when $$$i$$$ th node belongs to $$$A$$$
$$$dp_{i,2}$$$ represents when $$$i$$$ th node belogns to $$$B$$$
Then, the transitions are simple:
$$$dp_{v,0} = \sum_{u \in child(v)}dp_{u,0}+dp_{u,2}$$$
$$$dp_{v,1} = a\cdot (\sum_{u \in child(v)}dp_{u,1}+dp_{u,2})$$$
$$$dp_{v,2} = b\cdot (\sum_{u \in child(v)}dp_{u,0}+dp_{u,1}+dp_{u,2})$$$
thanks for the quick reply, this seems correct