有根树中，每一个点都有好几个祖先（在往根节点走的过程中遇到的都是它的祖先），一般化，把本身也称为它的祖先

对于两个点，离它们最近的一个公共祖先被称为最近公共祖先

法一：向上标记法（暴力做法）O（n）不常用

对于其中一个点，在走到根节点的过程中标记走过的点，然后另一个点开始往根节点走，走到第一个被标记过的点即为这两个点的最近公共祖先

法二：倍增法

预处理每个点向上走2^k步的节点，f[i,j]表示从i开始，向上走2^j步所能走到的节点（j大于等于0，j小于等于logn）

通过递推的方式来求

当j为0时，f(i,j)=i的父节点

当j大于0时，f(i,j)=f(f(i,j-1),j-1)

depth[i]表示深度

哨兵：如果从i开始跳2^j步会跳过根节点，那么f[i,j]=0，depth[0]=0

二进制拼凑：

比如已经有1，2，4，8，16

要想拼凑11，首先从大往小看，11小于16，不可行，11大于8，那么由于从大到小8是第一个出现，那么8可行，11减去8得3，第一个满足小于等于3的是2，所以2可行，3减2得1，第一个满足小于等于1的是1，所以1可行

利用这个思想可以把x和y跳到一个相同的位置上

x和y相差depth[x]-depth[y]步，用2的次幂拼凑出它们之间的距离

如果depth[f(x,k)]大于等于depth[y]，那么表示跳2^k步之后到达的点还是在y的下面的，那么就可以作为拼凑的一部分，可以跳2^k步

当f(a,k)等于f(b,k)时，不一定到达的是最近的公共祖先，有可能到达的是最近公共祖先的上面一个点

当f(a,k)不等于f(b,k)时，说明还没有走到a,b的最近公共祖先

预处理O（nlogn）

查询 O（logn）

步骤:

1.先将两个点跳到同一层（距根节点的距离相同）

2.如果两个点此时不在同一个位置，那么让两个点同时往上跳，一直跳到它们的最近公共祖先的下一层（即它们的最近公共祖先的儿子节点）

例1：祖孙询问 

 

 

AC代码： 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=40010,M=2*N;
int h[N],e[M],ne[M],idx;
int depth[N],fa[N][16];
int q[N];
int n,m;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs(int root){memset(depth,0x3f,sizeof depth);depth[0]=-1,depth[root]=0;int hh=0,tt=0;q[0]=root;while(hh<=tt){int t=q[hh++];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(depth[j]>depth[t]+1){depth[j]=depth[t]+1;q[++tt]=j;fa[j][0]=t;//j跳一步跳到t点,即t为j的父节点for(int k=1;k<=15;k++) fa[j][k]=fa[fa[j][k-1]][k-1];//预处理点j跳2^0,2^1,...2^15跳到哪个点}}}
}
int lca(int a,int b){if(depth[a]<depth[b]) swap(a,b);//使得a在b的下面for(int k=15;k>=0;k--){if(depth[fa[a][k]]>=depth[b]) a=fa[a][k];//如果a跳2^k步还在b的下面,那么就可以跳,哨兵的好处在于当跳2^k步后跳出根节点,那么depth为0}//此时a和b已经在同一层了,即距离根节点的距离是相同的if(a==b) return a;//如果a等于b,那么a就是a和b的最近公共祖先//否则a和b同时往上跳for(int k=15;k>=0;k--){//如果跳到的点不是同一个点,那么说明还没有跳到最近公共祖先//哨兵的第二个好处在于当跳出根节点时,跳到的点为0,那么两者就相同了if(fa[a][k]!=fa[b][k]){a=fa[a][k];b=fa[b][k];}}//此时a和b跳到了它们最近公共祖先的儿子节点return fa[a][0];
}
int main()
{cin>>n;int root=0;memset(h,-1,sizeof h);for(int i=0;i<n;i++){int a,b;cin>>a>>b;if(b==-1) root=a;else add(a,b),add(b,a);}bfs(root);cin>>m;while(m--){int a,b;cin>>a>>b;int p=lca(a,b);if(p==a) cout<<1<<endl;else if(p==b) cout<<2<<endl;else cout<<0<<endl;}return 0;
}

vector，queue版: 

#include<bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;
const int N=4e4+10,M=17;
int fa[N][M];
int depth[N];
int n,m;
vector<vector<int>>e(N);
queue<int>q;
void bfs(int root){memset(depth,0x3f,sizeof depth);depth[0]=-1,depth[root]=0;q.push(root);while(q.size()){int t=q.front();q.pop();for(auto v:e[t]){if(depth[v]>depth[t]+1){depth[v]=depth[t]+1;q.push(v);fa[v][0]=t;for(int k=1;k<M;k++) fa[v][k]=fa[fa[v][k-1]][k-1];}}}
}
int lca(int a,int b){if(depth[a]<depth[b]) swap(a,b);for(int k=16;k>=0;k--){if(depth[fa[a][k]]>=depth[b]) a=fa[a][k];}if(a==b) return a;for(int k=16;k>=0;k--){if(fa[a][k]!=fa[b][k]){a=fa[a][k];b=fa[b][k];}}return fa[a][0];
}
void solve() {cin>>n;int root;for(int i=0;i<n;i++){int a,b;cin>>a>>b;if(b==-1) root=a;else {e[a].push_back(b);e[b].push_back(a);}}bfs(root);cin>>m;while(m--){int x,y;cin>>x>>y;int l=lca(x,y);if(l==x) cout<<1<<endl;else if(l==y) cout<<2<<endl;else cout<<0<<endl;}
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

法三：Tarjan----离线求LCA O（n+m）（向上标记法的优化）

在线：对于每一个询问单独处理

离线：对于所有询问，全部存起来，一起处理，再一起输出

在深度优先遍历时，将所有点分三大类：（1）已经遍历过，且回溯过的点 （2）正在搜索的分支 （3）还未搜索到的点

tarjan在存储询问的时候，正反都会存一次，当lca(u,v)等于u,v其中一个时，lca会求两次，其它情况lca求一次，正反都存一次的目的是为了防止漏求lca

例：

AC代码： 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int,int>PII;
const int N=20010,M=2*N;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
int dist[N];
int p[N];
int res[N];
int vis[N];
vector<PII>query[N];//first存查询的另外一个点,second存查询编号
void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa){for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;dist[j]=dist[u]+w[i];dfs(j,u);}
}
int find(int x){if(p[x]!=x) p[x]=find(p[x]);return p[x];
}
void tarjan(int u){vis[u]=1;//入u时,标记ufor(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(!vis[j]){tarjan(j);p[j]=u;//回u时,v指向u,回u表示u往下搜完其中的一条路回到u}}//离u时,枚举LCA//离u表示u的子树已经全部搜完了for(auto item:query[u]){int y=item.first,id=item.second;if(vis[y]){int anc=find(y);res[id]=dist[u]+dist[y]-dist[anc]*2;}}
}
int main()
{cin>>n>>m;memset(h,-1,sizeof h);for(int i=0;i<n-1;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c),add(b,a,c);}for(int i=0;i<m;i++){int a,b;cin>>a>>b;if(a!=b){query[a].push_back({b,i});query[b].push_back({a,i});}}for(int i=1;i<=n;i++) p[i]=i;dfs(1,-1);tarjan(1);for(int i=0;i<m;i++) cout<<res[i]<<endl;return 0;
}

 

 

