2025-06-21：连接两棵树后最大目标节点数目Ⅱ。用go语言，有两棵无向树，第一棵有 n 个节点，节点编号范围为 [0, n-1]，第二棵有 m 个节点，编号范围为 [0, m-1]。

输入给出两组边信息，分别是 edges1 和 edges2。edges1 长度为 n-1，每个元素 edges1[i] = [ai, bi] 表示第一棵树中 ai 和 bi 之间有一条边；edges2 长度为 m-1，edges2[i] = [ui, vi] 表示第二棵树中 ui 和 vi 之间有一条边。

定义两个节点 u 和 v 之间的路径长度为它们之间边的数量，如果这个路径长度是偶数，那么称 u 是 v 的“目标节点”。注意，一个节点本身一定是它自己的目标节点。

现在，对于第一棵树中的每个节点 i，考虑将该节点与第二棵树的某个节点连接一条边。你需要求出在添加这条边之后，第一棵树中节点 i 的目标节点数量的最大可能值。

每个计算是独立的，即每次添加的边运行完后要删除，不会影响下一次的计算。

最终返回一个长度为 n 的数组 answer，answer[i] 就是对应节点 i 在连接第二棵树的某个节点后，第一棵树中目标节点数量的最大值。

2 <= n, m <= 100000。

edges1.length == n - 1。

edges2.length == m - 1。

edges1[i].length == edges2[i].length == 2。

edges1[i] = [ai, bi]。

0 <= ai, bi < n。

edges2[i] = [ui, vi]。

0 <= ui, vi < m。

输入保证 edges1 和 edges2 都表示合法的树。

输入：edges1 = [[0,1],[0,2],[2,3],[2,4]], edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]]。

输出：[8,7,7,8,8]。

解释：

对于 i = 0 ，连接第一棵树中的节点 0 和第二棵树中的节点 0 。

对于 i = 1 ，连接第一棵树中的节点 1 和第二棵树中的节点 4 。

对于 i = 2 ，连接第一棵树中的节点 2 和第二棵树中的节点 7 。

对于 i = 3 ，连接第一棵树中的节点 3 和第二棵树中的节点 0 。

对于 i = 4 ，连接第一棵树中的节点 4 和第二棵树中的节点 4 。

题目来自力扣3373。

解决步骤

1. 分析目标节点的性质：

   • 目标节点与路径长度的奇偶性有关。路径长度为偶数时是目标节点。
   • 一个节点到自己的路径长度为 0（偶数），因此自己总是自己的目标节点。
   • 在两棵树中，可以通过染色（如黑白染色）来标记节点的奇偶性。例如，根节点为黑色（深度 0），其子节点为白色（深度 1），依此类推。这样，颜色相同的节点之间的路径长度为偶数，颜色不同的节点之间的路径长度为奇数。

2. 预处理第一棵树：

   • 对第一棵树进行黑白染色（例如，color1 数组，0 表示黑色，1 表示白色）。
   • 统计第一棵树中黑色和白色节点的数量（count1[0] 和 count1[1]）。
   • 对于第一棵树的每个节点 i，其目标节点数量为：
     • 如果 i 是黑色，则目标节点数量为 count1[0]（包括自己）。
     • 如果 i 是白色，则目标节点数量为 count1[1]（包括自己）。

3. 预处理第二棵树：

   • 对第二棵树进行黑白染色（color2 数组）。
   • 统计第二棵树中黑色和白色节点的数量（count2[0] 和 count2[1]）。
   • 第二棵树的最大目标节点数量为 max(count2[0], count2[1])。

4. 连接两棵树后的目标节点计算：

   • 当连接第一棵树的节点 i（颜色为 color1[i]）和第二棵树的某个节点时：
     • 如果连接的第二棵树节点的颜色与 color1[i] 相同，则第二棵树中所有与该颜色相同的节点都会成为 i 的目标节点（因为路径长度为偶数）。
     • 因此，第二棵树对 i 的目标节点数量的贡献是 max(count2[0], count2[1])。
   • 因此，对于第一棵树的每个节点 i，其最大目标节点数量为：
     • 第一棵树中与 i 同色的节点数量（count1[color1[i]]）。
     • 加上第二棵树中较多同色的节点数量（max(count2[0], count2[1])）。
     • 即 res[i] = count1[color1[i]] + max(count2[0], count2[1])。

