DeepSeek LeetCode 3559. 给边赋权值的方案数 II Java实现

根据题目要求对于树中任意两个节点 u 和 v路径长度为 d边数使路径总代价为奇数的赋值方案数为 2^(d-1)。因此核心问题转化为快速求树上两点距离。以下是 Java 实现使用二进制提升Binary Lifting 求 LCA预处理 O(n log n)单次查询 O(log n)javaclass Solution {private static final int MOD 1_000_000_007;private ListListInteger graph;private int[] depth;private int[][] up;public int[] assignEdgeWeights(int[][] edges, int[][] queries) {int n edges.length 1;// 1. 建图graph new ArrayList();for (int i 0; i n; i) graph.add(new ArrayList());for (int[] e : edges) {int u e[0] - 1, v e[1] - 1;graph.get(u).add(v);graph.get(v).add(u);}// 2. 预处理深度 倍增表int LOG 32 - Integer.numberOfLeadingZeros(n); // ceil(log2(n)) 1depth new int[n];up new int[n][LOG];dfs(0, -1);// 3. 预处理 2 的幂次int[] pow2 new int[n 1];pow2[0] 1;for (int i 1; i n; i) {pow2[i] (int)((long)pow2[i - 1] * 2 % MOD);}// 4. 处理每个查询int q queries.length;int[] ans new int[q];for (int i 0; i q; i) {int u queries[i][0] - 1, v queries[i][1] - 1;int lca findLca(u, v);int dist depth[u] depth[v] - 2 * depth[lca];ans[i] dist 0 ? 0 : pow2[dist - 1];}return ans;}// DFS 构建深度和倍增表private void dfs(int node, int parent) {up[node][0] parent -1 ? node : parent;for (int j 1; j up[0].length; j) {up[node][j] up[up[node][j - 1]][j - 1];}for (int nei : graph.get(node)) {if (nei parent) continue;depth[nei] depth[node] 1;dfs(nei, node);}}// 将节点向上提升 diff 步private int lift(int node, int diff) {for (int j 0; diff 0; j, diff 1) {if ((diff 1) 1) node up[node][j];}return node;}// 求 LCAprivate int findLca(int u, int v) {if (depth[u] depth[v]) {int tmp u; u v; v tmp;}v lift(v, depth[v] - depth[u]);if (u v) return u;for (int j up[0].length - 1; j 0; j--) {if (up[u][j] ! up[v][j]) {u up[u][j];v up[v][j];}}return up[u][0];}}复杂度分析· 时间复杂度预处理 O(n log n)每个查询 O(log n)· 空间复杂度O(n log n)核心思路补充为什么答案是 2^(d-1)路径上 d 条边每条可选 1 或 2。要让总和为奇数等价于从 d 条边中选奇数条赋值为 1其余为 2。d 个元素中选奇数个的组合数之和 2^(d-1)。