We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Subtrees With Max Distance Between Cities

Difficulty: Hard

Problem Description

Given n cities numbered from 1 to n, and an array edges of size n-1 representing bidirectional edges between cities, find the number of subtrees for each distance d from 1 to n-1, where the maximum distance between any two cities in the subtree is equal to d.

Key Insights

  • The cities form a tree structure, ensuring unique paths between any pair of cities.
  • A subtree is defined as a subset of cities where every city can be reached from any other within the subset.
  • The maximum distance in a subtree is determined by the longest path (in terms of edges) between any two cities in that subtree.
  • For each possible maximum distance d, count how many unique subtrees exist that have this distance.

Space and Time Complexity

Time Complexity: O(n^2) - For each pair of cities, we may need to explore possible subtrees. Space Complexity: O(n) - For storing the graph structure (tree).

Solution

To solve the problem, we will utilize a tree representation using adjacency lists. The approach will involve:

  1. Constructing the tree from the given edges.
  2. Enumerating all possible subsets of cities to form candidate subtrees.
  3. For each candidate subtree, calculating the maximum distance (using BFS or DFS) and counting the occurrences for each distance.

This brute-force approach is feasible due to the small constraint on n (up to 15), allowing for an exhaustive enumeration of subsets.

Code Solutions

from collections import defaultdict
from itertools import combinations

def countSubtrees(n, edges):
    # Construct the tree using adjacency list
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    def bfs(start, nodes):
        # BFS to find maximum distance from start to any node in nodes
        visited = set()
        queue = [(start, 0)]  # (current node, current distance)
        max_distance = 0
        
        while queue:
            current, dist = queue.pop(0)
            if current in visited:
                continue
            visited.add(current)
            max_distance = max(max_distance, dist)
            for neighbor in graph[current]:
                if neighbor in nodes and neighbor not in visited:
                    queue.append((neighbor, dist + 1))
        
        return max_distance
    
    # Initialize counts for distances
    count = [0] * (n - 1)
    
    # Enumerate all subsets of nodes
    for size in range(2, n + 1):  # subsets of size 2 to n
        for subset in combinations(range(1, n + 1), size):
            max_dist = 0
            for node in subset:
                max_dist = max(max_dist, bfs(node, subset))
            
            if max_dist > 0:
                count[max_dist - 1] += 1
    
    return count

# Example usage
print(countSubtrees(4, [[1,2],[2,3],[2,4]]))  # Output: [3, 4, 0]
← Back to All Questions