1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    // Graph adjacency list
7    private List<Integer>[] graph;
8    // Maximum diameter found
9    private int maxDiameter;
10    // Furthest node found
11    private int furthestNode;
12
13    /**
14     * Calculates the minimum diameter after merging two trees.
15     * 
16     * @param edges1 The edges of the first tree.
17     * @param edges2 The edges of the second tree.
18     * @return The minimum diameter after merging the trees.
19     */
20    public int minimumDiameterAfterMerge(int[][] edges1, int[][] edges2) {
21        int diameter1 = treeDiameter(edges1);
22        int diameter2 = treeDiameter(edges2);
23      
24        // Calculate the effective diameter after potential merging
25        int mergedDiameter = (diameter1 + 1) / 2 + (diameter2 + 1) / 2 + 1;
26      
27        // Return the maximum diameter
28        return Math.max(Math.max(diameter1, diameter2), mergedDiameter);
29    }
30
31    /**
32     * Finds the diameter of a tree.
33     * 
34     * @param edges The edges representing the tree.
35     * @return The diameter of the tree.
36     */
37    public int treeDiameter(int[][] edges) {
38        int n = edges.length + 1; // Number of nodes
39
40        // Initialize graph as an adjacency list
41        graph = new List[n];
42        Arrays.setAll(graph, k -> new ArrayList<>());
43
44        // Reset maximum diameter and furthest node
45        maxDiameter = 0;
46        furthestNode = 0;
47
48        // Construct the graph
49        for (int[] edge : edges) {
50            int node1 = edge[0];
51            int node2 = edge[1];
52            graph[node1].add(node2);
53            graph[node2].add(node1);
54        }
55
56        // Perform DFS to find the furthest node from an arbitrary start (here, node 0)
57        dfs(0, -1, 0);
58        // Perform DFS again from the furthest node found to determine the tree's diameter
59        dfs(furthestNode, -1, 0);
60
61        // Return the maximum diameter found
62        return maxDiameter;
63    }
64
65    /**
66     * Depth-First Search to compute the furthest distance from the current node.
67     * 
68     * @param currentNode The current node in DFS.
69     * @param parent The parent node in DFS.
70     * @param currentLength The distance from the starting node.
71     */
72    private void dfs(int currentNode, int parent, int currentLength) {
73        for (int neighbor : graph[currentNode]) {
74            if (neighbor != parent) {
75                dfs(neighbor, currentNode, currentLength + 1);
76            }
77        }
78
79        // Update the maximum distance and furthest node if a longer path is found
80        if (maxDiameter < currentLength) {
81            maxDiameter = currentLength;
82            furthestNode = currentNode;
83        }
84    }
85}
86

1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7    int minimumDiameterAfterMerge(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
8        // Calculate the diameter of each tree
9        int d1 = treeDiameter(edges1);
10        int d2 = treeDiameter(edges2);
11      
12        // Determine the minimum possible diameter after merging the two trees
13        // The diameter of the merged tree is the maximum of the diameters of the two original trees, 
14        // or the sum of half the diameters of each tree (rounded up) plus 1.
15        return max({d1, d2, (d1 + 1) / 2 + (d2 + 1) / 2 + 1});
16    }
17
18    int treeDiameter(vector<vector<int>>& edges) {
19        int n = edges.size() + 1; // Number of nodes
20
21        // Create adjacency list for the tree
22        vector<vector<int>> graph(n);
23        for (const auto& e : edges) {
24            int a = e[0], b = e[1];
25            graph[a].push_back(b);
26            graph[b].push_back(a);
27        }
28
29        int diameter = 0, farthestNode = 0;
30
31        // Depth-First Search (DFS) to calculate the diameter
32        // Lambda function used for DFS traversal
33        auto dfs = [&](auto&& dfs, int node, int parent, int depth) -> void {
34            for (int neighbor : graph[node]) {
35                if (neighbor != parent) {
36                    dfs(dfs, neighbor, node, depth + 1);
37                }
38            }
39            // Update farthest distance and node
40            if (diameter < depth) {
41                diameter = depth;
42                farthestNode = node;
43            }
44        };
45
46        // Execute DFS twice to find the tree diameter
47        dfs(dfs, 0, -1, 0);  // First DFS to find the farthest node from root
48        dfs(dfs, farthestNode, -1, 0); // Second DFS from farthest node to find the actual diameter
49      
50        return diameter;
51    }
52};
53

1function minimumDiameterAfterMerge(edges1: number[][], edges2: number[][]): number {
2    // Calculate the diameter of the first tree.
3    const d1 = treeDiameter(edges1);
4    // Calculate the diameter of the second tree.
5    const d2 = treeDiameter(edges2);
6
7    // Return the maximum of the two diameters or the minimum possible diameter after merging.
8    return Math.max(d1, d2, Math.ceil(d1 / 2) + Math.ceil(d2 / 2) + 1);
9}
10
11function treeDiameter(edges: number[][]): number {
12    // Number of nodes is one more than the number of edges in a tree.
13    const n = edges.length + 1;
14  
15    // Initialize adjacency list for the graph.
16    const graph: number[][] = Array.from({ length: n }, () => []);
17  
18    // Construct the graph.
19    for (const [a, b] of edges) {
20        graph[a].push(b);
21        graph[b].push(a);
22    }
23  
24    // Variables to store the maximum distance found and the corresponding node.
25    let [maxDistance, farthestNode] = [0, 0];
26  
27    // Depth-first search helper function.
28    const dfs = (currentNode: number, parent: number, distance: number): void => {
29        // Traverse each connected node.
30        for (const neighbor of graph[currentNode]) {
31            // Continue traversal only if the node is not the parent.
32            if (neighbor !== parent) {
33                dfs(neighbor, currentNode, distance + 1);
34            }
35        }
36        // Update the maximum distance and farthest node if current distance is greater.
37        if (maxDistance < distance) {
38            maxDistance = distance;
39            farthestNode = currentNode;
40        }
41    };
42  
43    // Perform a DFS to find a farthest node from node 0.
44    dfs(0, -1, 0);
45    // Perform another DFS from the farthest node found to determine the tree's diameter.
46    dfs(farthestNode, -1, 0);
47    return maxDistance;
48}
49