Solutions CS101

Appearance

第 157 场双周赛-20250524 ​

https://leetcode.cn/contest/biweekly-contest-157/

中国时间：2025-05-24 22:30, 1 小时 30 分

M3556.最大质数子字符串之和 ​

sliding window, https://leetcode.cn/problems/sum-of-largest-prime-substrings/description/

M3557.不相交子字符串的最大数量 ​

greedy, https://leetcode.cn/problems/find-maximum-number-of-non-intersecting-substrings/description/

M3558.给边赋权值的方案数 I ​

bfs, math, https://leetcode.cn/problems/number-of-ways-to-assign-edge-weights-i/description/

T3559.给边赋权值的方案数 II ​

https://leetcode.cn/problems/number-of-ways-to-assign-edge-weights-ii/

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

一开始，所有边的权重为 0。你可以将每条边的权重设为 1 或 2。

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

给定一个二维整数数组 queries。对于每个 queries[i] = [ui, vi]，计算从节点 ui 到 vi 的路径中，使得路径代价为 奇数 的权重分配方式数量。

返回一个数组 answer，其中 answer[i] 表示第 i 个查询的合法赋值方式数量。

由于答案可能很大，请对每个 answer[i] 取模 109 + 7。

注意： 对于每个查询，仅考虑 ui 到 vi 路径上的边，忽略其他边。

示例 1：

img

输入： edges = [[1,2]], queries = [[1,1],[1,2]]

输出： [0,1]

解释：

  • 查询 [1,1]：节点 1 到自身没有边，代价为 0，因此合法赋值方式为 0。
  • 查询 [1,2]：从节点 1 到节点 2 的路径有一条边（1 → 2）。将权重设为 1 时代价为奇数，设为 2 时为偶数，因此合法赋值方式为 1。

示例 2：

img

输入： edges = [[1,2],[1,3],[3,4],[3,5]], queries = [[1,4],[3,4],[2,5]]

输出： [2,1,4]

解释：

  • 查询 [1,4]：路径为两条边（1 → 3 和 3 → 4），(1,2) 或 (2,1) 的组合会使代价为奇数，共 2 种。
  • 查询 [3,4]：路径为一条边（3 → 4），仅权重为 1 时代价为奇数，共 1 种。
  • 查询 [2,5]：路径为三条边（2 → 1 → 3 → 5），组合 (1,2,2)、(2,1,2)、(2,2,1)、(1,1,1) 均为奇数代价，共 4 种。

提示：

  • 2 <= n <= 10^5
  • edges.length == n - 1
  • edges[i] == [ui, vi]
  • 1 <= queries.length <= 10^5
  • queries[i] == [ui, vi]
  • 1 <= ui, vi <= n
  • edges 表示一棵合法的树。
python
class Solution:
    def assignEdgeWeights(self, edges: List[List[int]], queries: List[List[int]]) -> List[int]: