# Count Number of Possible Root Nodes
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-number-of-possible-root-nodes)
Canonical: https://scaleengineer.com/dsa/problems/count-number-of-possible-root-nodes
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Hash Table, Tree
---
## Problem
Alice has an undirected tree with `n` nodes labeled from `0` to `n - 1`. The tree is represented as a 2D integer array `edges` of length `n - 1` where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the tree.

Alice wants Bob to find the root of the tree. She allows Bob to make several **guesses** about her tree. In one guess, he does the following:

* Chooses two **distinct** integers `u` and `v` such that there exists an edge `[u, v]` in the tree.
* He tells Alice that `u` is the **parent** of `v` in the tree.

Bob's guesses are represented by a 2D integer array `guesses` where `guesses[j] = [uj, vj]` indicates Bob guessed `uj` to be the parent of `vj`.

Alice being lazy, does not reply to each of Bob's guesses, but just says that **at least** `k` of his guesses are `true`.

Given the 2D integer arrays `edges`, `guesses` and the integer `k`, return _the **number of possible nodes** that can be the root of Alice's tree_. If there is no such tree, return `0`.

**Example 1:**

![](https://assets.glich.co/dsa/count-number-of-possible-root-nodes/image0.png)

**Input:** edges = [[0,1],[1,2],[1,3],[4,2]], guesses = [[1,3],[0,1],[1,0],[2,4]], k = 3
**Output:** 3
**Explanation:** 
Root = 0, correct guesses = [1,3], [0,1], [2,4]
Root = 1, correct guesses = [1,3], [1,0], [2,4]
Root = 2, correct guesses = [1,3], [1,0], [2,4]
Root = 3, correct guesses = [1,0], [2,4]
Root = 4, correct guesses = [1,3], [1,0]
Considering 0, 1, or 2 as root node leads to 3 correct guesses.

**Example 2:**

![](https://assets.glich.co/dsa/count-number-of-possible-root-nodes/image1.png)

**Input:** edges = [[0,1],[1,2],[2,3],[3,4]], guesses = [[1,0],[3,4],[2,1],[3,2]], k = 1
**Output:** 5
**Explanation:** 
Root = 0, correct guesses = [3,4]
Root = 1, correct guesses = [1,0], [3,4]
Root = 2, correct guesses = [1,0], [2,1], [3,4]
Root = 3, correct guesses = [1,0], [2,1], [3,2], [3,4]
Root = 4, correct guesses = [1,0], [2,1], [3,2]
Considering any node as root will give at least 1 correct guess. 

**Constraints:**

* `edges.length == n - 1`
* `2 <= n <= 105`
* `1 <= guesses.length <= 105`
* `0 <= ai, bi, uj, vj <= n - 1`
* `ai != bi`
* `uj != vj`
* `edges` represents a valid tree.
* `guesses[j]` is an edge of the tree.
* `guesses` is unique.
* `0 <= k <= guesses.length`

# Approaches
## Brute Force: Iterate Through All Possible Roots
The most direct way to solve this problem is to test every single node as a potential root. For each node, we can determine the structure of the tree if it were the root, count how many guesses are correct for that structure, and if the count meets the threshold `k`, we increment our result.
**Time:** O(N^2 + M), where N is the number of nodes and M is the number of guesses. Building the adjacency list takes O(N). Storing guesses in a set takes O(M). The main loop runs N times. Inside the loop, a full tree traversal (BFS/DFS) takes O(N) time. So the loop takes O(N*N). The total complexity is O(N^2 + M). This is too slow for the given constraints. · **Space:** O(N + M). O(N) for the adjacency list and the visited array. O(M) for the `guessSet`. The queue for BFS would take O(N) in the worst case.
**Pros:** Simple to understand and implement.
**Cons:** Inefficient and will time out on larger test cases due to its quadratic time complexity.
### Explanation
We can iterate through each node from `0` to `n-1`. Let's say we are currently checking if node `r` can be a valid root.\n\nTo find out the parent-child relationships for a tree rooted at `r`, we can perform a tree traversal like Breadth-First Search (BFS) or Depth-First Search (DFS), starting from `r`. During the traversal, whenever we move from a node `u` to an unvisited neighbor `v`, we establish that `u` is the parent of `v`.\n\nTo efficiently check the guesses, we can first store all the `guesses` in a `HashSet` of pairs. This allows for O(1) lookups. A pair `(u, v)` can be encoded into a single `long` value to be stored in the set.\n\nAs we traverse the tree rooted at `r` and establish a parent-child relationship `u -> v`, we check if the pair `(u, v)` exists in our `guessSet`. If it does, we increment a counter for correct guesses for the root `r`.\n\nAfter the traversal for root `r` is complete, we check if the total count of correct guesses is at least `k`. If it is, we count `r` as a possible root.\n\nWe repeat this process for all `n` nodes and return the total count of possible roots.
```java
import java.util.*;

class Solution {
    public int rootCount(int[][] edges, int[][] guesses, int k) {
        int n = edges.length + 1;
        List<List<Integer>> 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]);
        }

        Set<Long> guessSet = new HashSet<>();
        long factor = n;
        for (int[] guess : guesses) {
            guessSet.add((long) guess[0] * factor + guess[1]);
        }

        int possibleRoots = 0;
        for (int i = 0; i < n; i++) {
            // Consider node i as the root
            int correctGuesses = 0;
            
            Queue<Integer> q = new LinkedList<>();
            boolean[] visited = new boolean[n];
            
            q.add(i);
            visited[i] = true;
            
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : adj.get(u)) {
                    if (!visited[v]) {
                        visited[v] = true;
                        q.add(v);
                        // u is parent of v
                        if (guessSet.contains((long) u * factor + v)) {
                            correctGuesses++;
                        }
                    }
                }
            }
            
            if (correctGuesses >= k) {
                possibleRoots++;
            }
        }
        
        return possibleRoots;
    }
}
```
### Algorithm
- Build an adjacency list representation of the undirected tree from the `edges` array.\n- Store the `guesses` in a `HashSet` for quick lookups. Encode each pair `(u, v)` into a single `long`.\n- Initialize a counter for possible roots, `result = 0`.\n- Loop through each node `i` from `0` to `n-1`:\n  - Consider `i` as the current root.\n  - Initialize `current_correct_guesses = 0`.\n  - Perform a traversal (BFS or DFS) starting from `i`. Keep track of visited nodes.\n  - During the traversal, for each edge from a parent `u` to a child `v`, check if the guess `(u, v)` is in the `guessSet`. If yes, increment `current_correct_guesses`.\n  - After the traversal is complete, if `current_correct_guesses >= k`, increment `result`.\n- Return `result`.

## Optimal Two-Pass DFS (Rerooting)
The brute-force approach is inefficient because it recomputes the number of correct guesses from scratch for each potential root. A much more efficient method is the 'rerooting' technique, a form of dynamic programming on trees. We first calculate the answer for an arbitrary root (e.g., node 0), and then in a second pass, we efficiently calculate the answer for every other node by observing how the answer changes when we shift the root to an adjacent node.
**Time:** O(N + M), where N is the number of nodes and M is the number of guesses. Building the adjacency list is O(N), populating the `guessSet` is O(M). Each of the two DFS passes visits every node and edge once, taking O(N) time. The final counting step takes O(N). Thus, the total time complexity is linear. · **Space:** O(N + M). O(N) for the adjacency list, O(M) for the `guessSet`, O(N) for the `correctGuessesCount` array, and O(N) for the recursion stack in the worst-case (for a skewed tree).
**Pros:** Highly efficient, optimal solution that passes for large constraints.
**Cons:** More complex to conceptualize and implement compared to the brute-force approach.; Requires understanding of tree traversal and dynamic programming on trees.
### Explanation
This approach involves two Depth-First Searches (DFS).\n\n**First Pass (Post-order traversal style):** We arbitrarily choose node `0` as the root. We perform a DFS from node `0` to calculate `count0`, the number of correct guesses if the tree is rooted at `0`. During this DFS, when we traverse from a parent `u` to a child `v`, we check if the guess `(u, v)` exists. We sum up these correct guesses over the entire tree.\n\n**Second Pass (Pre-order traversal style):** Now, we perform a second DFS, also starting from node `0`. This time, we will calculate the number of correct guesses for every node. Let `correct_guesses[i]` be the number of correct guesses when `i` is the root. We already know `correct_guesses[0] = count0`.\n\nWhen we move the root from a parent `u` to its child `v`, the orientation of only one edge changes: the edge between `u` and `v`. It was `u -> v`, and now it becomes `v -> u`. All other parent-child relationships in the tree remain the same relative to their side of this edge.\n\nTherefore, the number of correct guesses for root `v` can be calculated from the number of correct guesses for root `u` with a simple adjustment:\n`correct_guesses[v] = correct_guesses[u] - (is_guess(u, v) ? 1 : 0) + (is_guess(v, u) ? 1 : 0)`\nWe use this formula to propagate the counts down the tree in our second DFS.\n\nAfter the second DFS completes, we will have the correct guess count for every possible root stored in an array. We can then iterate through this array and count how many nodes have a score of at least `k`.
```java
import java.util.*;

class Solution {
    List<List<Integer>> adj;
    Set<Long> guessSet;
    int n;
    int k;
    int[] correctGuessesCount;
    int countForRoot0 = 0;
    long factor;

    public int rootCount(int[][] edges, int[][] guesses, int k) {
        this.n = edges.length + 1;
        this.k = k;
        this.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]);
        }

        this.guessSet = new HashSet<>();
        this.factor = n;
        for (int[] guess : guesses) {
            guessSet.add((long) guess[0] * factor + guess[1]);
        }

        // Step 1: DFS from root 0 to calculate initial correct guess count
        dfs1(0, -1);

        // Step 2: DFS from root 0 again to calculate counts for all other nodes
        this.correctGuessesCount = new int[n];
        dfs2(0, -1, countForRoot0);

        // Step 3: Count the number of valid roots
        int result = 0;
        for (int count : correctGuessesCount) {
            if (count >= k) {
                result++;
            }
        }
        return result;
    }

    // DFS to calculate the number of correct guesses for the tree rooted at 0
    private void dfs1(int u, int p) {
        for (int v : adj.get(u)) {
            if (v == p) continue;
            // Edge is u -> v
            if (guessSet.contains(u * factor + v)) {
                countForRoot0++;
            }
            dfs1(v, u);
        }
    }

    // DFS to calculate correct guesses for all nodes using rerooting
    private void dfs2(int u, int p, int currentCorrectGuesses) {
        correctGuessesCount[u] = currentCorrectGuesses;

        for (int v : adj.get(u)) {
            if (v == p) continue;
            
            int nextCorrectGuesses = currentCorrectGuesses;
            // The edge u -> v is flipped to v -> u
            // If u -> v was a correct guess, we lose a point
            if (guessSet.contains(u * factor + v)) {
                nextCorrectGuesses--;
            }
            // If v -> u is a guess, we gain a point
            if (guessSet.contains(v * factor + u)) {
                nextCorrectGuesses++;
            }
            
            dfs2(v, u, nextCorrectGuesses);
        }
    }
}
```
### Algorithm
- Build an adjacency list for the tree.\n- Store `guesses` in a `HashSet` for `O(1)` lookups.\n- **DFS Pass 1:**\n  - Start a DFS from an arbitrary root, say node `0`.\n  - For each edge `u -> v` (where `u` is parent, `v` is child), check if `(u, v)` is in the `guessSet`.\n  - Calculate the total number of correct guesses for root `0`, let's call it `count_root_0`.\n- **DFS Pass 2:**\n  - Create an array `answer` of size `n`. Set `answer[0] = count_root_0`.\n  - Start a second DFS from root `0`.\n  - For a traversal from parent `u` to child `v`, calculate `answer[v]` using the formula: `answer[v] = answer[u] - (is_guess(u, v) ? 1 : 0) + (is_guess(v, u) ? 1 : 0)`.\n  - Recursively call the DFS for `v` with its calculated count.\n- **Final Count:**\n  - Iterate through the `answer` array and count how many values are `>= k`.

# Solutions
### Java

```java
class Solution {
private
  List<Integer>[] g;
private
  Map<Long, Integer> gs = new HashMap<>();
private
  int ans;
private
  int k;
private
  int cnt;
private
  int n;
public
  int rootCount(int[][] edges, int[][] guesses, int k) {
    this.k = k;
    n = edges.length + 1;
    g = new List[n];
    Arrays.setAll(g, e->new ArrayList<>());
    for (var e : edges) {
      int a = e[0], b = e[1];
      g[a].add(b);
      g[b].add(a);
    }
    for (var e : guesses) {
      int a = e[0], b = e[1];
      gs.merge(f(a, b), 1, Integer : : sum);
    }
    dfs1(0, -1);
    dfs2(0, -1);
    return ans;
  }
private
  void dfs1(int i, int fa) {
    for (int j : g[i]) {
      if (j != fa) {
        cnt += gs.getOrDefault(f(i, j), 0);
        dfs1(j, i);
      }
    }
  }
private
  void dfs2(int i, int fa) {
    ans += cnt >= k ? 1 : 0;
    for (int j : g[i]) {
      if (j != fa) {
        int a = gs.getOrDefault(f(i, j), 0);
        int b = gs.getOrDefault(f(j, i), 0);
        cnt -= a;
        cnt += b;
        dfs2(j, i);
        cnt -= b;
        cnt += a;
      }
    }
  }
private
  long f(int i, int j) { return 1L * i * n + j; }
}

```

### CPP

```cpp
class Solution {
public:
  int rootCount(vector<vector<int>> &edges, vector<vector<int>> &guesses,
                int k) {
    int n = edges.size() + 1;
    vector<vector<int>> g(n);
    unordered_map<long long, int> gs;
    auto f = [&](int i, int j) { return 1LL * i * n + j; };
    for (auto &e : edges) {
      int a = e[0], b = e[1];
      g[a].push_back(b);
      g[b].push_back(a);
    }
    for (auto &e : guesses) {
      int a = e[0], b = e[1];
      gs[f(a, b)]++;
    }
    int ans = 0;
    int cnt = 0;
    function<void(int, int)> dfs1 = [&](int i, int fa) {
      for (int &j : g[i]) {
        if (j != fa) {
          cnt += gs[f(i, j)];
          dfs1(j, i);
        }
      }
    };
    function<void(int, int)> dfs2 = [&](int i, int fa) {
      ans += cnt >= k;
      for (int &j : g[i]) {
        if (j != fa) {
          int a = gs[f(i, j)];
          int b = gs[f(j, i)];
          cnt -= a;
          cnt += b;
          dfs2(j, i);
          cnt -= b;
          cnt += a;
        }
      }
    };
    dfs1(0, -1);
    dfs2(0, -1);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def rootCount(self, edges: List[List[int]], guesses: List[List[int]], k: int) -> int: def dfs1(i, fa): nonlocal cnt for j in g[i]: if j != fa: cnt += gs[(i, j)] dfs1(j, i) def dfs2(i, fa): nonlocal ans, cnt ans += cnt >= k for j in g[i]: if j != fa: cnt -= gs[(i, j)] cnt += gs[(j, i)] dfs2(j, i) cnt -= gs[(j, i)] cnt += gs[(i, j)] g = defaultdict(list) for a, b in edges: g[a]. append(b) g[b]. append(a) gs = Counter((u, v) for u, v in guesses) cnt = 0 dfs1(0, - 1) ans = 0 dfs2(0, - 1) return ans

```