3241. Time Taken to Mark All Nodes Hard

1/**
2 * [3241] Time Taken to Mark All Nodes
3 *
4 * There exists an undirected tree with n nodes numbered 0 to n - 1. You are given 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 in the tree.
5 * Initially, all nodes are unmarked. For each node i:
6 * 
7 * 	If i is odd, the node will get marked at time x if there is at least one node adjacent to it which was marked at time x - 1.
8 * 	If i is even, the node will get marked at time x if there is at least one node adjacent to it which was marked at time x - 2.
9 * 
10 * Return an array times where times[i] is the time when all nodes get marked in the tree, if you mark node i at time t = 0.
11 * Note that the answer for each times[i] is independent, i.e. when you mark node i all other nodes are unmarked.
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">edges = [[0,1],[0,2]]</span>
16 * Output: [2,4,3]
17 * Explanation:
18 * <img alt="" src="https://assets.leetcode.com/uploads/2024/06/01/screenshot-2024-06-02-122236.png" style="width: 500px; height: 241px;" />
19 * 
20 * 	For i = 0:
21 * 	
22 * 		Node 1 is marked at t = 1, and Node 2 at t = 2.
23 * 	
24 * 	
25 * 	For i = 1:
26 * 	
27 * 		Node 0 is marked at t = 2, and Node 2 at t = 4.
28 * 	
29 * 	
30 * 	For i = 2:
31 * 	
32 * 		Node 0 is marked at t = 2, and Node 1 at t = 3.
33 * 	
34 * 	
35 * </div>
36 * <strong class="example">Example 2:
37 * <div class="example-block">
38 * Input: <span class="example-io">edges = [[0,1]]</span>
39 * Output: [1,2]
40 * Explanation:
41 * <img alt="" src="https://assets.leetcode.com/uploads/2024/06/01/screenshot-2024-06-02-122249.png" style="width: 500px; height: 257px;" />
42 * 
43 * 	For i = 0:
44 * 	
45 * 		Node 1 is marked at t = 1.
46 * 	
47 * 	
48 * 	For i = 1:
49 * 	
50 * 		Node 0 is marked at t = 2.
51 * 	
52 * 	
53 * </div>
54 * <strong class="example">Example 3:
55 * <div class="example-block">
56 * Input: <span class="example-io">edges = </span>[[2,4],[0,1],[2,3],[0,2]]
57 * Output: [4,6,3,5,5]
58 * Explanation:
59 * <img alt="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-2024-06-03-210550.png" style="height: 266px; width: 500px;" />
60 * </div>
61 *  
62 * Constraints:
63 * 
64 * 	2 <= n <= 10^5
65 * 	edges.length == n - 1
66 * 	edges[i].length == 2
67 * 	0 <= edges[i][0], edges[i][1] <= n - 1
68 * 	The input is generated such that edges represents a valid tree.
69 * 
70 */
71pub struct Solution {}
72
73// problem: https://leetcode.com/problems/time-taken-to-mark-all-nodes/
74// discuss: https://leetcode.com/problems/time-taken-to-mark-all-nodes/discuss/?currentPage=1&orderBy=most_votes&query=
75
76// submission codes start here
77
78impl Solution {
79    pub fn time_taken(edges: Vec<Vec<i32>>) -> Vec<i32> {
80        vec![]
81    }
82}
83
84// submission codes end
85
86#[cfg(test)]
87mod tests {
88    use super::*;
89
90    #[test]
91    fn test_3241() {
92    }
93}
94