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})$$$

I think it could be solved easily using some combinatorics. Let's divide the solution into two parts first, 2 has not been assigned to any node in the tree and second the tree has 2 assigned to some node. For the first part if $$$p$$$ is the number of primes less than 100 then the number of solutions are $$$n!*{{p-1}\choose{n}}$$$.

Second part can be calculated by taking adjacency into account. For each node fix the current node as 2. The neighboring nodes can be assigned all numbers which pairs with 2 and has pair-wise sum as non-prime (let' say $$$m$$$ is the count of all such primes), then $$$\Sigma{{m\choose{adj}} * adj! * {{p - adj - 1}\choose{n - adj - 1}} * (n - adj - 1)!}$$$ for all nodes.

Could you give me some advice on how to get the Google summer intern OA? I haven't got one

I had got the same question ,tried solving it using combinatorics but couldn't solve it.