方法思路

这道题需要找到剪切一条边后形成的两棵树直径之差的最小值。参考代码中的思路是：

1. 构建树的邻接表
2. 记录所有的边
3. 对于每条边(u,v)，我们可以通过设置父节点来模拟剪切
4. 分别计算剪切后形成的两棵子树的直径
5. 找出所有可能的直径差的最小值

代码实现

Java

import java.util.*;

public class Main {
    static List<List<Integer>> tree;
    static List<int[]> edges;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        tree = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            tree.add(new ArrayList<>());
        }
        edges = new ArrayList<>();

        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            tree.get(u).add(v);
            tree.get(v).add(u);
            edges.add(new int[]{u, v});
        }

        int ans = Integer.MAX_VALUE;

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int[] ans1 = new int[1];
            int[] ans2 = new int[1];
            treeLength(u, v, ans1);
            treeLength(v, u, ans2);
            ans = Math.min(ans, Math.abs(ans1[0] - ans2[0]));
        }

        System.out.println(ans);
    }

    static int treeLength(int u, int p, int[] ansList) {
        int maxLen = 0;
        List<Integer> maxLenList = new ArrayList<>();
        maxLenList.add(0);
        maxLenList.add(0);

        for (int v : tree.get(u)) {
            if (v == p) {
                continue;
            }
            int t = treeLength(v, u, ansList) + 1;
            maxLen = Math.max(maxLen, t);
            maxLenList.add(t);
        }

        Collections.sort(maxLenList, Collections.reverseOrder());
        ansList[0] = Math.max(ansList[0], maxLenList.get(0) + maxLenList.get(1));

        return maxLen;
    }
}

Python

def main():
    n = int(input())
    tree = [[] for _ in range(n + 1)]
    edges = []
    
    for _ in range(n - 1):
        u, v = map(int, input().split())
        tree[u].append(v)
        tree[v].append(u)
        edges.append((u, v))
    
    # 计算树的直径
    def tree_length(u, p, ans_list):
        max_len = 0
        max_len_list = [0, 0]  # 存储两个最长的路径
        
        for v in tree[u]:
            if v == p:  # 被剪切的边或父节点
                continue
            
            t = tree_length(v, u, ans_list) + 1
            max_len = max(max_len, t)
            max_len_list.append(t)
        
        # 对长度排序取最大的两个
        max_len_list.sort(reverse=True)
        ans_list[0] = max(ans_list[0], max_len_list[0] + max_len_list[1])
        
        return max_len
    
    ans = float('inf')
    
    # 枚举每条边进行剪切
    for u, v in edges:
        ans1 = [0]  # 用列表传递引用
        ans2 = [0]
        tree_length(u, v, ans1)  # 计算以u为根的子树的直径
        tree_length(v, u, ans2)  # 计算以v为根的子树的直径
        
        ans = min(ans, abs(ans1[0] - ans2[0]))
    
    print(ans)

if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

vector<vector<int>> tree;
vector<pair<int, int>> edges;

int treeLength(int u, int p, int &ansList) {
    int maxLen = 0;
    vector<int> maxLenList = {0, 0};

    for (int v : tree[u]) {
        if (v == p) {
            continue;
        }
        int t = treeLength(v, u, ansList) + 1;
        maxLen = max(maxLen, t);
        maxLenList.push_back(t);
    }

    sort(maxLenList.rbegin(), maxLenList.rend());
    ansList = max(ansList, maxLenList[0] + maxLenList[1]);

    return maxLen;
}

int main() {
    int n;
    cin >> n;
    tree.resize(n + 1);
    edges.reserve(n - 1);

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
        edges.emplace_back(u, v);
    }

    int ans = INT_MAX;

    for (auto &edge : edges) {
        int u = edge.first;
        int v = edge.second;
        int ans1 = 0;
        int ans2 = 0;
        treeLength(u, v, ans1);
        treeLength(v, u, ans2);
        ans = min(ans, abs(ans1 - ans2));
    }

    cout << ans << endl;

    return 0;
}