[BJOI2018] 求和 - 洛谷

该题是点前缀和

AC代码:

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=3e5+10,mod=998244353;
int depth[N],fa[N][22];
int mi[60];//mi[j]表示depth[v]的j次幂
int s[N][60];//s[v][j]表示从根节点到v的路径节点的深度的j次幂之和
int n,m;
int root;
vector<vector<int>>e(N);
queue<int>q;
void bfs(int root){memset(depth,0x3f,sizeof depth);depth[0]=-1,depth[root]=0;q.push(root);while(q.size()){int t=q.front();q.pop();for(auto v:e[t]){if(depth[v]>depth[t]+1){depth[v]=depth[t]+1;q.push(v);fa[v][0]=t;for(int k=1;k<=20;k++) fa[v][k]=fa[fa[v][k-1]][k-1];for(int j=1;j<=50;j++) mi[j]=mi[j-1]*depth[v]%mod;for(int j=1;j<=50;j++) s[v][j]=(mi[j]+s[t][j])%mod;}}}
}
int lca(int a,int b){if(depth[a]<depth[b]) swap(a,b);for(int k=20;k>=0;k--){if(depth[fa[a][k]]>=depth[b]) a=fa[a][k];}if(a==b) return a;for(int k=20;k>=0;k--){if(fa[a][k]!=fa[b][k]){a=fa[a][k];b=fa[b][k];}}return fa[a][0];
}
void solve() {cin>>n;for(int i=0;i<n-1;i++){int a,b;cin>>a>>b;e[a].push_back(b);e[b].push_back(a);}root=1;mi[0]=1;bfs(root);cin>>m;for(int i=0;i<m;i++){int a,b,k;cin>>a>>b>>k;int l=lca(a,b);cout<<(s[a][k]+s[b][k]-s[l][k]-s[fa[l][0]][k]+2*mod)%mod<<endl;}
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

 树上差分

 

 

[USACO15DEC] Max Flow P - 洛谷

AC代码:

#include<bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;
const int N=5e4+10;
int depth[N],fa[N][22];
int diff[N];//差分数组
int n,k;
int root;
int ans;
vector<vector<int>>e(N);
queue<int>q;
void bfs(int root){memset(depth,0x3f,sizeof depth);depth[0]=-1,depth[root]=0;q.push(root);while(q.size()){int t=q.front();q.pop();for(auto v:e[t]){if(depth[v]>depth[t]+1){depth[v]=depth[t]+1;q.push(v);fa[v][0]=t;for(int k=1;k<=20;k++) fa[v][k]=fa[fa[v][k-1]][k-1];}}}
}
void dfs(int u,int fa){for(auto v:e[u]){if(v==fa) continue;dfs(v,u);diff[u]+=diff[v];}ans=max(ans,diff[u]);
}
int lca(int a,int b){if(depth[a]<depth[b]) swap(a,b);for(int k=20;k>=0;k--){if(depth[fa[a][k]]>=depth[b]) a=fa[a][k];}if(a==b) return a;for(int k=20;k>=0;k--){if(fa[a][k]!=fa[b][k]){a=fa[a][k];b=fa[b][k];}}return fa[a][0];
}
void solve() {cin>>n>>k;for(int i=0;i<n-1;i++){int a,b;cin>>a>>b;e[a].push_back(b);e[b].push_back(a);}root=1;bfs(root);while(k--){int a,b;cin>>a>>b;int l=lca(a,b);diff[a]++,diff[b]++;diff[l]--,diff[fa[l][0]]--;}dfs(1,0);cout<<ans<<endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}