Maximize the Number of Target Nodes After Connecting Trees II solution and explanation

/* Python code for DFS solution */

/* Java code for DFS solution */

/* C++ code for DFS solution */

/* JavaScript code for DFS solution */

/* C code for DFS solution */

/* C# code for DFS solution */

/* Python code for DP solution */

/* Java code for DP solution */

/* C++ code for DP solution */

/* JavaScript code for DP solution */

/* C code for DP solution */

/* C# code for DP solution */

function maxTargetNodes(edges1: number[][], edges2: number[][]): number[] {
    const g1 = build(edges1);
    const g2 = build(edges2);
    const [n, m] = [g1.length, g2.length];
    const c1 = Array(n).fill(0);
    const c2 = Array(m).fill(0);
    const cnt1 = [0, 0];
    const cnt2 = [0, 0];

    dfs(g2, 0, -1, c2, 0, cnt2);
    dfs(g1, 0, -1, c1, 0, cnt1);

    const t = Math.max(...cnt2);
    const ans = Array(n);
    for (let i = 0; i < n; i++) {
        ans[i] = t + cnt1[c1[i]];
    }
    return ans;
}

function build(edges: number[][]): number[][] {
    const n = edges.length + 1;
    const g: number[][] = Array.from({ length: n }, () => []);
    for (const [a, b] of edges) {
        g[a].push(b);
        g[b].push(a);
    }
    return g;
}

function dfs(g: number[][], a: number, fa: number, c: number[], d: number, cnt: number[]): void {
    c[a] = d;
    cnt[d]++;
    for (const b of g[a]) {
        if (b !== fa) {
            dfs(g, b, a, c, d ^ 1, cnt);
        }
    }
}

func maxTargetNodes(edges1 [][]int, edges2 [][]int) []int {
    g1 := build(edges1)
    g2 := build(edges2)
    n, m := len(g1), len(g2)
    c1 := make([]int, n)
    c2 := make([]int, m)
    cnt1 := make([]int, 2)
    cnt2 := make([]int, 2)

    dfs(g2, 0, -1, c2, 0, cnt2)
    dfs(g1, 0, -1, c1, 0, cnt1)

    t := max(cnt2[0], cnt2[1])
    ans := make([]int, n)
    for i := 0; i < n; i++ {
        ans[i] = t + cnt1[c1[i]]
    }
    return ans
}

func build(edges [][]int) [][]int {
    n := len(edges) + 1
    g := make([][]int, n)
    for _, e := range edges {
        a, b := e[0], e[1]
        g[a] = append(g[a], b)
        g[b] = append(g[b], a)
    }
    return g
}

func dfs(g [][]int, a, fa int, c []int, d int, cnt []int) {
    c[a] = d
    cnt[d]++
    for _, b := range g[a] {
        if b != fa {
            dfs(g, b, a, c, d^1, cnt)
        }
    }
}

impl Solution {
    pub fn max_target_nodes(edges1: Vec<Vec<i32>>, edges2: Vec<Vec<i32>>) -> Vec<i32> {
        fn build(edges: &Vec<Vec<i32>>) -> Vec<Vec<i32>> {
            let n = edges.len() + 1;
            let mut g = vec![vec![]; n];
            for e in edges {
                let a = e[0] as usize;
                let b = e[1] as usize;
                g[a].push(b as i32);
                g[b].push(a as i32);
            }
            g
        }

        fn dfs(g: &Vec<Vec<i32>>, a: usize, fa: i32, c: &mut Vec<i32>, d: i32, cnt: &mut Vec<i32>) {
            c[a] = d;
            cnt[d as usize] += 1;
            for &b in &g[a] {
                if b != fa {
                    dfs(g, b as usize, a as i32, c, d ^ 1, cnt);
                }
            }
        }

        let g1 = build(&edges1);
        let g2 = build(&edges2);
        let n = g1.len();
        let m = g2.len();

        let mut c1 = vec![0; n];
        let mut c2 = vec![0; m];
        let mut cnt1 = vec![0; 2];
        let mut cnt2 = vec![0; 2];

        dfs(&g2, 0, -1, &mut c2, 0, &mut cnt2);
        dfs(&g1, 0, -1, &mut c1, 0, &mut cnt1);

        let t = cnt2[0].max(cnt2[1]);
        let mut ans = vec![0; n];
        for i in 0..n {
            ans[i] = t + cnt1[c1[i] as usize];
        }

        ans
    }
}