Explanation

Let's consider the longest possible path the added edge could create. One way to find this path would be to use the two farthest nodes on each tree from the nodes the added edge connects. Therefore, on each tree, the optimal node to connect the edge to is the node that has the shortest possible path to the farthest node.

It turns out that this node is always the middle of the tree's diameter. To help understand this, we can visualize the tree with its diameter as a horizontal line, and the other nodes 'hanging' off of it:

Note how moving the node to anything but 3 extends the longest path by the edge that was just used.

Now it remains to calculate this resulting length. When the diameter's length is even, the longest path will use the longer of the 2 halves of the diameter, so we need to divide the diameters by 2, round up, and add 1 for the added edge itself (If you don't know how to find the diameter of a tree, see CPH 14.2).

This is, however, not necessarily the longest path. It's possible for the initial diameter of either of the two trees to be longer. So we need to compare the above value to these as well.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <bits/stdc++.h>
using namespace std;

/** @return the farthest node and its distance from the given node. */
pair<int, int> dfs(const vector<vector<int>> &tree, int node = 1, int previous = 0,
                   int length = 0) {
	pair<int, int> max_path = {node, length};
	for (const int &i : tree[node]) {
		if (i == previous) { continue; }
		pair<int, int> other = dfs(tree, i, node, length + 1);

Copy
import java.io.*;
import java.util.*;

public class MinimizeDiameter {
	private static class Pair {
		public int first;
		public int second;
		public Pair(int first, int second) {
			this.first = first;
			this.second = second;