3373. 连接树后可到达目标节点的最大数目 II

Hard

题目描述

存在两个无向树，分别有 n 和 m 个节点，节点分别标记为 [0, n - 1] 和 [0, m - 1]。

给你两个二维整数数组 edges1 和 edges2，长度分别为 n - 1 和 m - 1，其中 edges1[i] = [ai, bi] 表示第一个树中节点 ai 和 bi 之间有一条边，edges2[i] = [ui, vi] 表示第二个树中节点 ui 和 vi 之间有一条边。

如果从节点 u 到节点 v 的路径上边的数量是偶数，那么节点 u 是节点 v 的目标节点。注意一个节点总是它自己的目标节点。

返回一个长度为 n 的整数数组 answer，其中 answer[i] 是在你必须将第一个树中的一个节点连接到第二个树中的另一个节点的情况下，第一个树中节点 i 可以到达的目标节点的最大可能数量。

注意查询是相互独立的。也就是说，对于每个查询，在进行下一个查询之前，你会移除添加的边。

示例 1：

输入：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]

示例 2：

输入：edges1 = [[0,1],[0,2],[0,3],[0,4]], edges2 = [[0,1],[1,2],[2,3]] 输出：[3,6,6,6,6]

提示：

2 <= n, m <= 10^5
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 代表有效的树。

解题思路

这道题的核心思路是理解"目标节点"的定义：从节点 u 到节点 v 的路径上边的数量是偶数时，v 是 u 的目标节点。

分析过程：

理解连接操作的影响：当我们连接两个树时，会形成一个新的连通图。对于第一个树中的节点 i，它能到达的目标节点包括：
- 第一个树中与 i 距离为偶数的节点
- 第二个树中与连接点距离为奇数的节点（因为连接边增加1的距离）
预计算策略：
- 对第一个树的每个节点，计算与它距离为偶数的节点数量
- 对第二个树的每个节点，计算与它距离为奇数的节点数量
- 找到第二个树中奇数距离节点数量的最大值
最优连接选择：为了最大化目标节点数量，我们应该选择第二个树中能提供最多奇数距离节点的连接点。
计算答案：对于第一个树的每个节点 i，答案就是它在第一个树中的偶数距离节点数量，加上第二个树中最大的奇数距离节点数量。

算法步骤：

构建两个树的邻接表
使用 DFS 计算第一个树中每个节点的偶数距离节点数量
使用 DFS 计算第二个树中每个节点的奇数距离节点数量
找到第二个树中奇数距离节点数量的最大值
组合结果得到答案

代码实现

class Solution {
public:
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
        int n = edges1.size() + 1;
        int m = edges2.size() + 1;
        
        // Build adjacency lists
        vector<vector<int>> adj1(n), adj2(m);
        for (auto& edge : edges1) {
            adj1[edge[0]].push_back(edge[1]);
            adj1[edge[1]].push_back(edge[0]);
        }
        for (auto& edge : edges2) {
            adj2[edge[0]].push_back(edge[1]);
            adj2[edge[1]].push_back(edge[0]);
        }
        
        // Calculate even distance nodes for tree1
        vector<int> even1(n);
        for (int i = 0; i < n; i++) {
            vector<bool> visited(n, false);
            even1[i] = dfsEven(adj1, i, 0, visited);
        }
        
        // Calculate odd distance nodes for tree2
        vector<int> odd2(m);
        for (int i = 0; i < m; i++) {
            vector<bool> visited(m, false);
            odd2[i] = dfsOdd(adj2, i, 0, visited);
        }
        
        // Find max odd distance nodes in tree2
        int maxOdd2 = *max_element(odd2.begin(), odd2.end());
        
        // Build answer
        vector<int> answer(n);
        for (int i = 0; i < n; i++) {
            answer[i] = even1[i] + maxOdd2;
        }
        
        return answer;
    }
    
private:
    int dfsEven(vector<vector<int>>& adj, int node, int dist, vector<bool>& visited) {
        visited[node] = true;
        int count = (dist % 2 == 0) ? 1 : 0;
        
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                count += dfsEven(adj, neighbor, dist + 1, visited);
            }
        }
        
        return count;
    }
    
    int dfsOdd(vector<vector<int>>& adj, int node, int dist, vector<bool>& visited) {
        visited[node] = true;
        int count = (dist % 2 == 1) ? 1 : 0;
        
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                count += dfsOdd(adj, neighbor, dist + 1, visited);
            }
        }
        
        return count;
    }
};

