题解

本题要求我们在给定的树上给每个结点分配字母，目标是使得“回文路径”的最大长度（树的权值）达到最大。
实际上我们可以证明：

• 任何树中，一个简单路径的最大长度不会超过树的直径（最长路径）；
• 而我们又可以任意安排字母，因此在树上是否能找到一个回文路径，取决于我们能否在直径上选取一个子集的字母，使得这些字母能够构成回文。

因此问题转化为：

在全局给定的字母个数下，能构成的最长回文串长度是多少？

对于任意一个字母集合，要构成回文串，其要求是：

• 如果字符串长度为偶数，则每个字母出现次数必须为偶数；
• 如果字符串长度为奇数，则至多只有一个字母出现次数为奇数，其余字母出现次数为偶数。

因此给定每个字母的个数，我们可以计算出能构成的最长回文串长度：

• 对每个字母，取其偶数部分的和
• 如果存在至少一个字母的个数为奇数，则可以再加 1

记这个值为 L_max。

同时，我们用 DFS 或 BFS 求出树的直径长度（注意这里直径长度按照“结点数”来算）。

最后答案就是
$\text{答案} = \min(\text{树的直径长度}, L_{max})$

例如样例中，字母个数为：
a:1, c:2, d:1, z:1，其余为 0。
计算得到偶数部分总和为 2（只有 c 的 2 个可以直接使用），再加上 1（因为有 a、d、z出现奇数次）得到 3；
而链式树直径长度为 5，所以答案为 min(5,3)=3。

算法复杂度

• 计算 L_max 只需遍历 26 个字母，时间复杂度 O(1)
• 求树的直径需要两次 BFS/DFS，时间复杂度为 O(n)
• 总体复杂度为 O(n)，满足 n ≤ 10^5 的要求

Python 代码

# -*- coding: utf-8 -*-
import sys
from collections import deque

def main():
    # 读入26个字母的个数
    counts = list(map(int, sys.stdin.readline().split()))
    n = int(sys.stdin.readline().strip())
    
    # 构造树的邻接表
    tree = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u, v = map(int, sys.stdin.readline().split())
        tree[u].append(v)
        tree[v].append(u)
    
    # 求树的直径：使用两次 BFS
    def bfs(start):
        visited = [False]*(n+1)
        dist = [0]*(n+1)
        q = deque([start])
        visited[start] = True
        while q:
            u = q.popleft()
            for v in tree[u]:
                if not visited[v]:
                    visited[v] = True
                    dist[v] = dist[u] + 1
                    q.append(v)
        # 找到最远的节点及其距离
        max_node = 1
        max_dist = 0
        for i in range(1, n+1):
            if dist[i] > max_dist:
                max_dist = dist[i]
                max_node = i
        return max_node, max_dist

    # 第一次BFS，任选一个结点（例如1）
    u, _ = bfs(1)
    # 第二次BFS，从u出发找到最远点，距离为树的直径（边数）
    v, diameter_edges = bfs(u)
    # 转换成结点数（直径路径上的结点数 = 边数 + 1）
    diameter_nodes = diameter_edges + 1

    # 计算能构成的最长回文串长度 L_max
    even_sum = 0
    has_odd = False
    for cnt in counts:
        even_sum += cnt - (cnt & 1)  # cnt 去掉奇数部分，即偶数部分
        if cnt % 2 == 1:
            has_odd = True
    L_max = even_sum + (1 if has_odd else 0)

    # 最终答案为两者的最小值
    ans = min(diameter_nodes, L_max)
    print(ans)

if __name__ == '__main__':
    main()

JAVA 代码

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

public class Main {
    static int n;
    static ArrayList<Integer>[] tree;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读入26个字母的个数
        String[] parts = br.readLine().split(" ");
        int[] counts = new int[26];
        for (int i = 0; i < 26; i++) {
            counts[i] = Integer.parseInt(parts[i]);
        }
        n = Integer.parseInt(br.readLine().trim());
        
