题解 | 芭芭拉冲鸭~（续） #
芭芭拉冲鸭~（续）
https://www.nowcoder.com/practice/8e8535a4b7ab4e7b92986a0713e17c83?
维护每个节点 从根节点出发到现在节点的26个字符前缀之和即可 + LCA模板
没太多好说的
总代码：
#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;
}
