Maximize the number of target nodes after connecting trees ii

Tree Depth-First Search Breadth-First Search

73.2% acceptance

Feb 24, 2026

371

There exist two undirected trees with n and m nodes, labeled from [0, n - 1] and [0, m - 1], respectively. 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. 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. 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. 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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_target_nodes(edges1: Vec<Vec<i32>>, edges2: Vec<Vec<i32>>) -> Vec<i32> {
    // For tree with even-distance: 2-color the tree (bipartite)
    // Nodes at even distance from root = same color as root
    // When we connect node i from tree1 to some node j in tree2:
    // - even-dist nodes in tree1 from i = color1[i] (nodes same parity as i)
    // - through the connecting edge, distance parity flips
    // - from j in tree2, even-dist nodes = color2[j]
    // - but since edge i-j adds 1 edge, nodes even-dist from i via j are:
    //   nodes that are ODD dist from j in tree2
    // So answer[i] = count_even_from_i_in_tree1 + max(count_odd_from_j_in_tree2)
    // In a tree, 2-coloring gives two groups A and B
    // count_even_from_node = size of node's color group
    
    fn build_adj(edges: &Vec<Vec<i32>>, n: usize) -> Vec<Vec<usize>> {
      let mut adj = vec![vec![]; n];
      for e in edges {
        let (u, v) = (e[0] as usize, e[1] as usize);
        adj[u].push(v);
        adj[v].push(u);
      }
      adj
    }
    
    // BFS 2-coloring, return color array (0 or 1)
    fn color_tree(adj: &Vec<Vec<usize>>, n: usize) -> Vec<usize> {
      let mut color = vec![2usize; n];
      color[0] = 0;
      let mut queue = std::collections::VecDeque::new();
      queue.push_back(0usize);
      while let Some(u) = queue.pop_front() {
        for &v in &adj[u] {
          if color[v] == 2 {
            color[v] = 1 - color[u];
            queue.push_back(v);
          }
        }
      }
      color
    }
    
    let n = edges1.len() + 1;
    let m = edges2.len() + 1;
    
    let adj1 = build_adj(&edges1, n);
    let adj2 = build_adj(&edges2, m);
    
    let color1 = color_tree(&adj1, n);
    let color2 = color_tree(&adj2, m);
    
    // Count each color group
    let cnt1 = [
      color1.iter().filter(|&&c| c == 0).count() as i32,
      color1.iter().filter(|&&c| c == 1).count() as i32,
    ];
    let cnt2 = [
      color2.iter().filter(|&&c| c == 0).count() as i32,
      color2.iter().filter(|&&c| c == 1).count() as i32,
    ];
    
    // max odd-dist nodes from any node in tree2 = max(cnt2[1-j_color]) = max(cnt2[0], cnt2[1])
    // But: "odd dist from j" = nodes of color != color[j]
    // For each j: odd_from_j = cnt2[1 - color2[j]]
    // max over all j = max(cnt2[0], cnt2[1])  (since color2[j] can be 0 or 1)
    let best2 = cnt2[0].max(cnt2[1]);
    
    (0..n)
      .map(|i| cnt1[color1[i]] + best2)
      .collect()
  }
}