        // 初始化树的邻接表
        tree = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }
        for (int i = 1; i <= n-1; i++) {
            String[] edge = br.readLine().split(" ");
            int u = Integer.parseInt(edge[0]);
            int v = Integer.parseInt(edge[1]);
            tree[u].add(v);
            tree[v].add(u);
        }
        
        // 计算树的直径：使用两次BFS
        int[] firstBFS = bfs(1);
        int u = firstBFS[0]; // 第一次BFS得到的最远点
        int[] secondBFS = bfs(u);
        int diameterEdges = secondBFS[1]; // 边数
        int diameterNodes = diameterEdges + 1; // 结点数
        
        // 计算能构成的最长回文串长度 L_max
        int evenSum = 0;
        boolean hasOdd = false;
        for (int cnt : counts) {
            evenSum += cnt - (cnt & 1); // 取偶数部分
            if (cnt % 2 == 1) {
                hasOdd = true;
            }
        }
        int L_max = evenSum + (hasOdd ? 1 : 0);
        
        int ans = Math.min(diameterNodes, L_max);
        System.out.println(ans);
    }
    
    // BFS返回一个数组：[最远结点, 距离]
    static int[] bfs(int start) {
        boolean[] visited = new boolean[n+1];
        int[] dist = new int[n+1];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : tree[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    dist[v] = dist[u] + 1;
                    queue.add(v);
                }
            }
        }
        int maxNode = start, maxDist = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] > maxDist) {
                maxDist = dist[i];
                maxNode = i;
            }
        }
        return new int[]{maxNode, maxDist};
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n;
vector<vector<int>> tree;

// BFS函数，返回一对 {最远结点, 距离}
pair<int,int> bfs(int start) {
    vector<bool> visited(n+1, false);
    vector<int> dist(n+1, 0);
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for (int v : tree[u]) {
            if (!visited[v]){
                visited[v] = true;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    int maxNode = start, maxDist = 0;
    for (int i = 1; i <= n; i++){
        if(dist[i] > maxDist){
            maxDist = dist[i];
            maxNode = i;
        }
    }
    return {maxNode, maxDist};
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int counts[26];
    for (int i = 0; i < 26; i++){
        cin >> counts[i];
    }
    cin >> n;
    tree.resize(n+1);
    for (int i = 1; i <= n-1; i++){
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    // 两次 BFS 求树的直径（以结点数计，直径 = 边数 + 1）
    pair<int,int> first = bfs(1);
    pair<int,int> second = bfs(first.first);
    int diameterEdges = second.second;
    int diameterNodes = diameterEdges + 1;
    
    // 计算能构成的最长回文串长度 L_max
    int evenSum = 0;
    bool hasOdd = false;
    for (int i = 0; i < 26; i++){
        evenSum += counts[i] - (counts[i] & 1);
        if(counts[i] % 2 == 1)
            hasOdd = true;
    }
    int L_max = evenSum + (hasOdd ? 1 : 0);
    
    int ans = min(diameterNodes, L_max);
    cout << ans << "\n";
    return 0;
}

题目内容

小红定义一棵树的权值为:

若一条简单路径$u→v$满足$s_u+...+s_v$，是一个回文串。在所有这样的路径中，路径的长度的最大值是是该树的权值。现在小红给定一棵结点总数为$n$的树和 '$a$','$b$','$c$',...,'$z$'每种字母的个数，保证所有个数之和恰好等于$n$。

你需要将每个字母填入一个树的结点，使得该树的权值最大，输出树的最大权值。

输入描述

第一行输入一个长度为$26$的用，表示每个字母的个数，保证总和为

第二行输入一个整数$n(1≤n≤10^5)$，表示的结点总数。

接下来$n-1$行，每行输入两个整数

$u,v(1≤u,v ≤n,u≠v)$，表示树的一条边。

输出描述

输出一个整数，表示树的最大权值。

样例1

输入

1 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
5
1 2
2 3
3 4
4 5

输出

3