3373. Maximize the Number of Target Nodes After Connecting Trees II Hard

1/**
2 * [3373] Maximize the Number of Target Nodes After Connecting Trees II
3 *
4 * There exist two undirected trees with n and m nodes, labeled from [0, n - 1] and [0, m - 1], respectively.
5 * You are given two 2D integer arrays edges1 and edges2 of lengths n - 1 and m - 1, respectively, where edges1[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the first tree and edges2[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the second tree.
6 * Node u is target to node v if the number of edges on the path from u to v is even. Note that a node is always target to itself.
7 * Return an array of n integers answer, where answer[i] is the maximum possible number of nodes that are target to node i of the first tree if you had to connect one node from the first tree to another node in the second tree.
8 * Note that queries are independent from each other. That is, for every query you will remove the added edge before proceeding to the next query.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">edges1 = [[0,1],[0,2],[2,3],[2,4]], edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]]</span>
13 * Output: <span class="example-io">[8,7,7,8,8]</span>
14 * Explanation:
15 * 
16 * 	For i = 0, connect node 0 from the first tree to node 0 from the second tree.
17 * 	For i = 1, connect node 1 from the first tree to node 4 from the second tree.
18 * 	For i = 2, connect node 2 from the first tree to node 7 from the second tree.
19 * 	For i = 3, connect node 3 from the first tree to node 0 from the second tree.
20 * 	For i = 4, connect node 4 from the first tree to node 4 from the second tree.
21 * <img alt="" src="https://assets.leetcode.com/uploads/2024/09/24/3982-1.png" style="width: 600px; height: 169px;" /></div>
22 * <strong class="example">Example 2:
23 * <div class="example-block">
24 * Input: <span class="example-io">edges1 = [[0,1],[0,2],[0,3],[0,4]], edges2 = [[0,1],[1,2],[2,3]]</span>
25 * Output: <span class="example-io">[3,6,6,6,6]</span>
26 * Explanation:
27 * For every i, connect node i of the first tree with any node of the second tree.
28 * <img alt="" src="https://assets.leetcode.com/uploads/2024/09/24/3928-2.png" style="height: 281px; width: 500px;" /></div>
29 *  
30 * Constraints:
31 * 
32 * 	2 <= n, m <= 10^5
33 * 	edges1.length == n - 1
34 * 	edges2.length == m - 1
35 * 	edges1[i].length == edges2[i].length == 2
36 * 	edges1[i] = [ai, bi]
37 * 	0 <= ai, bi < n
38 * 	edges2[i] = [ui, vi]
39 * 	0 <= ui, vi < m
40 * 	The input is generated such that edges1 and edges2 represent valid trees.
41 * 
42 */
43pub struct Solution {}
44
45// problem: https://leetcode.com/problems/maximize-the-number-of-target-nodes-after-connecting-trees-ii/
46// discuss: https://leetcode.com/problems/maximize-the-number-of-target-nodes-after-connecting-trees-ii/discuss/?currentPage=1&orderBy=most_votes&query=
47
48// submission codes start here
49
50impl Solution {
51    pub fn max_target_nodes(edges1: Vec<Vec<i32>>, edges2: Vec<Vec<i32>>) -> Vec<i32> {
52        vec![]
53    }
54}
55
56// submission codes end
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn test_3373() {
64    }
65}
66