1. 題目鏈接

1617. 統計子樹中城市之間最大距離 - 力扣（LeetCode）

2. 題目描述

給你 n 個城市，編號為從 1 到 n 。同時給你一個大小為 n-1 的數組 edges ，其中 edges[i] = [ui, vi] 表示城市 ui 和 vi 之間有一條雙向邊。題目保證任意城市之間只有唯一的一條路徑。換句話說，所有城市形成了一棵 樹 。

一棵 子樹 是城市的一個子集，且子集中任意城市之間可以通過子集中的其他城市和邊到達。兩個子樹被認為不一樣的條件是至少有一個城市在其中一棵子樹中存在，但在另一棵子樹中不存在。

對于 d 從 1 到 n-1 ，請你找到城市間 最大距離 恰好為 d 的所有子樹數目。

請你返回一個大小為 n-1 的數組，其中第 d 個元素（下標從 1 開始）是城市間 最大距離 恰好等于 d 的子樹數目。

請注意，兩個城市間距離定義為它們之間需要經過的邊的數目。

3. 題目示例

示例 1 :

輸入：n = 4, edges = [[1,2],[2,3],[2,4]]
輸出：[3,4,0]
解釋：
子樹 {1,2}, {2,3} 和 {2,4} 最大距離都是 1 。
子樹 {1,2,3}, {1,2,4}, {2,3,4} 和 {1,2,3,4} 最大距離都為 2 。
不存在城市間最大距離為 3 的子樹。

示例 2 :

輸入：n = 2, edges = [[1,2]]
輸出：[1]

4. 解題思路

1. 問題理解：
   • 給定一棵樹，統計所有連通子圖
   • 對每個可能的直徑d，計算有多少子圖的直徑等于d
   • 直徑定義為子圖中最長路徑的邊數
2. 核心算法：
   • 使用回溯法枚舉所有可能的節點子集（2^n種可能）
   • 對每個子集檢查是否構成連通子圖
   • 計算連通子圖的直徑并統計結果
3. 直徑計算：
   • 采用樹形DP方法
   • 通過DFS計算每個節點的最長路徑
   • 在遞歸過程中維護全局直徑
4. 連通性檢查：
   • 比較訪問標記數組和選擇數組
   • 兩者一致說明子圖連通

5. 題解代碼

class Solution {private List<Integer>[] g; // 鄰接表存儲樹結構private boolean[] inSet;    // 記錄哪些節點在當前子集中private boolean[] vis;      // DFS訪問標記private int[] ans;          // 結果數組，ans[d]表示直徑為d+1的子圖數量private int n, diameter;   // n是節點總數，diameter記錄當前子圖的直徑public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {this.n = n;// 初始化鄰接表g = new ArrayList[n];Arrays.setAll(g, e -> new ArrayList<>());// 構建樹結構（節點編號轉為0-based）for (var e : edges) {int x = e[0] - 1, y = e[1] - 1;g[x].add(y);g[y].add(x);}ans = new int[n - 1]; // 直徑范圍是1到n-1inSet = new boolean[n];f(0); // 開始遞歸枚舉所有子集return ans;}// 遞歸枚舉所有可能的節點子集private void f(int i) {// 遞歸終止條件：處理完所有節點if (i == n) {// 檢查當前子集是否構成連通子圖for (int v = 0; v < n; ++v)if (inSet[v]) {vis = new boolean[n];diameter = 0;dfs(v); // 從第一個選中的節點開始DFSbreak;}// 如果子圖連通且直徑有效，更新結果if (diameter > 0 && Arrays.equals(vis, inSet))++ans[diameter - 1];return;}// 不選當前節點if(i + 1);// 選當前節點iinSet[i] = true;f(i + 1);inSet[i] = false; // 回溯}// 計算子圖的直徑（同時標記訪問過的節點）private int dfs(int x) {vis[x] = true;int maxLen = 0; // 記錄從x出發的最長路徑長度for (int y : g[x])if (!vis[y] && inSet[y]) { // 只考慮選中的且未訪問的鄰居int ml = dfs(y) + 1;  // 遞歸計算子節點路徑長度diameter = Math.max(diameter, maxLen + ml); // 更新直徑maxLen = Math.max(maxLen, ml); // 更新當前最大長度}return maxLen;}
}

6. 復雜度分析

時間復雜度：O(n * 2^n)

• 枚舉所有子集：O(2^n)
• 對每個子集進行DFS：O(n)
• 總復雜度為兩者的乘積

空間復雜度：O(n)

• 鄰接表存儲空間：O(n)
• 遞歸調用棧深度：O(n)
• 各種標記數組：O(n)