💥💥Beats 100% on runtime and memory [EXPLAINED]
Intuition\nThe problem revolves around understanding trees as a special type of graph where there\u2019s a unique path between any two nodes. Each subtree forme
# Intuition\nThe problem revolves around understanding trees as a special type of graph where there\u2019s a unique path between any two nodes. Each subtree formed by selecting nodes can have various distances between its furthest nodes, and our goal is to count how many of these subtrees correspond to each possible maximum distance.\n\n\n# Approach\nWe first build a graph from the edges, then iterate through all possible subsets of nodes using bit manipulation to determine which nodes are included, checking if the subset forms a single connected component, and if so, calculating its diameter (maximum distance) using depth-first search; we store these counts in an array corresponding to their diameters.\n\n\n# Complexity\n- Time complexity:\nO(n . 2n) because we evaluate all subsets (up to 2n) and check the connected components and diameters for each subset.\n\n\n- Space complexity:\nO(n) for storing the graph and auxiliary data structures like visited nodes and depths during the DFS.\n\n\n# Code\n```typescript []\n/**\n * Calculate the diameter of the tree formed by the selected nodes.\n * @param graph - The adjacency list representing the graph.\n * @param nodes - The nodes selected for the subtree.\n * @param n - The total number of nodes.\n * @returns The diameter of the tree.\n */\nfunction getTreeDiameter(graph: Map<number, number[]>, nodes: number[], n: number): number {\n    if (nodes.length === 1) return 0; // A single node has no diameter\n\n    const root = nodes[0]; // Start DFS from the first node\n    const depths = Array(n).fill(0); // Array to store depths of each node\n    const visited = new Set<number>(); // Set to track visited nodes\n\n    // Depth-first search to calculate depths\n    function dfs(node: number, depth: number): void {\n        if (visited.has(node)) return; // Return if already visited\n        visited.add(node);\n        depths[node] = depth; // Set the depth for the current node\n        for (const to of graph.get(node) || []) {\n            if (!visited.has(to) && nodes.includes(to)) {\n                dfs(to, depth + 1); // Recursive DFS for adjacent nodes\n            }\n        }\n    }\n\n    // Second DFS to find the maximum distance from the furthest node\n    function dfs2(node: number): number {\n        if (visited.has(node)) return 0; // Return if already visited\n        visited.add(node);\n        let dist = 0;\n        for (const to of graph.get(node) || []) {\n            if (!visited.has(to) && nodes.includes(to)) {\n                dist = Math.max(dist, dfs2(to) + 1); // Find max distance\n            }\n        }\n        return dist; // Return the maximum distance found\n    }\n\n    // Perform first DFS to calculate depths\n    dfs(root, 0);\n    let maxDepth = -1;\n    let furthestNode = -1;\n\n    // Identify the furthest node from the root\n    for (const node of nodes) {\n        if (depths[node] > maxDepth) {\n            maxDepth = depths[node];\n            furthestNode = node;\n        }\n    }\n\n    visited.clear(); // Clear visited set for the second DFS\n    return dfs2(furthestNode); // Get the diameter from the furthest node\n}\n\n/**\n * Get the size of the connected component for the selected nodes.\n * @param graph - The adjacency list representing the graph.\n * @param nodes - The nodes selected for the component.\n * @param n - The total number of nodes.\n * @returns The size of the connected component.\n */\nfunction getComponentSize(graph: Map<number, number[]>, nodes: number[], n: number): number {\n    let count = 0; // Count of connected components\n    const visited = Array(n).fill(false); // Array to track visited nodes\n\n    // Depth-first search to mark connected nodes\n    function dfs(node: number): void {\n        if (visited[node]) return; // Return if already visited\n        visited[node] = true; // Mark the node as visited\n        for (const to of graph.get(node) || []) {\n            if (!visited[to] && nodes.includes(to)) {\n                dfs(to); // Recursive DFS for adjacent nodes\n            }\n        }\n    }\n\n    // Iterate through selected nodes to count components\n    for (const node of nodes) {\n        if (!visited[node]) {\n            dfs(node); // Perform DFS for each unvisited node\n            count += 1; // Increment count for each component found\n        }\n    }\n    return count; // Return the total number of components\n}\n\n/**\n * Count the number of subgraphs for each diameter.\n * @param n - The total number of nodes.\n * @param edges - The edges connecting the nodes.\n * @returns An array with counts of subgraphs for each diameter.\n */\nconst countSubgraphsForEachDiameter = function (n: number, edges: number[][]): number[] {\n    const graph = new Map<number, number[]>(); // Graph representation\n    const distMap = new Map<number, number[][]>(); // Map to store distances and corresponding nodes\n\n    // Build the graph from the edges\n    for (const [a, b] of edges) {\n        const u = a - 1; // Convert to 0-based index\n        const v = b - 1;\n        if (!graph.has(u)) {\n            graph.set(u, []);\n        }\n        if (!graph.has(v)) {\n            graph.set(v, []);\n        }\n        graph.get(u)!.push(v); // Add edge to the graph\n        graph.get(v)!.push(u);\n    }\n\n    // Iterate over all subsets of nodes using bit masking\n    for (let mask = 0; mask < (1 << n); mask++) {\n        const select: number[] = []; // Selected nodes for the current subset\n        for (let j = 0; j < n; j++) {\n            if (mask & (1 << j)) {\n                select.push(j); // Add the node if it\'s included in the subset\n            }\n        }\n\n        // Get the size of the connected component for the selected nodes\n        const size = getComponentSize(graph, select, n);\n        if (size === 1) { // Only consider single components\n            const dist = getTreeDiameter(graph, select, n); // Calculate tree diameter\n            if (!distMap.has(dist)) {\n                distMap.set(dist, []);\n            }\n            distMap.get(dist)!.push(select); // Store the nodes for the diameter\n        }\n    }\n\n    const ans = Array(n - 1).fill(0); // Initialize answer array\n    for (let d = 1; d <= n - 1; d++) {\n        const count = distMap.get(d)?.length || 0; // Count for diameter d\n        ans[d - 1] = count; // Store in result\n    }\n    return ans; // Return the final counts for each diameter\n};\n\n```
['TypeScript']