3559. Number of Ways to Assign Edge Weights II Hard

1/**
2 * [3559] Number of Ways to Assign Edge Weights II
3 *
4 * There is an undirected tree with n nodes labeled from 1 to n, rooted at node 1. The tree is represented by a 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi.
5 * Initially, all edges have a weight of 0. You must assign each edge a weight of either 1 or 2.
6 * The cost of a path between any two nodes u and v is the total weight of all edges in the path connecting them.
7 * You are given a 2D integer array queries. For each queries[i] = [ui, vi], determine the number of ways to assign weights to edges in the path such that the cost of the path between ui and vi is odd.
8 * Return an array answer, where answer[i] is the number of valid assignments for queries[i].
9 * Since the answer may be large, apply modulo 10^9 + 7 to each answer[i].
10 * Note: For each query, disregard all edges not in the path between node ui and vi.
11 *  
12 * <strong class="example">Example 1:
13 * <div class="example-block">
14 * <img src="https://assets.leetcode.com/uploads/2025/03/23/screenshot-2025-03-24-at-060006.png" style="height: 72px; width: 200px;" />
15 * Input: <span class="example-io">edges = [[1,2]], queries = [[1,1],[1,2]]</span>
16 * Output: <span class="example-io">[0,1]</span>
17 * Explanation:
18 * 
19 * 	Query [1,1]: The path from Node 1 to itself consists of no edges, so the cost is 0. Thus, the number of valid assignments is 0.
20 * 	Query [1,2]: The path from Node 1 to Node 2 consists of one edge (1 &rarr; 2). Assigning weight 1 makes the cost odd, while 2 makes it even. Thus, the number of valid assignments is 1.
21 * </div>
22 * <strong class="example">Example 2:
23 * <img src="https://assets.leetcode.com/uploads/2025/03/23/screenshot-2025-03-24-at-055820.png" style="height: 207px; width: 220px;" />
24 * <div class="example-block">
25 * Input: <span class="example-io">edges = [[1,2],[1,3],[3,4],[3,5]], queries = [[1,4],[3,4],[2,5]]</span>
26 * Output: <span class="example-io">[2,1,4]</span>
27 * Explanation:
28 * 
29 * 	Query [1,4]: The path from Node 1 to Node 4 consists of two edges (1 &rarr; 3 and 3 &rarr; 4). Assigning weights (1,2) or (2,1) results in an odd cost. Thus, the number of valid assignments is 2.
30 * 	Query [3,4]: The path from Node 3 to Node 4 consists of one edge (3 &rarr; 4). Assigning weight 1 makes the cost odd, while 2 makes it even. Thus, the number of valid assignments is 1.
31 * 	Query [2,5]: The path from Node 2 to Node 5 consists of three edges (2 &rarr; 1, 1 &rarr; 3, and 3 &rarr; 5). Assigning (1,2,2), (2,1,2), (2,2,1), or (1,1,1) makes the cost odd. Thus, the number of valid assignments is 4.
32 * </div>
33 *  
34 * Constraints:
35 * 
36 * 	2 <= n <= 10^5
37 * 	edges.length == n - 1
38 * 	edges[i] == [ui, vi]
39 * 	1 <= queries.length <= 10^5
40 * 	queries[i] == [ui, vi]
41 * 	1 <= ui, vi <= n
42 * 	edges represents a valid tree.
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/number-of-ways-to-assign-edge-weights-ii/
48// discuss: https://leetcode.com/problems/number-of-ways-to-assign-edge-weights-ii/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn assign_edge_weights(edges: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
54        vec![]
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_3559() {
66    }
67}
68