5. 具体步骤：

   • 构建第一棵树的邻接表，进行 DFS 染色，并统计 count1。
   • 构建第二棵树的邻接表，进行 DFS 染色，并统计 count2。
   • 对于第一棵树的每个节点 i，计算 res[i]。

时间和空间复杂度

• 时间复杂度：
  • 构建邻接表和 DFS 遍历两棵树的时间均为 O(n + m)。
  • 计算 res 数组的时间为 O(n)。
  • 总时间复杂度为 O(n + m)。
• 空间复杂度：
  • 存储邻接表需要 O(n + m)。
  • 存储颜色数组需要 O(n + m)。
  • 其他临时空间为 O(1)。
  • 总空间复杂度为 O(n + m)。

Go完整代码如下：

.

package main

import (
	"fmt"
)

func maxTargetNodes(edges1 [][]int, edges2 [][]int) []int {
	var dfs func(node, parent, depth int, children [][]int, color []int) int
	dfs = func(node, parent, depth int, children [][]int, color []int) int {
		res := 1 - depth%2
		color[node] = depth % 2
		for _, child := range children[node] {
			if child == parent {
				continue
			}
			res += dfs(child, node, depth+1, children, color)
		}
		return res
	}

	build := func(edges [][]int, color []int) []int {
		n := len(edges) + 1
		children := make([][]int, n)
		for _, edge := range edges {
			u, v := edge[0], edge[1]
			children[u] = append(children[u], v)
			children[v] = append(children[v], u)
		}
		res := dfs(0, -1, 0, children, color)
		return []int{res, n - res}
	}

	n := len(edges1) + 1
	m := len(edges2) + 1
	color1 := make([]int, n)
	color2 := make([]int, m)
	count1 := build(edges1, color1)
	count2 := build(edges2, color2)
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = count1[color1[i]] + max(count2[0], count2[1])
	}
	return res
}

func main() {
	edges1 := [][]int{{0, 1}, {0, 2}, {2, 3}, {2, 4}}
	edges2 := [][]int{{0, 1}, {0, 2}, {0, 3}, {2, 7}, {1, 4}, {4, 5}, {4, 6}}
	fmt.Println(maxTargetNodes(edges1, edges2))
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

from typing import List

def max_target_nodes(edges1: List[List[int]], edges2: List[List[int]]) -> List[int]:
    def dfs(node: int, parent: int, depth: int, children: List[List[int]], color: List[int]) -> int:
        res = 1 - depth % 2
        color[node] = depth % 2
        for child in children[node]:
            if child == parent:
                continue
            res += dfs(child, node, depth + 1, children, color)
        return res

    def build(edges: List[List[int]], color: List[int]) -> List[int]:
        n = len(edges) + 1
        children = [[] for _ in range(n)]
        for u, v in edges:
            children[u].append(v)
            children[v].append(u)
        res = dfs(0, -1, 0, children, color)
        return [res, n - res]

    def max_val(a: int, b: int) -> int:
        return a if a > b else b

    n = len(edges1) + 1
    m = len(edges2) + 1
    color1 = [0] * n
    color2 = [0] * m
    count1 = build(edges1, color1)
    count2 = build(edges2, color2)
    res = [0] * n
    for i in range(n):
        res[i] = count1[color1[i]] + max_val(count2[0], count2[1])
    return res

if __name__ == '__main__':
    edges1 = [[0, 1], [0, 2], [2, 3], [2, 4]]
    edges2 = [[0, 1], [0, 2], [0, 3], [2, 7], [1, 4], [4, 5], [4, 6]]
    print(max_target_nodes(edges1, edges2))