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

福大大架构师每日一题

发布于 2025-06-21 10:50:31

1780

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 :=  - depth%
        color[node] = depth % 
        for _, child := range children[node] {
            if child == parent {
                continue
            }
            res += dfs(child, node, depth+, children, color)
        }
        return res
    }

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

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

func main() {
    edges1 := [][]int{{, }, {, }, {, }, {, }}
    edges2 := [][]int{{, }, {, }, {, }, {, }, {, }, {, }, {, }}
    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 =  - depth % 
        color[node] = depth % 
        for child in children[node]:
            if child == parent:
                continue
            res += dfs(child, node, depth + , children, color)
        return res

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

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

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

if __name__ == '__main__':
    edges1 = [[, ], [, ], [, ], [, ]]
    edges2 = [[, ], [, ], [, ], [, ], [, ], [, ], [, ]]
    print(max_target_nodes(edges1, edges2))