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

根据题目要求对于树中任意两个节点 u 和 v路径长度为 d边数使路径总代价为奇数的赋值方案数为 2^(d-1)。因此核心是快速求树上两点距离。Python3 实现pythonclass Solution:MOD 10**9 7def assignEdgeWeights(self, edges: List[List[int]], queries: List[List[int]]) - List[int]:n len(edges) 1# 1. 建图无向树graph [[] for _ in range(n)]for u, v in edges:u - 1v - 1graph[u].append(v)graph[v].append(u)# 2. 预处理深度和倍增表LOG (n).bit_length() # ceil(log2(n)) 1depth [0] * nup [[0] * LOG for _ in range(n)]# DFS 构建倍增表stack [(0, -1)] # (node, parent)order [] # 后序遍历顺序parent [-1] * nwhile stack:node, par stack.pop()parent[node] parorder.append(node)for nei in graph[node]:if nei ! par:depth[nei] depth[node] 1stack.append((nei, node))# 初始化 up[0]for i in range(n):up[i][0] parent[i] if parent[i] ! -1 else i# 构建倍增表for j in range(1, LOG):for i in range(n):up[i][j] up[up[i][j-1]][j-1]# 3. 预处理 2 的幂次pow2 [1] * (n 1)for i in range(1, n 1):pow2[i] (pow2[i-1] * 2) % self.MOD# 4. 处理每个查询ans []for u, v in queries:u - 1v - 1lca self._find_lca(u, v, depth, up, LOG)dist depth[u] depth[v] - 2 * depth[lca]ans.append(0 if dist 0 else pow2[dist - 1])return ansdef _find_lca(self, u, v, depth, up, LOG):求 LCA# 确保 u 是较浅的节点if depth[u] depth[v]:u, v v, u# 将 v 提升到与 u 同深度diff depth[v] - depth[u]for j in range(LOG):if (diff j) 1:v up[v][j]if u v:return u# 同时提升for j in range(LOG - 1, -1, -1):if up[u][j] ! up[v][j]:u up[u][j]v up[v][j]return up[u][0]优化版本使用 BFS 替代 DFSpythonfrom collections import dequeclass Solution:MOD 10**9 7def assignEdgeWeights(self, edges: List[List[int]], queries: List[List[int]]) - List[int]:n len(edges) 1# 建图graph [[] for _ in range(n)]for u, v in edges:u, v u - 1, v - 1graph[u].append(v)graph[v].append(u)# BFS 预处理深度和父节点LOG (n).bit_length()depth [0] * nup [[0] * LOG for _ in range(n)]q deque([0])visited [False] * nvisited[0] Trueparent [-1] * nwhile q:node q.popleft()for nei in graph[node]:if not visited[nei]:visited[nei] Truedepth[nei] depth[node] 1parent[nei] nodeq.append(nei)# 初始化倍增表for i in range(n):up[i][0] parent[i] if parent[i] ! -1 else ifor j in range(1, LOG):for i in range(n):up[i][j] up[up[i][j-1]][j-1]# 预处理 2 的幂pow2 [1] * (n 1)for i in range(1, n 1):pow2[i] (pow2[i-1] * 2) % self.MOD# 处理查询def lca(u, v):if depth[u] depth[v]:u, v v, u# 提升 vdiff depth[v] - depth[u]j 0while diff:if diff 1:v up[v][j]diff 1j 1if u v:return ufor j in range(LOG - 1, -1, -1):if up[u][j] ! up[v][j]:u up[u][j]v up[v][j]return up[u][0]ans []for u, v in queries:u, v u - 1, v - 1ancestor lca(u, v)dist depth[u] depth[v] - 2 * depth[ancestor]ans.append(0 if dist 0 else pow2[dist - 1])return ans更简洁的实现使用递归 DFSpythonclass Solution:MOD 10**9 7def assignEdgeWeights(self, edges: List[List[int]], queries: List[List[int]]) - List[int]:n len(edges) 1# 建图g [[] for _ in range(n)]for u, v in edges:u, v u - 1, v - 1g[u].append(v)g[v].append(u)# DFS 预处理LOG n.bit_length()depth [0] * nup [[0] * LOG for _ in range(n)]def dfs(node, parent):up[node][0] parent if parent ! -1 else nodefor j in range(1, LOG):up[node][j] up[up[node][j-1]][j-1]for nei in g[node]:if nei ! parent:depth[nei] depth[node] 1dfs(nei, node)dfs(0, -1)# LCA 函数def get_lca(u, v):if depth[u] depth[v]:u, v v, u# 提升 vdiff depth[v] - depth[u]j 0while diff:if diff 1:v up[v][j]diff 1j 1if u v:return ufor j in range(LOG - 1, -1, -1):if up[u][j] ! up[v][j]:u up[u][j]v up[v][j]return up[u][0]# 预处理 2 的幂pow2 [1] * (n 1)for i in range(1, n 1):pow2[i] (pow2[i-1] * 2) % self.MOD# 处理查询return [0 if dist 0 else pow2[dist - 1]for u, v in queriesfor dist in [depth[u-1] depth[v-1] - 2 * depth[get_lca(u-1, v-1)]]]复杂度分析操作 时间复杂度 空间复杂度预处理 O(n log n) O(n log n)单次查询 O(log n) O(1)总体 O((n q) log n) O(n log n)其中 n 为节点数q 为查询数。核心公式证明对于路径长度为 d 的路径每条边可选权重 1 或 2路径总代价为奇数等价于· 路径上有奇数条边权重为 1其余为 2· 从 d 条边中选择奇数条赋值为 1 的方案数组合数公式C(d,1) C(d,3) C(d,5) ... 2^(d-1)因此答案为 2^(d-1)。当 d 0 时即 u v方案数为 0。