题解 | 芭芭拉冲鸭~（续） #

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 1e5 + 10;
const int M = 18;

int st[N][M];
int depth[N];
int cnt[26][N];
vector<int> adj[N];
char a[N];

void dfs(int u, int fa, int dep){
    depth[u] = dep;
    st[u][0] = fa;
    for(int i = 0; i < 26; i ++) cnt[i][u] = cnt[i][fa];
    cnt[a[u] - 'a'][u] ++;
    for(int v : adj[u]){
        if(v != fa) dfs(v, u, dep + 1);
    }
}

int lca(int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    int dif = depth[u] - depth[v];
    for(int i = M - 1; i >= 0; i --){
        if((dif >> i) & 1) u = st[u][i];
    }
    if(u == v) return u;
    for(int i = M - 1; i >= 0; i --){
        if(st[u][i] != st[v][i]){
            u = st[u][i];
            v = st[v][i];
        }
    }
    return st[u][0];
}

signed main(){
    HelloWorld;
    
    int n; cin >> n;
    for(int i = 1; i <= n - 1; i ++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1; i <= n; i ++) cin >> a[i];
    dfs(1, 1, 1);

    for(int j = 1; j < M; j ++){
        for(int i = 1; i <= n; i ++) st[i][j] = st[st[i][j - 1]][j - 1];
    }
    int q; cin >> q;
    while(q --){
        int u, v; cin >> u >> v;
        int LCA = lca(u, v);
        bool ok = false;
        int ans = 0;
        for(int i = 0; i < 26; i ++){
            int sum = cnt[i][u] + cnt[i][v] - 2 * cnt[i][LCA];
            if(a[LCA] - 'a' == i) sum ++;
            if(sum & 1) ans += sum / 2 * 2, ok = true;
            else ans += sum;
        }
        if(ok) ans ++;
        cout << ans << endl;
    }
    return 0;
}