What is the pattern for solving 'Count Subtrees With Max Distance Between Cities'?

The pattern revolves around binary-tree traversal and state tracking, specifically using bitmasking and dynamic programming to efficiently find subtrees and their maximum distances.

How do I use bitmasking for this problem?

Bitmasking is used to represent every possible subset of cities, which helps in efficiently iterating over potential subtrees and checking their validity and maximum distance.

How do I determine if a subtree is valid?

To determine if a subtree is valid, check if all cities in the subset are connected. This can be done using DFS or BFS to ensure the subset forms a valid tree structure.

What is the time complexity of this approach?

The time complexity is O(2^n * n), where n is the number of cities. This comes from iterating over all subsets using bitmasking and performing a tree traversal for each subset.

Can this problem be optimized further?

Yes, further optimizations can be achieved by reducing redundant calculations using dynamic programming and efficiently managing the bitmasking process.

#1617

Hard

auto_awesome二分·树·traversal

LeetCode 题解工作台

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

给你 n 个城市，编号为从 1 到 n 。同时给你一个大小为 n-1 的数组 edges ，其中 edges[i] = [u i , v i ] 表示城市 u i 和 v i 之间有一条双向边。题目保证任意城市之间只有唯一的一条路径。换句话说，所有城市形成了一棵树。一棵子树是城市的一个子集…

动态规划位运算树枚举位掩码

题目描述

给你 n 个城市，编号为从 1 到 n 。同时给你一个大小为 n-1 的数组 edges ，其中 edges[i] = [u_i, v_i] 表示城市 u_i 和 v_i之间有一条双向边。题目保证任意城市之间只有唯一的一条路径。换句话说，所有城市形成了一棵树。

一棵子树是城市的一个子集，且子集中任意城市之间可以通过子集中的其他城市和边到达。两个子树被认为不一样的条件是至少有一个城市在其中一棵子树中存在，但在另一棵子树中不存在。

对于 d 从 1 到 n-1 ，请你找到城市间 最大距离 恰好为 d 的所有子树数目。

请你返回一个大小为 n-1 的数组，其中第 d 个元素（下标从 1 开始）是城市间 最大距离 恰好等于 d 的子树数目。

请注意，两个城市间距离定义为它们之间需要经过的边的数目。

示例 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]

示例 3：

输入：n = 3, edges = [[1,2],[2,3]]
输出：[2,1]

提示：

2 <= n <= 15
edges.length == n-1
edges[i].length == 2
1 <= u_i, v_i <= n
题目保证 (u_i, v_i) 所表示的边互不相同。

lightbulb

解题思路

方法一：二进制枚举 + BFS 或 DFS

我们注意到 $n \leq 15$ ，因此可以考虑使用二进制枚举的方法枚举所有的子树。而子树中节点的最大距离，其实就是子树中两个节点之间的最长路径，也即是树的直径，求解树的直径一般可以使用 DFS 或 BFS，先找到树直径的一个端点，然后再从该端点出发，找到树的另一个端点，这两个端点之间的路径长度就是树的直径。

接下来，我们详细说明具体的代码实现。

我们先根据数组 $edges$ 构建出邻接表 $g$ ，其中 $g[u]$ 表示节点 $u$ 的所有邻接节点。

用一个二进制数 $mask$ 表示子树，其中 $mask$ 的第 $i$ 位为 $1$ 表示节点 $i$ 在子树中，否则表示节点 $i$ 不在子树中。每个节点都有两种状态，即在子树中或不在子树中，有 $n$ 个节点，因此一共有 $2^n$ 种状态。

接下来，我们在 $[1,..2^n-1]$ 的范围内枚举子树 $mask$ ，对于每个子树：

如果 $mask$ 的二进制表示中只有一个二进制位为 $1$ ，即 $mask \in [1,2,4,8,\cdots,2^{n-1}]$ ，则跳过该 $mask$ ，因为这些 $mask$ 表示的子树只有一个节点，不符合题意；

否则，我们找到 $mask$ 的二进制表示中最高位的二进制位为 $1$ 的位置，记为 $cur$ 。然后从节点 $cur$ 出发，通过深度优先搜索或者广度优先搜索，找到树直径的一个端点 $nxt$ ，然后我们再从节点 $nxt$ 出发，同样通过深度优先搜索或者广度优先搜索，过程中记录下最大距离 $mx$ 。

当走到最深的节点时，即可得知树的直径。此时我们更新答案数组 $ans$ ，将 $ans[mx-1]$ 的值加 $1$ 。注意，这里是 $mx-1$ ，因为题目中的最大距离是从 $1$ 开始计数的。

最后，枚举完所有的子树，返回答案数组 $ans$ 即可。

时间复杂度 $O(2^n \times n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

class Solution:
    def countSubgraphsForEachDiameter(
        self, n: int, edges: List[List[int]]
    ) -> List[int]:
        def dfs(u: int, d: int = 0):
            nonlocal mx, nxt, msk
            if mx < d:
                mx, nxt = d, u
            msk ^= 1 << u
            for v in g[u]:
                if msk >> v & 1:
                    dfs(v, d + 1)

        g = defaultdict(list)
        for u, v in edges:
            u, v = u - 1, v - 1
            g[u].append(v)
            g[v].append(u)
        ans = [0] * (n - 1)
        nxt = mx = 0
        for mask in range(1, 1 << n):
            if mask & (mask - 1) == 0:
                continue
            msk, mx = mask, 0
            cur = msk.bit_length() - 1
            dfs(cur)
            if msk == 0:
                msk, mx = mask, 0
                dfs(nxt)
                ans[mx - 1] += 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's understanding of bitmasking and dynamic programming techniques.
question_mark
Assess the candidate's ability to handle tree traversal efficiently within constraints.
question_mark
Evaluate their ability to optimize the algorithm, especially considering time and space complexity.

warning

常见陷阱

外企场景

error
Not efficiently managing the bitmasking process and trying to iterate through all subsets without considering optimizations.
error
Failing to validate whether a subset forms a connected graph before calculating the maximum distance between cities.
error
Overlooking the importance of dynamic programming in storing precomputed values to avoid redundant calculations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increase the number of cities to test the scalability of the solution.
arrow_right_alt
Consider additional constraints such as weighted edges or directed edges to modify the problem.
arrow_right_alt
Modify the problem to count subtrees with a fixed number of cities and a maximum distance limit.

help

常见问题

外企场景

继续练习

#1595 连通两组点的最小成本 #1655 分配重复整数 #1659 最大化网格幸福感