FastPrep
Problem · Tree

Prime Tree City Labelings

Learn this problem
● HardRipplingOA

Problem statement

Hackerland contains n cities numbered from 1 to n. Its n - 1 roads form a tree, where road i connects edgeFrom[i] and edgeTo[i].

Assign one prime number from 2 through 100, inclusive, to every city. Prime values may be reused. For every road, the sum of the prime values assigned to its two endpoints must not be prime.

Return the number of valid assignments modulo 10^9 + 7.

Function

countPrimeLabelings(n: int, edgeFrom: int[], edgeTo: int[]) → int

Examples

Example 1

n = 2edgeFrom = [1]edgeTo = [2]return = 609

Among all ordered assignments of primes from 2 through 100 to the two cities, 609 have a non-prime endpoint sum.

Example 2

n = 1edgeFrom = []edgeTo = []return = 25

There are 25 primes from 2 through 100, and a one-city tree has no road constraint.

Constraints

  • 1 <= n <= 200000
  • edgeFrom.length = edgeTo.length = n - 1
  • The roads form a tree.

More Rippling problems

drafts saved locally
public int countPrimeLabelings(int n, int[] edgeFrom, int[] edgeTo) {
  // write your code here
}
n2
edgeFrom[1]
edgeTo[2]
expected609
checking account