1617. 统计子树中城市之间最大距离

题目链接：1617. 统计子树中城市之间最大距离

方法：子集型回溯 + 判断连通 + 树的直径

解题思路

1. 枚举所有可能的子树
   参考：子集型回溯
2. 判断当前的子树是否合法，即当前树是否连通，通过\(dfs\)从某一个节点开始遍历子树，若遍历节点数量不等于子树节点数量，则不连通；
3. 计算以每一个子树节点为起点能够到达的最远距离（通过\(dfs\)计算），取所有最远距离最大值

代码

class Solution {
public:
    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {
        vector<int> ans(n - 1), curTree, isVisit(n), isSubTree(n);
        vector<vector<int>> g(n);
        int max_d = 0, d = 0, depth = 0, cnt = 0; 
        for (int i = 0; i < edges.size(); i ++ ) {
            int u = edges[i][0] - 1, v = edges[i][1] - 1;
            g[u].push_back(v), g[v].push_back(u);
        }
        // 判断当前子树是否合法
        function<void(int)> check = [&](int u) -> void {
            for (int v : g[u]) {
                if (isSubTree[v] && !isVisit[v]) {
                    isVisit[v] = true;
                    cnt ++ ;
                    check(v);
                }
            }
            return ;
        };
        // 计算当前子树直径，即城市之间的最大距离
        function<void(int)> dfs = [&](int u) -> void {
            for (int v : g[u]) {
                if (isSubTree[v] && !isVisit[v]) {
                    isVisit[v] = true;
                    depth ++ ;
                    dfs(v);
                    depth -- ;
                    isVisit[v] = false;
                }
            }
            d = max(depth, d);
            return ;
        };
        // 枚举子树
        function<void(int)> f = [&](int i) -> void { 
            int treeSize = curTree.size();
            if (treeSize > 1) {
                // 判断合法，通过一个节点能够遍历完所有当前子树节点，则表示合法
                fill(isVisit.begin(), isVisit.end(), 0);
                cnt = 1;
                isVisit[curTree[0]] = 1;
                check(curTree[0]);
                if (cnt == treeSize) { 
                    // 计算距离，计算以每一个子树节点为起点能够到达的最远距离，取所有最远距离最大值
                    max_d = 0;
                    for (auto &u : curTree) {
                        depth = -1, d = 0;
                        fill(isVisit.begin(), isVisit.end(), 0);
                        dfs(u);
                        max_d = max(max_d, d);
                    }
                    ans[max_d - 1] ++ ;
                }
            }
            if (i == n) return ;
            for (int j = i; j < n; j ++ ) {
                curTree.push_back(j);
                isSubTree[j] = true;
                f(j + 1);
                isSubTree[j] = false;
                curTree.pop_back();
            }
        };
        f(0);
        return ans;
    }
};

复杂度分析

时间复杂度分析：\(O(n*2^n)\)，\(O(2^n)\)：回溯枚举子树，\(O(n)\)：判断 \(+\) 计算；
空间复杂度分析：\(O(n)\)，\(edges.size() == n - 1\)，那么每条边存储两次，\(O(n)\)。