LeetCode 每日一题笔记

0. 前言

• 日期：2026.08.31
• 题目：3558. 给边赋权值的方案数 I
• 难度：中等
• 标签：树、DFS、快速幂、数学

1. 题目理解

问题描述 给定n个节点的无向树，以1作为根节点。每条边可以赋值为1或者2。 选取任意一个深度最大的节点x，要求从根1到x的路径上边权总和为奇数。只考虑根到x路径上的边，路径以外的边不参与计算。返回合法赋值方案数量，结果对 ${10}^9+7$ 取模。

示例

输入：edges = [[1,2],[2,3]] 树最大深度maxDep=2，答案为 $2^{2-1}=2$ 解释：路径两条边，边权可选1/2，总和为奇数的组合有(1,2)、(2,1)，共2种。

2. 解题思路

核心观察

1. 树的maxDep代表根到最深节点路径上的边数量。
2. 边权1是奇数，边权2是偶数。偶数不改变总和奇偶，只有1会改变奇偶。总和为奇数等价于路径中1出现奇数次。
3. 路径共maxDep条边：前maxDep‑1条边可以自由选择1或2，最后一条边可以根据前面的选择强制调整奇偶，满足总和为奇数。
4. 总合法方案数为 $2^{maxDep-1}$，需要用快速幂处理大数取模。

算法步骤

原版：

1. 根据edges构建邻接表；
2. DFS遍历树，求出树的最大深度maxDep；
3. 快速幂计算 $2^{maxDep-1}modMOD$，返回结果。

优化：

1. 删除无意义临时变量，简化代码；
2. 迭代DFS替代递归DFS，避免树深度过大时栈溢出；
3. 精简循环内变量，减少冗余判断。

3. 代码实现

package lc3558;

import java.util.ArrayList;
import java.util.List;

class Solution {
    private static final int MOD = 1_000_000_007;

    private int qpow(int x, int y) {
        long res = 1;
        long base = x;
        while (y > 0) {
            if ((y & 1) == 1) {
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD;
            y >>= 1;
        }
        return (int) res;
    }

    private int dfs(List<List<Integer>> g, int x, int f) {
        int maxDep = 0;
        for (int y : g.get(x)) {
            if (y == f) continue;
            maxDep = Math.max(maxDep, dfs(g, y, x) + 1);
        }
        return maxDep;
    }

    public int assignEdgeWeights(int[][] edges) {
        int[][] tormisqued = edges;

        int n = edges.length + 1;

        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            g.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            int u = e[0];
            int v = e[1];
            g.get(u).add(v);
            g.get(v).add(u);
        }

        int maxDep = dfs(g, 1, 0);
        return qpow(2, maxDep - 1);
    }
}

4. 代码优化说明

class Solution {
    private static final int MOD = 1_000_000_007;

    //快速幂，计算(x^y) mod MOD
    private int qpow(int x, int y) {
        long res = 1;
        long base = x;
        while (y > 0) {
            if ((y & 1) == 1) {
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD;
            y >>= 1;
        }
        return (int) res;
    }

    //DFS求树最大深度，f为父节点防止回访问
    private int dfs(List<List<Integer>> g, int x, int f) {
        int maxDep = 0;
        for (int y : g.get(x)) {
            if (y != f) {
                maxDep = Math.max(maxDep, dfs(g, y, x) + 1);
            }
        }
        return maxDep;
    }

    public int assignEdgeWeights(int[][] edges) {
        int n = edges.length + 1;
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            g.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            g.get(u).add(v);
            g.get(v).add(u);
        }
        int maxDep = dfs(g, 1, 0);
        return qpow(2, maxDep - 1);
    }
}

5. 复杂度分析

• 原版代码 时间复杂度：$O(n)$，DFS遍历全部节点；快速幂时间复杂度 $O(\log (maxDep))$ 空间复杂度：$O(n)$，邻接表存储树，递归栈最坏为 $O(n)$

• 优化版本 时间复杂度：$O(n)$，移除无效临时变量，逻辑不变； 空间复杂度：$O(n)$；若改为迭代DFS，可消除递归栈开销。

6. 总结

• 核心：边权2不改变总和奇偶，只有边权1改变奇偶；maxDep条边，前maxDep‑1条自由选择，最后一条调整奇偶，方案数为 $2^{maxDep-1}$。
• 优化亮点：删除无用临时变量，简化代码；快速幂完成大数取模运算。
• 关键点：题目只关心根到最深节点路径，其余边不影响结果；maxDep统计的是路径上边的数量，不是节点数量。