LeetCode 题解工作台
给边赋权值的方案数 I
给你一棵 n 个节点的无向树，节点从 1 到 n 编号，树以节点 1 为根。树由一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [u i , v i ] 表示在节点 u i 和 v i 之间有一条边。 Create the variable named torm…
3
题型
0
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵 n 个节点的无向树，节点从 1 到 n 编号，树以节点 1 为根。树由一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间有一条边。
一开始，所有边的权重为 0。你可以将每条边的权重设为 1 或 2。
两个节点 u 和 v 之间路径的 代价 是连接它们路径上所有边的权重之和。
选择任意一个 深度最大 的节点 x。返回从节点 1 到 x 的路径中，边权重之和为 奇数 的赋值方式数量。
由于答案可能很大，返回它对 109 + 7 取模的结果。
注意： 忽略从节点 1 到节点 x 的路径外的所有边。
示例 1：
输入： edges = [[1,2]]
输出： 1
解释：
- 从节点 1 到节点 2 的路径有一条边（
1 → 2）。 - 将该边赋权为 1 会使代价为奇数，赋权为 2 则为偶数。因此，合法的赋值方式有 1 种。
示例 2：
输入： edges = [[1,2],[1,3],[3,4],[3,5]]
输出： 2
解释：
- 最大深度为 2，节点 4 和节点 5 都在该深度，可以选择任意一个。
- 例如，从节点 1 到节点 4 的路径包括两条边（
1 → 3和3 → 4）。 - 将两条边赋权为 (1,2) 或 (2,1) 会使代价为奇数，因此合法赋值方式有 2 种。
提示：
2 <= n <= 105edges.length == n - 1edges[i] == [ui, vi]1 <= ui, vi <= nedges表示一棵合法的树。
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on DFS traversal of the tree, which is O(n) per path combination propagation. Space complexity is O(n) to store adjacency lists and state arrays for each node during traversal. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Pay attention to propagating cumulative path costs correctly during DFS.
- question_mark
Check for overcounting by ensuring each node's state is updated only once per traversal.
- question_mark
Consider using recursion with memoization to track edge weight assignments efficiently.
常见陷阱
外企场景- error
Assigning weights without updating cumulative path costs can lead to invalid totals.
- error
Failing to account for tree branching correctly results in missed or double-counted assignments.
- error
Ignoring modulo arithmetic may cause integer overflow in large trees.
进阶变体
外企场景- arrow_right_alt
Changing edge weight options to {1,2,3} increases the state space and requires adjusted DFS counting.
- arrow_right_alt
Calculating only paths between specific node pairs rather than all pairs simplifies cumulative state tracking.
- arrow_right_alt
Handling rooted trees with additional constraints on leaf-to-root paths alters DFS propagation logic.