题解 | 树的最大权值

import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static List<List<Integer>> adjacencyList;
    private static boolean[] visited;
    private static int[] distance;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        boolean oddExist = false;
        int maxHalfStrLen = 0;
        for (int i = 0; i < 26; i++) {
            int nChar = in.nextInt();
            if (nChar % 2 == 1) oddExist = true;
            maxHalfStrLen += nChar / 2;
        }
        int maxStrLen = oddExist ? (maxHalfStrLen * 2 + 1) : (maxHalfStrLen * 2);

        // 读取节点个数 n
        int n = in.nextInt();
        adjacencyList = new ArrayList<>(n + 1); // 节点编号从 1 到 n
        for (int i = 0; i <= n; i++) {
            adjacencyList.add(new ArrayList<>());
        }

        // 读取 n-1 条边并构建无向图
        for (int k = 0; k < n - 1; k++) {
            int i = in.nextInt();
            int j = in.nextInt();
            adjacencyList.get(i).add(j);
            adjacencyList.get(j).add(i);
        }

        // 计算树的直径
        int diameter = computeTreeDiameter(n) + 1;
        int result = (diameter > maxStrLen) ? maxStrLen : diameter;
        System.out.println(result);
    }

    private static int computeTreeDiameter(int n) {
        // 第一次 BFS 找到最远的节点 u
        visited = new boolean[n + 1];
        distance = new int[n + 1];
        bfs(1); // 从任意节点开始（这里选择节点1）
        int u = 1;
        int maxDistance = 0;
        for (int i = 1; i <= n; i++) {
            if (distance[i] > maxDistance) {
                maxDistance = distance[i];
                u = i;
            }
        }

        // 第二次 BFS 从 u 出发找到最远的节点 v
        visited = new boolean[n + 1];
        distance = new int[n + 1];
        bfs(u);
        int v = 1;
        maxDistance = 0;
        for (int i = 1; i <= n; i++) {
            if (distance[i] > maxDistance) {
                maxDistance = distance[i];
                v = i;
            }
        }

        // 最长路径就是 u 到 v 的距离
        return maxDistance;
    }

    private static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;
        distance[start] = 0;

        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int neighbor : adjacencyList.get(current)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    distance[neighbor] = distance[current] + 1;
                    queue.offer(neighbor);
                }
            }
        }
    }
}

事实上，这题纯粹是两个简单问题的杂糅。

前一个问题是，给定若干个字母，问组成的最长回文字符串长度maxStrLen；

后一个问题是，给定一棵树，问最长路径上的节点数diameter；

然后输出二者中较小的那个就好。