LeetCode 1617: Count Subtrees With Max Distance Between Cities
Problem Description
Explanation
To solve this problem, we can use dynamic programming combined with tree traversal techniques. We first build a tree structure from the given edges. Then, for each node in the tree, we calculate the number of subtrees with maximum distance d for all d from 1 to n-1. We do this by considering each node as the root of the subtree and calculating the distances of all nodes from this root. We use these distances to count the number of subtrees with maximum distance d.
We can perform a depth-first search (DFS) to traverse the tree and calculate distances from each node to all other nodes. Then, we can use dynamic programming to calculate the number of subtrees with maximum distance d for each node.
Time complexity: O(n^2)
Space complexity: O(n)
Solutions
class Solution {
public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {
// Create the tree structure
List<Integer>[] tree = new ArrayList[n];
for (int i = 0; i < n; i++) {
tree[i] = new ArrayList<>();
}
for (int[] edge : edges) {
tree[edge[0] - 1].add(edge[1] - 1);
tree[edge[1] - 1].add(edge[0] - 1);
}
int[] result = new int[n - 1];
for (int i = 0; i < (1 << n); i++) {
boolean[] visited = new boolean[n];
int count = 0;
int maxDist = 0;
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) > 0) {
count++;
maxDist = dfs(tree, visited, j, i) - 1;
}
}
if (count > 1 && maxDist > 0) {
result[maxDist - 1]++;
}
}
return Arrays.copyOfRange(result, 0, n - 1);
}
private int dfs(List<Integer>[] tree, boolean[] visited, int node, int mask) {
visited[node] = true;
int maxDist = 0;
for (int neighbor : tree[node]) {
if (!visited[neighbor] && ((mask & (1 << neighbor)) > 0)) {
maxDist = Math.max(maxDist, 1 + dfs(tree, visited, neighbor, mask));
}
}
return maxDist;
}
}Loading editor...