树的最大权值

[题目链接](https://www.nowcoder.com/practice/8aeda31a5b524b31a2fcdfb62341aed6)

思路

给定一棵 个结点的树，以及 26 个字母各自的数量（总和为 ），要求将每个字母填入恰好一个结点，使得树上所有"字符序列构成回文串"的简单路径中，最长路径的结点数最大。

关键观察一：最长回文路径长度的上界

设 26 个字母的个数分别为 。定义：

  • （可组成的字符对数）
  • （奇数个数的字母数量）

一个长度为 的回文串需要 对相同字符，以及当 为奇数时需要 1 个中心字符。因此，无论路径怎么选，能构成回文的最大长度为：

$$

即先用完所有字符对（贡献 个字符），如果还有剩余的奇数字符，可以放一个在中间。

关键观察二：路径长度的上界

树上最长简单路径的结点数就是直径（以结点数计）。两次 BFS 即可求得。

为什么答案恰好是 ？

  1. 上界：路径结点数不超过直径，回文长度不超过 ，因此答案 。
  1. 可达性：设直径路径经过结点 。对于任意 ，取前 个结点即构成长度为 的路径。因此树上存在所有长度 到 的路径。
  1. 字符分配自由度：我们可以自由选择哪些字符放在目标路径上。只需选出 对字符依次放在路径的首尾对称位置， 为奇数时再选一个字符放中间，其余字符随意填到其他结点。只要 ，一定能选出足够多的字符对。

综上，答案为 。

样例演示

，即 ，。

  • ，（ 各为奇数）
  • 树为链 ，直径

答案 。例如在路径 上放 c d c，即为回文。

代码

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int cnt[26];
    for(int i = 0; i < 26; i++) cin >> cnt[i];

    int n;
    cin >> n;

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

    // 两次 BFS 求直径（结点数）
    auto bfs = [&](int start) -> pair<int,int> {
        vector<int> dist(n + 1, -1);
        queue<int> q;
        dist[start] = 1;
        q.push(start);
        int far = start, maxd = 1;
        while(!q.empty()){
            int u = q.front(); q.pop();
            for(int v : adj[u]){
                if(dist[v] == -1){
                    dist[v] = dist[u] + 1;
                    if(dist[v] > maxd){
                        maxd = dist[v];
                        far = v;
                    }
                    q.push(v);
                }
            }
        }
        return {far, maxd};
    };

    auto [u, d1] = bfs(1);
    auto [v, diameter] = bfs(u);

    // 计算最大回文长度
    int odd = 0, pairs = 0;
    for(int i = 0; i < 26; i++){
        pairs += cnt[i] / 2;
        if(cnt[i] % 2) odd++;
    }
    int maxPalin = 2 * pairs + (odd > 0 ? 1 : 0);

    cout << min(diameter, maxPalin) << "\n";
    return 0;
}

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        int[] cnt = new int[26];
        for (int i = 0; i < 26; i++) cnt[i] = Integer.parseInt(st.nextToken());

        int n = Integer.parseInt(br.readLine().trim());
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine().trim());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        int[] bfsResult = bfs(1, n, adj);
        int far1 = bfsResult[0];
        bfsResult = bfs(far1, n, adj);
        int diameter = bfsResult[1];

        int odd = 0, pairs = 0;
        for (int i = 0; i < 26; i++) {
            pairs += cnt[i] / 2;
            if (cnt[i] % 2 != 0) odd++;
        }
        int maxPalin = 2 * pairs + (odd > 0 ? 1 : 0);

        System.out.println(Math.min(diameter, maxPalin));
    }

    static int[] bfs(int start, int n, List<List<Integer>> adj) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();
        dist[start] = 1;
        q.add(start);
        int far = start, maxd = 1;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    if (dist[v] > maxd) {
                        maxd = dist[v];
                        far = v;
                    }
                    q.add(v);
                }
            }
        }
        return new int[]{far, maxd};
    }
}

复杂度分析

  • 时间复杂度：。两次 BFS 各遍历所有边一次，统计字母个数 。
  • 空间复杂度：。存储邻接表和 BFS 距离数组。