3558. Number of Ways to Assign Edge Weights I Medium

1/**
2 * [3558] Number of Ways to Assign Edge Weights I
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 * Select any one node x at the maximum depth. Return the number of ways to assign edge weights in the path from node 1 to x such that its total cost is odd.
8 * Since the answer may be large, return it modulo 10^9 + 7.
9 * Note: Ignore all edges not in the path from node 1 to x.
10 *  
11 * <strong class="example">Example 1:
12 * <img src="https://assets.leetcode.com/uploads/2025/03/23/screenshot-2025-03-24-at-060006.png" style="width: 200px; height: 72px;" />
13 * <div class="example-block">
14 * Input: <span class="example-io">edges = [[1,2]]</span>
15 * Output: <span class="example-io">1</span>
16 * Explanation:
17 * 
18 * 	The path from Node 1 to Node 2 consists of one edge (1 &rarr; 2).
19 * 	Assigning weight 1 makes the cost odd, while 2 makes it even. Thus, the number of valid assignments is 1.
20 * </div>
21 * <strong class="example">Example 2:
22 * <img src="https://assets.leetcode.com/uploads/2025/03/23/screenshot-2025-03-24-at-055820.png" style="width: 220px; height: 207px;" />
23 * <div class="example-block">
24 * Input: <span class="example-io">edges = [[1,2],[1,3],[3,4],[3,5]]</span>
25 * Output: <span class="example-io">2</span>
26 * Explanation:
27 * 
28 * 	The maximum depth is 2, with nodes 4 and 5 at the same depth. Either node can be selected for processing.
29 * 	For example, the path from Node 1 to Node 4 consists of two edges (1 &rarr; 3 and 3 &rarr; 4).
30 * 	Assigning weights (1,2) or (2,1) results in an odd cost. Thus, the number of valid assignments is 2.
31 * </div>
32 *  
33 * Constraints:
34 * 
35 * 	2 <= n <= 10^5
36 * 	edges.length == n - 1
37 * 	edges[i] == [ui, vi]
38 * 	1 <= ui, vi <= n
39 * 	edges represents a valid tree.
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/number-of-ways-to-assign-edge-weights-i/
45// discuss: https://leetcode.com/problems/number-of-ways-to-assign-edge-weights-i/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn assign_edge_weights(edges: Vec<Vec<i32>>) -> i32 {
51        0
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_3558() {
63    }
64}
65