class Solution:
    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]]) -> List[int]:
        n = len(edges1) + 1
        m = len(edges2) + 1
        
        # Build adjacency lists
        adj1 = [[] for _ in range(n)]
        adj2 = [[] for _ in range(m)]
        
        for a, b in edges1:
            adj1[a].append(b)
            adj1[b].append(a)
            
        for u, v in edges2:
            adj2[u].append(v)
            adj2[v].append(u)
        
        # Calculate even distance nodes for tree1
        def dfs_even(adj, node, dist, visited):
            visited[node] = True
            count = 1 if dist % 2 == 0 else 0
            
            for neighbor in adj[node]:
                if not visited[neighbor]:
                    count += dfs_even(adj, neighbor, dist + 1, visited)
            
            return count
        
        # Calculate odd distance nodes for tree2
        def dfs_odd(adj, node, dist, visited):
            visited[node] = True
            count = 1 if dist % 2 == 1 else 0
            
            for neighbor in adj[node]:
                if not visited[neighbor]:
                    count += dfs_odd(adj, neighbor, dist + 1, visited)
            
            return count
        
        # Calculate even distance nodes for each node in tree1
        even1 = []
        for i in range(n):
            visited = [False] * n
            even1.append(dfs_even(adj1, i, 0, visited))
        
        # Calculate odd distance nodes for each node in tree2
        odd2 = []
        for i in range(m):
            visited = [False] * m
            odd2.append(dfs_odd(adj2, i, 0, visited))
        
        # Find max odd distance nodes in tree2
        max_odd2 = max(odd2)
        
        # Build answer
        answer = []
        for i in range(n):
            answer.append(even1[i] + max_odd2)
        
        return answer

public class Solution {
    public int[] MaxTargetNodes(int[][] edges1, int[][] edges2) {
        int n = edges1.Length + 1;
        int m = edges2.Length + 1;
        
        // Build adjacency lists
        List<int>[] adj1 = new List<int>[n];
        List<int>[] adj2 = new List<int>[m];
        
        for (int i = 0; i < n; i++) adj1[i] = new List<int>();
        for (int i = 0; i < m; i++) adj2[i] = new List<int>();
        
        foreach (var edge in edges1) {
            adj1[edge[0]].Add(edge[1]);
            adj1[edge[1]].Add(edge[0]);
        }
        
        foreach (var edge in edges2) {
            adj2[edge[0]].Add(edge[1]);
            adj2[edge[1]].Add(edge[0]);
        }
        
        // Calculate even distance nodes for tree1
        int[] even1 = new int[n];
        for (int i = 0; i < n; i++) {
            bool[] visited = new bool[n];
            even1[i] = DfsEven(adj1, i, 0, visited);
        }
        
        // Calculate odd distance nodes for tree2
        int[] odd2 = new int[m];
        for (int i = 0; i < m; i++) {
            bool[] visited = new bool[m];
            odd2[i] = DfsOdd(adj2, i, 0, visited);
        }
        
        // Find max odd distance nodes in tree2
        int maxOdd2 = odd2.Max();
        
        // Build answer
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            answer[i] = even1[i] + maxOdd2;
        }
        
        return answer;
    }
    
    private int DfsEven(List<int>[] adj, int node, int dist, bool[] visited) {
        visited[node] = true;
        int count = (dist % 2 == 0) ? 1 : 0;
        
        foreach (int neighbor in adj[node]) {
            if (!visited[neighbor]) {
                count += DfsEven(adj, neighbor, dist + 1, visited);
            }
        }
        
        return count;
    }
    
    private int DfsOdd(List<int>[] adj, int node, int dist, bool[] visited) {
        visited[node] = true;
        int count = (dist % 2 == 1) ? 1 : 0;
        
        foreach (int neighbor in adj[node]) {
            if (!visited[neighbor]) {
                count += DfsOdd(adj, neighbor, dist + 1, visited);
            }
        }
        
        return count;
    }
}

var maxTargetNodes = function(edges1, edges2) {
    function buildGraph(edges) {
        const graph = {};
        for (const [u, v] of edges) {
            if (!graph[u]) graph[u] = [];
            if (!graph[v]) graph[v] = [];
            graph[u].push(v);
            graph[v].push(u);
        }
        return graph;
    }
    
    function bipartiteColor(graph, n) {
        const color = new Array(n).fill(-1);
        const groups = [[], []];
        
        function dfs(node, c) {
            color[node] = c;
            groups[c].push(node);
            for (const neighbor of graph[node] || []) {
                if (color[neighbor] === -1) {
                    dfs(neighbor, 1 - c);
                }
            }
        }
        
        for (let i = 0; i < n; i++) {
            if (color[i] === -1) {
                dfs(i, 0);
            }
        }
        
        return groups;
    }
    
    const n = edges1.length + 1;
    const m = edges2.length + 1;
    
    const graph1 = buildGraph(edges1);
    const graph2 = buildGraph(edges2);
    
    const groups1 = bipartiteColor(graph1, n);
    const groups2 = bipartiteColor(graph2, m);
    
    const maxFromTree2 = Math.max(groups2[0].length, groups2[1].length);
    
    const result = new Array(n);
    
    for (let i = 0; i < n; i++) {
        const sameParityCount1 = groups1[0].includes(i) ? groups1[0].length : groups1[1].length;
        result[i] = sameParityCount1 + maxFromTree2;
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度
时间复杂度	O(n² + m²)
空间复杂度	O(n + m)

其中 n 和 m 分别是两个树的节点数。时间复杂度主要来自对每个节点执行 DFS 遍历整个树。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目