统计子树中城市之间最大距离【LC1617】
给你
n个城市，编号为从1到n。同时给你一个大小为n-1的数组edges，其中edges[i] = [ui, vi]表示城市ui和vi之间有一条双向边。题目保证任意城市之间只有唯一的一条路径。换句话说，所有城市形成了一棵 树 。一棵 子树 是城市的一个子集，且子集中任意城市之间可以通过子集中的其他城市和边到达。两个子树被认为不一样的条件是至少有一个城市在其中一棵子树中存在，但在另一棵子树中不存在。
对于
d从1到n-1，请你找到城市间 最大距离 恰好为d的所有子树数目。请你返回一个大小为
n-1的数组，其中第d个元素（下标从 1 开始）是城市间 最大距离 恰好等于d的子树数目。请注意，两个城市间距离定义为它们之间需要经过的边的数目。
就是说要考虑好多 做完来练一下树形dp吧
- 思路
实现
- 首先根据数组
edges构建出邻接表g - 使用二进制数
mask表示子树，第i位为1表示节点i在子树中，否则表示节点i不在子树中
然后枚举子树mask
- 如果
mask的二进制表示中只有一个二进制位为1，那么跳过该mask - 否则，找到
mask的二进制表示中最高位的二进制为1的位置，进行dfs搜索树的直径，如果mask中的节点全部访问过，表示该mask有效，更新结果；否则表示该mask不是合法的子树 - 最后返回结果即可
class Solution { private List<Integer>[] g; private int mask, vis, diameter; public int[] countSubgraphsForEachDiameter(int n, int[][] edges) { g = new ArrayList[n]; Arrays.setAll(g, e -> new ArrayList<>()); for (var e : edges) { int x = e[0] - 1, y = e[1] - 1; // 编号改为从 0 开始 g[x].add(y); g[y].add(x); // 建树 } var ans = new int[n - 1]; // 二进制枚举 for (mask = 3; mask < 1 << n; ++mask) { if ((mask & (mask - 1)) == 0) continue; // 需要至少两个点 vis = diameter = 0; dfs(Integer.numberOfTrailingZeros(mask)); // 从一个在 mask 中的点开始递归 if (vis == mask) ++ans[diameter - 1]; } return ans; } // 求树的直径 private int dfs(int x) { vis |= 1 << x; // 标记 x 访问过 int maxLen = 0; for (int y : g[x]) if ((vis >> y & 1) == 0 && (mask >> y & 1) == 1) { // y 没有访问过且在 mask 中 int ml = dfs(y) + 1; diameter = Math.max(diameter, maxLen + ml); maxLen = Math.max(maxLen, ml); } return maxLen; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/count-subtrees-with-max-distance-between-cities/solutions/2162612/tu-jie-on3-mei-ju-zhi-jing-duan-dian-che-am2n/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
