Count Valid Paths in a Tree

This approach iterates through every possible starting node in the tree. For each starting node, it performs a traversal (like Depth-First Search or Breadth-First Search) to find all possible paths originating from it. During the traversal, it keeps track of the number of prime nodes encountered on the current path. If a path to a destination node contains exactly one prime number, it's counted as a valid path.

1. Create a boolean array isPrime of size n+1 and populate it using the Sieve of Eratosthenes.
2. Build an adjacency list for the tree from the edges array.
3. Initialize a global counter validPaths to 0.
4. Iterate through each node i from 1 to n.
5. For each i, start a DFS traversal dfs(u, parent, primeCount) from u=i, parent=-1, primeCount=0.
6. In the dfs(u, p, pc) function: a. Update the prime count: new_pc = pc + (isPrime[u] ? 1 : 0). b. If new_pc > 1, stop exploring this path and return. c. If new_pc == 1, it means the path from the start node i to u is valid. Increment validPaths. d. For each neighbor v of u (where v != p), recursively call dfs(v, u, new_pc).
7. After the outer loop finishes, return validPaths / 2 to correct for double counting.

First, we need a way to quickly check if a number is prime. We can pre-compute primality for all numbers from 1 to n using the Sieve of Eratosthenes and store the results in a boolean array. Next, we build an adjacency list representation of the tree from the given edges. The main part of the algorithm involves a nested loop. The outer loop iterates through each node i from 1 to n, considering it as a potential starting point of a path. From each starting node i, we initiate a Depth-First Search (DFS). The DFS function, say dfs(u, p, primeCount), will explore the tree, where u is the current node, p is its parent (to avoid going backward), and primeCount is the count of prime numbers on the path from the starting node i to u. Inside the DFS, we first update primeCount based on whether the current node u is prime. If the primeCount for the path from i to u is exactly 1, we've found a valid path (i, u). We've found a valid path (i, u). We increment our total count. The DFS continues recursively to all neighbors of u (except its parent), but only if the primeCount does not exceed 1. If it's already 2 or more, any further extension of the path will also have at least 2 primes, so we can prune this search branch. Since this process counts each path (a, b) twice (once when starting from a and once from b), the final result is the total count divided by 2.

class Solution {
    private List<List<Integer>> adj;
    private boolean[] isPrime;
    private long count = 0;
    private int n;

    public long countPaths(int n, int[][] edges) {
        this.n = n;
        sieve(n);
        adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        for (int i = 1; i <= n; i++) {
            // We only need to start from a prime or a node adjacent to a prime
            // to find all paths, but for simplicity of brute force, we start from all.
            dfs(i, -1, 0);
        }

        return count / 2;
    }

    private void dfs(int u, int p, int primeCount) {
        if (isPrime[u]) {
            primeCount++;
        }

        if (primeCount > 1) {
            return;
        }

        // If start node is not u, and path is valid, count it.
        if (primeCount == 1) {
            count++;
        }

        for (int v : adj.get(u)) {
            if (v != p) {
                dfs(v, u, primeCount);
            }
        }
    }

    private void sieve(int n) {
        isPrime = new boolean[n + 1];
        if (n >= 2) {
            java.util.Arrays.fill(isPrime, true);
        }
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }
}