Medium

题目描述

有一个由 n 个节点组成的无向树，节点标号从 1 到 n，以节点 1 为根。树由长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 之间有一条边。

初始时，所有边的权重都是 0。你必须为每条边分配权重 1 或 2。

任意两个节点 u 和 v 之间路径的代价是连接它们路径上所有边的权重总和。

选择最大深度处的任意一个节点 x。返回从节点 1 到节点 x 的路径上分配边权重使其总代价为奇数的方案数。

由于答案可能很大，返回其对 10^9 + 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 <= 10^5
  • edges.length == n - 1
  • edges[i] == [ui, vi]
  • 1 <= ui, vi <= n
  • edges 表示一个有效的树

解题思路

这道题的关键洞察在于理解奇偶性规律。

首先，我们需要找到树的最大深度。由于树以节点 1 为根，我们可以使用 DFS 从根节点开始遍历，计算每个节点的深度。

接下来分析权重分配的奇偶性：

  • 每条边可以分配权重 1 或 2
  • 路径总代价为奇数，意味着所有边权重之和为奇数
  • 关键观察：权重为 2 的边不影响奇偶性（因为 2 是偶数）
  • 只有权重为 1 的边会影响奇偶性

因此，要使路径总代价为奇数，我们需要在从根到最大深度节点的路径上选择奇数个边分配权重 1，其余边可以分配权重 1 或 2。

对于深度为 max_depth 的路径（包含 max_depth 条边）：

  • 选择奇数个位置放权重 1：C(max_depth, 1) + C(max_depth, 3) + …
  • 每个选中位置必须是 1，其余位置可以是 1 或 2
  • 数学上，从 n 个位置中选择奇数个的方案数是 2^(n-1)

因此答案就是 2^(max_depth-1) mod (10^9 + 7)。

代码实现

class Solution {
public:
    int assignEdgeWeights(vector<vector<int>>& edges) {
        const int MOD = 1000000007;
        int n = edges.size() + 1;
        
        // 建立邻接表
        vector<vector<int>> adj(n + 1);
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        
        // DFS 计算最大深度
        int maxDepth = 0;
        function<void(int, int, int)> dfs = [&](int node, int parent, int depth) {
            maxDepth = max(maxDepth, depth);
            for (int neighbor : adj[node]) {
                if (neighbor != parent) {
                    dfs(neighbor, node, depth + 1);
                }
            }
        };
        
        dfs(1, -1, 0);
        
        // 计算 2^(maxDepth-1) mod MOD
        if (maxDepth == 0) return 0;
        
        long long result = 1;
        for (int i = 0; i < maxDepth - 1; i++) {
            result = (result * 2) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def assignEdgeWeights(self, edges: List[List[int]]) -> int:
        MOD = 1000000007
        n = len(edges) + 1
        
        # 建立邻接表
        adj = [[] for _ in range(n + 1)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        
        # DFS 计算最大深度
        max_depth = 0
        
        def dfs(node, parent, depth):
            nonlocal max_depth
            max_depth = max(max_depth, depth)
            for neighbor in adj[node]:
                if neighbor != parent:
                    dfs(neighbor, node, depth + 1)
        
        dfs(1, -1, 0)
        
        # 计算 2^(max_depth-1) mod MOD
        if max_depth == 0:
            return 0
        
        return pow(2, max_depth - 1, MOD)

public class Solution {
    public int AssignEdgeWeights(int[][] edges) {
        const int MOD = 1000000007;
        int n = edges.Length + 1;
        
        // 建立邻接表
        var adj = new List<int>[n + 1];
        for (int i = 0; i <= n; i++) {
            adj[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
        }
        
        // DFS 计算最大深度
        int maxDepth = 0;
        
        void Dfs(int node, int parent, int depth) {
            maxDepth = Math.Max(maxDepth, depth);
            foreach (int neighbor in adj[node]) {
                if (neighbor != parent) {
                    Dfs(neighbor, node, depth + 1);
                }
            }
        }
        
        Dfs(1, -1, 0);
        
        // 计算 2^(maxDepth-1) mod MOD
        if (maxDepth == 0) return 0;
        
        long result = 1;
        for (int i = 0; i < maxDepth - 1; i++) {
            result = (result * 2) % MOD;
        }
        
        return (int)result;
    }
}

var assignEdgeWeights = function(edges) {
    const MOD = 1000000007;
    const n = edges.length + 1;
    
    // Build adjacency list
    const adj = Array.from({length: n + 1}, () => []);
    for (const [u, v] of edges) {
        adj[u].push(v);
        adj[v].push(u);
    }
    
    // Find maximum depth and path to deepest node
    let maxDepth = 0;
    let deepestNode = 1;
    const parent = new Array(n + 1).fill(-1);
    
    function dfs(node, par, depth) {
        parent[node] = par;
        if (depth > maxDepth) {
            maxDepth = depth;
            deepestNode = node;
        }
        
        for (const child of adj[node]) {
            if (child !== par) {
                dfs(child, node, depth + 1);
            }
        }
    }
    
    dfs(1, -1, 0);
    
    // Find path from root to deepest node
    const path = [];
    let curr = deepestNode;
    while (parent[curr] !== -1) {
        path.push(curr);
        curr = parent[curr];
    }
    path.push(1);
    path.reverse();
    
    // Number of edges in path
    const pathEdges = path.length - 1;
    
    if (pathEdges === 0) return 0;
    
    // Count ways to make sum odd
    // For k edges, we need odd number of edges with weight 1
    // Total ways = 2^k, ways to make even sum = 2^(k-1), ways to make odd sum = 2^(k-1)
    return Math.pow(2, pathEdges - 1) % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

时间复杂度：DFS 遍历所有节点一次，时间复杂度为 O(n)，计算幂次的时间复杂度为 O(max_depth)，总体为 O(n)。 空间复杂度：邻接表存储需要 O(n) 空间，DFS 递归栈最深为树的高度，最坏情况下为 O(n)。