<p>Alice has an undirected tree with <code>n</code> nodes labeled from <code>0</code> to <code>n - 1</code>. The tree is represented as a 2D integer array <code>edges</code> of length <code>n - 1</code> where <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> indicates that there is an edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> in the tree.</p>

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

<ul>
	<li>Chooses two <strong>distinct</strong> integers <code>u</code> and <code>v</code> such that there exists an edge <code>[u, v]</code> in the tree.</li>
	<li>He tells Alice that <code>u</code> is the <strong>parent</strong> of <code>v</code> in the tree.</li>
</ul>

<p>Bob&#39;s guesses are represented by a 2D integer array <code>guesses</code> where <code>guesses[j] = [u<sub>j</sub>, v<sub>j</sub>]</code> indicates Bob guessed <code>u<sub>j</sub></code> to be the parent of <code>v<sub>j</sub></code>.</p>

<p>Alice being lazy, does not reply to each of Bob&#39;s guesses, but just says that <strong>at least</strong> <code>k</code> of his guesses are <code>true</code>.</p>

<p>Given the 2D integer arrays <code>edges</code>, <code>guesses</code> and the integer <code>k</code>, return <em>the <strong>number of possible nodes</strong> that can be the root of Alice&#39;s tree</em>. If there is no such tree, return <code>0</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2022/12/19/ex-1.png" style="width: 727px; height: 250px;" /></p>

<pre>
<strong>Input:</strong> edges = [[0,1],[1,2],[1,3],[4,2]], guesses = [[1,3],[0,1],[1,0],[2,4]], k = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> 
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.

</pre>

<p><strong class="example">Example 2:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2022/12/19/ex-2.png" style="width: 600px; height: 303px;" /></p>

<pre>
<strong>Input:</strong> edges = [[0,1],[1,2],[2,3],[3,4]], guesses = [[1,0],[3,4],[2,1],[3,2]], k = 1
<strong>Output:</strong> 5
<strong>Explanation:</strong> 
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. 

</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>edges.length == n - 1</code></li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= guesses.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub>, u<sub>j</sub>, v<sub>j</sub> &lt;= n - 1</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li><code>u<sub>j</sub> != v<sub>j</sub></code></li>
	<li><code>edges</code> represents a valid tree.</li>
	<li><code>guesses[j]</code> is an edge of the tree.</li>
	<li><code>guesses</code> is unique.</li>
	<li><code>0 &lt;= k &lt;= guesses.length</code></li>
</ul>

from typing import List, Dict, Set

def rootCount(edges: List[List[int]], guesses: List[List[int]], k: int) -> int:
    # Step 1: Handle the case where the tree has only one node
    if len(edges) == 0:
        return 1 if k == 0 else 0
    
    # Step 2: Initialize the adjacency list for the tree
    tree: Dict[int, List[int]] = {}
    for u, v in edges:
        if u not in tree:
            tree[u] = []
        if v not in tree:
            tree[v] = []
        tree[u].append(v)
        tree[v].append(u)
    
    # Step 3: Initialize the set for guesses
    guess_set: Set[tuple] = set()
    for u, v in guesses:
        guess_set.add((u, v))
    
    # Step 4: Perform DFS to determine parent-child relationships
    def dfs(node: int, parent: int, parent_child: Dict[int, int]):
        for neighbor in tree[node]:
            if neighbor != parent:
                parent_child[neighbor] = node
                dfs(neighbor, node, parent_child)
    
    parent_child: Dict[int, int] = {}
    dfs(0, -1, parent_child)
    
    # Step 5: Count correct guesses for the initial root (node 0)
    correct_guesses = 0
    for child, parent in parent_child.items():
        if (parent, child) in guess_set:
            correct_guesses += 1
    
    # Step 6: Initialize data structures for re-rooting
    correct_guess_count = [0] * len(tree)
    correct_guess_count[0] = correct_guesses
    visited = set()
    
    # Step 7: Define the DFS function for propagation
    def propagate_dfs(node: int, parent: int):
        visited.add(node)
        for neighbor in tree[node]:
            if neighbor != parent:
                # Update the correct guess count for the child node
                correct_guess_count[neighbor] = correct_guess_count[node]
                if (node, neighbor) in guess_set:
                    correct_guess_count[neighbor] -= 1
                if (neighbor, node) in guess_set:
                    correct_guess_count[neighbor] += 1
                propagate_dfs(neighbor, node)
    
    # Step 8: Start the DFS traversal from the initial root (node 0)
    propagate_dfs(0, -1)
    
    # Step 9: Count valid roots
    valid_roots = sum(1 for count in correct_guess_count if count >= k)
    
    return valid_roots



class Solution:
    def rootCount(self, *args, **kwargs):
        return rootCount(*args, **kwargs)


1700