3372. Maximize the Number of Target Nodes After Connecting Trees I Medium

1/**
2 * [3372] Maximize the Number of Target Nodes After Connecting Trees I
3 *
4 * There exist two undirected trees with n and m nodes, with distinct labels in ranges [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. You are also given an integer k.
6 * Node u is target to node v if the number of edges on the path from u to v is less than or equal to k. 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 target to node i of the first tree if you have 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]], k = 2</span>
13 * Output: <span class="example-io">[9,7,9,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 0 from the second tree.
18 * 	For i = 2, connect node 2 from the first tree to node 4 from the second tree.
19 * 	For i = 3, connect node 3 from the first tree to node 4 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]], k = 1</span>
25 * Output: <span class="example-io">[6,3,3,3,3]</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 <= 1000
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 * 	0 <= k <= 1000
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/maximize-the-number-of-target-nodes-after-connecting-trees-i/
47// discuss: https://leetcode.com/problems/maximize-the-number-of-target-nodes-after-connecting-trees-i/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn max_target_nodes(edges1: Vec<Vec<i32>>, edges2: Vec<Vec<i32>>, k: i32) -> Vec<i32> {
53        vec![]
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_3372() {
65    }
66}
67