LCA算法求解最近公共祖先
北京信息科技大学:J题题目链接
树
感悟
：
1.加深dfs的印象
2.LCA算法（最近公共祖先）
3.倍增
4.ar数组的巧妙
题意：
芭芭拉这次来到了一棵字母树，这同样是一棵无根树，每个节点上面有一个小写字母。
芭芭拉想知道，自己从x冲刺到y，从x走到y收集所有字母，选择其中一部分字母组成一个回文串，这个
回文串的最大长度是多少
？
啥意思呢，
简单的讲走过的路不能再走的意思咯，而且注意了，从x到y的路径是唯一的，因为是树型结构。（脑海里想象后者画几个树
验证一下，就明白是唯一的了）
思路：
给出的每组测试数据，两个节点x，y。x到y收集这一路上的字母，选取一部分咯，
正常逻辑x到y一步一步，显然这种方法太慢了.
p测试组数， n节点数 ，(n,p<=100000)
每一组测试数组求解都要dfs遍历一次，
就很时间复杂复杂度到了 O(n*p)=O(1e10);
不用想肯定超时，当然你用天河计算机那是不会超时，哈哈哈。
那有没有能极大缩短时间的巧妙呢！那必须得有啊，
不然我还在写个寂寞（滑稽）。
LCA算法： 他能将时间缩短至O(n+p)
.哇，这时间复杂度，你还不i吗，i了i了。不i，那爱就消失了。。。。
//
视频一定要看，方便理解
点击链接：LCA算法视频讲解：超棒的喔，快来看看
是怎么缩短时间的呢？？
1。
fa数组-倍增，缩短时间
定义一个数组fa[i][j] i表示节点 j表示走2^j步。存放节点值。(ps: 2^j表示2的j次方)
fa[i][j]: 从节点i出发，跳2^j步后，节点的值。
就有：i+2^j= i+2^j(-1) + 2^(j-1) —->>
fa[i][j]=fa[fa[i][j-1]][j-1];
（咚咚咚，记住了喔，后面要用到的喔。。。。）
如下图：以节点11为例.(在0节点添加一个父节点-1)
fa[11][0]=5; fa[11][1]=2;fa[11][2]=-1;
跳一步 跳2步 跳4步（2^2）
你看这么跳的话，比起一步一步跳快太多了。
可能还是有小伙伴对fa不太了解。
来咱们再看一个图：
fa数组如下图：
题解代码如下(配有解释，建议先看完上文中LCA算法视频，再看)
#include<iostream>
#include<vector>
const int maxn=2e5+10;
using namespace std;
vector<int> a[maxn];
//i节点 j字符字母 从根(1)节点出发到i节点 存放到j中,ar:字符j+'a'在这条路径出现的次数。
int ar[maxn][30];
//好强大的fa数组
int fa[maxn][30]; // 节点 跳2^i步
char s[maxn];
int n;
//快速输入
int read(){
int s = 0, f = 1; char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') f = -1;
ch = getchar();
}
while(isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
return s * f;
}
//每个节点的对应的深度
int dep[maxn];
//dfs1函数递归-树的遍历。
void dfs1(int u,int pre){
dep[u]=dep[pre]+1;
//用到了它！！：fa[i][j]=fa[fa[i][j-1]][j-1];
for(int i=1;i<=20;i++){
fa[u][i]=fa[fa[u][i-1]][i-1];
}
// ar字符在dfs1中的赋值，以及添加
for(int i=0;i<26;i++) ar[u][i]=ar[pre][i];
ar[u][s[u]-'a']++;
int v;
for(int i=0;i<a[u].size();i++){
v=a[u][i];
if(v==pre) continue;
//子 父关系咯
fa[v][0]=u;
dfs1(v,u);
}
}
//LCA算法， 给两个节点x,y 返回最近公共祖先。
//拿最前面的图举个栗子，lca(7,8)=3; lca(7,9)=1;就这意思咯。。。
int lca(int x,int y){
//规定x的深度比y深度大，所以swap
if(dep[x]<dep[y]) swap(x,y);
//好好看视频，多多理解，
//下面for循环，目的是为了x，y跳同一深度
//起先x，y节点深度是不同的蛮
for(int i=20;i>=0;i--){
if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if(x==y) return x;
}
//x，y条跳到了统一深度，下for循环里x，y就可以同步跳了。
//我对这个for循环的理解：二进制吧10011101010
// 1表示if语句执行，0不执行 我是这么理解的，哈哈哈
for(int i=20;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
void solve(){
n=read();
int u,v;
for(int i=1;i<n;i++){
u=read(); v=read();
a[u].push_back(v);
a[v].push_back(u);
}
cin>>(s+1);
dep[0]=-1;
dfs1(1,0);
//for(int i=1;i<=n;i++)
//cout<<dep[i]<<" "<<i<<endl; cout<<endl;
for(int i=1;i<=n;i++){ cout<<"fa["<<i<<"]:";
for(int j=0;j<10;j++)
cout<<fa[i][j]<<" ";cout<<endl;}
//cout<<lca(4,8)<<endl<<lca(9,7)<<endl<<lca(3,7);
//dfs(1,0);
//for(int i=1;i<=n;i++)
// cout<<i<<":"<<ar[i][0]<<endl;
int T=read();
int x,y;
while(T--){
x=read();y=read();
int ans=lca(x,y);
int sum=0;
int flag=0;
//下面就是对回文字符串的处理
//多悟一悟
for(int i=0;i<26;i++){
int ks=ar[x][i]+ar[y][i]-2*ar[ans][i];
if(s[ans]=='a'+i) ks++;
if(ks%2==0) sum+=ks;
else{
if(flag==0) sum+=ks,flag=1;
else{
sum+=ks-1;
}
}
}
cout<<sum<<endl;
}
}
int main (){
solve();
}