问题

给一棵树，每个节点有一个小写字母。多次询问，每次给出两个节点 x, y，问将 x 到 y 路径上的所有字母重新排列，能组成的最长回文串的长度是多少。

思路

一个字符串能重排成回文串当且仅当至多一个字母出现奇数次。

最长回文串的长度 = 所有字母出现次数的偶数部分之和（即每对相同字母贡献2），如果存在奇数个的字母，可额外加1。

因此只需统计路径上每个字母的出现次数。

实现

用 DFS 预处理每个节点到根路径上各个字母的前缀和 cnt[u][c]。

用倍增法预处理 LCA，快速求祖先。

对于询问 (x, y)，设 l = \text{lca}(x, y)，p = \text{fa}[l]（l 的父亲），则路径上的字母出现次数为：

num=cnt[x][c]+cnt[y][c]−cnt[l][c]−cnt[p][c]

累加每对贡献，判断是否有奇数。

复杂度

预处理 O(n \log n + n \cdot 26)，单次询问 O(26)，

总时间 O((n+q) \log n)，空间 O(n \log n + n \cdot 26)n \le 2\times 10^5。

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

const int MAXN = 2e5 + 5;
const int LOG = 20;      // 2^20 > 2e5

// ---------- LCA 倍增预处理 ----------
vector<int> G[MAXN];
int depth[MAXN];
int up[MAXN][LOG];

void dfs_lca(int u, int p) {
    depth[u] = depth[p] + 1;
    up[u][0] = p;
    for (int i = 1; i < LOG; i++)
        up[u][i] = up[ up[u][i-1] ][i-1];
    for (int v : G[u]) if (v != p)
        dfs_lca(v, u);
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for (int i = 0; i < LOG; i++)
        if (diff >> i & 1) u = up[u][i];
    if (u == v) return u;
    for (int i = LOG-1; i >= 0; i--)
        if (up[u][i] != up[v][i])
            u = up[u][i], v = up[v][i];
    return up[u][0];
}

// ---------- 树上字符前缀和 ----------
int cnt[MAXN][26];  // cnt[u][c] : 从根到 u 的路径上字母 c 的出现次数
int fa[MAXN];       // 父节点

void dfs_cnt(int u, int p, const string& s) {
    fa[u] = p;
    for (int c = 0; c < 26; c++)
        cnt[u][c] = cnt[p][c];
    cnt[u][ s[u] - 'a' ]++;
    for (int v : G[u]) if (v != p)
        dfs_cnt(v, u, s);
}

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

    int n; cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    string s; cin >> s;
    s = " " + s;  // 1‑based

    // 预处理 LCA
    depth[0] = -1;
    dfs_lca(1, 0);
    // 预处理前缀和
    dfs_cnt(1, 0, s);

    int q; cin >> q;
    while (q--) {
        int x, y; cin >> x >> y;
        int anc = lca(x, y);
        int par = fa[anc];   // anc 的父亲

        int pair_cnt = 0;      // 能配成多少对相同字母
        int odd_flag = 0;      // 是否有奇数个的字母
        for (int c = 0; c < 26; c++) {
            int num = cnt[x][c] + cnt[y][c] - cnt[anc][c] - cnt[par][c];
            pair_cnt += num / 2;
            if (num % 2) odd_flag = 1;
        }
        // 最长回文串长度 = 2 * 对数 + (有奇数个时加 1)
        cout << pair_cnt * 2 + odd_flag << '\n';
    }
    return 0;
}