There is an undirected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.

You are given 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. You are also given an integer array restricted which represents restricted nodes.

Return the maximum number of nodes you can reach from node 0 without visiting a restricted node.

Note that node 0 will not be a restricted node.

&nbsp;
Example 1:

Input: n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]
Output: 4
Explanation: The diagram above shows the tree.
We have that [0,1,2,3] are the only nodes that can be reached from node 0 without visiting a restricted node.


Example 2:

Input: n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1]
Output: 3
Explanation: The diagram above shows the tree.
We have that [0,5,6] are the only nodes that can be reached from node 0 without visiting a restricted node.


&nbsp;
Constraints:


	2 &lt;= n &lt;= 105
	edges.length == n - 1
	edges[i].length == 2
	0 &lt;= ai, bi &lt; n
	ai != bi
	edges represents a valid tree.
	1 &lt;= restricted.length &lt; n
	1 &lt;= restricted[i] &lt; n
	All the values of restricted are unique.


class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
        # ignore restricted node
        # bfs from 0
        
        # O(E), EDITED: the time complexity here is wrong, plz see my comment
        adj_dict = collections.defaultdict(list)
        for u, v in edges:
            if u in restricted or v in restricted:  # EDITED: not O(1)
                continue
            adj_dict[u].append(v)
            adj_dict[v].append(u)
        
        # O(V + E)
        queue = collections.deque([0])
        visited = {0}
        while queue:
            cur = queue.popleft()
            for neighbor in adj_dict[cur]:
                if neighbor in visited:
                    continue
                visited.add(neighbor)
                queue.append(neighbor)

        return len(visited)
class Solution {
    int count=0;
    ArrayList<ArrayList<Integer>> adj=new ArrayList<>();
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        boolean[] vis=new boolean[n];
        for(int i:restricted){
            vis[i]=true;
        }
        for(int i=0;i<n;i++){
            adj.add(new ArrayList<>());
        }
        for(int[] ii:edges){
            adj.get(ii[0]).add(ii[1]);
            adj.get(ii[1]).add(ii[0]);
        }
        dfs(0,vis);
        return count;
    }
    private void dfs(int node,boolean[] vis){
        vis[node]=true;
        count++;
        for(int it:adj.get(node)){
            if(vis[it]==false){
                dfs(it,vis);
            }
        }
    }
}
class Solution {
public:
    int count=1;  // node 0 is already reached as it is starting point
    vector<vector<int>> graph;
    unordered_set<int> res;  // to store restricted numbers for fast fetch
    vector<bool> vis;  // visited array for DFS
    
    void dfs(int i){
        for(int y: graph[i]){
            if(!vis[y] && res.count(y)==0){
                vis[y]= true;
                dfs(y);
                count++;
            }
        }
    }
    
    int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
        for(int x:restricted) res.insert(x);
        
        // creating graph
        graph.resize(n);
        vis.resize(n);
        for(auto &x:edges){
            graph[x[0]].push_back(x[1]);
            graph[x[1]].push_back(x[0]);
        }
        
        // mark 0 as visited coz it is starting point and is already reached 
        vis[0]= true;
        dfs(0);
        
        return count;
    }
};
/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number[]} restricted
 * @return {number}
 */
var reachableNodes = function(n, edges, restricted) {
    const adj = {};
    
    for (const [u, v] of edges) {
        if (adj[u]) {
            adj[u].add(v);
        } else {
            adj[u] = new Set().add(v);
        }
        if (adj[v]) {
            adj[v].add(u);
        } else {
            adj[v] = new Set().add(u);
        }
    }
    
    const restrictedSet = new Set(restricted);
    const visited = new Set();
    
    let ans = 0;
    
    function dfs(node) {
        if (restrictedSet.has(node) || visited.has(node)) {
            return;
        }
        
        ans++;
        visited.add(node);
        
        for (const adjNode of adj[node]) {
            dfs(adjNode);
        }
    }
    
    dfs(0);
    
    return ans;
};
Reachable Nodes With Restrictions