|
lca 求最近公共祖先 暴力：搜两个点的所有祖先，相对寻找最近的祖先 O(n^2) 倍增：快速幂， ST表（区域最小，区域最大）：dp[i][j] 从i开始后面2^j个数据中，最大（小）的值 如果能够通过st表延伸出表示出x这个节点在某个范围中的祖先节点的方式， 就可以通过倍增解决lca问题。 设树的节点为i，i的父节点存在father[i]中 第一层父节点：fat1[i]=father[i] 第二层父节点：fat2[i]=fat1[fat1[i]] 第三层父节点：fat3[i]=fat1[fat2[i]] 第三层父节点：fat4[i]=fat2[fat2[i]] 状态：dp[i][j]表示编号i节点的第2^j层父节点 方程：dp[i][j]=dp[dp[i][j-1]][j-1]; i---------------j ^ dp[i][j-1] dp[i][j]=dp[dp[i][j-1]][j-1] dp[i][j+1]=dp[dp[i][j]][j] 算法部分： 邻接表存树 vector<int> g[100];//g[i][0]存数据，g[i][x]存子节点编号 int dp[100][20]; int level[100];//第几层 初始化边界：设置所有节点的第一代父节点 void dfs(int r,int v,int l){ dp[v][0]=r;//当前节点的父节点为r level[v]=l; for(int i=0;i<g[v].size();i++){ dfs(v,g[v][i],l+1);//（父,子,层） } } int root=1;//根节点编号 dfs(-1,root,1); //动态规划的填表过程 for(int j=1;1<<j+1<100;j++){ for(int i=0;i<100;i++){ if(dp[i][j]<0) dp[i][j+1]=-1; else dp[i][j+1]=dp[dp[i][j]][j]; } } //利用dp处理lca O(logn) int lca(int x,int y){ if(level[x]>level[y]) swap(x,y); while(level[x]<level[y]) y=dp[y][log2(level[y]-level[x])]; if(x==y) return x; for(int i=log2(level[x]);i>=0;i--){ if(dp[x][i]!=dp[y][i]){ x=dp[x][i]; y=dp[y][i]; } } return dp[x][0]; } //-----假如没有dp 先获悉所有节点的父节点，记到father[]内 搜索 O(n) int lca(int x,int y){ while(level[x]<level[y]) y=father[y]; while(level[y]<level[x]) x=father[x]; //此时x和y一定在同一层 while(father[x]!=father[y]){ y=father[y]; x=father[x]; } return father[x]; } 解题部分： int n,q,x,y; cin>>n; for(int i=1;i<n;i++){ cin>>x>>y; g[x].push_back(y); } cin>>q; while(q--){ cin>>x>>y; int t=lca(x,y); cout<<level[x]-level[t]+level[y]-level[t]<<endl; } ```c++ #include <bits/stdc++.h> using namespace std; int n,m,dp[1010][20],level[1010]={}; vector<int> e[1010]; void dfs(int r,int v,int l){ dp[v][0]=r; level[v]=l; for(int i=0;i<e[v].size();i++){ dfs(v,e[v][i],l+1); } } void get(){ int root=1; dfs(-1,root,1); for(int j=1;1<<j+1<100;j++){ for(int i=0;i<100;i++){ if(dp[i][j]<0){ dp[i][j+1]=-1; } else{ dp[i][j+1]=dp[dp[i][j]][j]; } } } } int lca(int x,int y){ if(level[x]>level[y]){ swap(x,y); } while(level[x]<level[y]){ int log=log2(level[y]-level[x]); y=dp[y][log]; } if(x==y){ return x; } for(int i=log2(level[x]);i>=0;i--){ if(dp[x][i]!=dp[y][i]){ x=dp[x][i]; y=dp[y][i]; } } return dp[x][0]; } int main() { scanf("%d",&n); for(int i=2;i<=n;i++) { int x,y; scanf("%d%d",&x,&y); e[x].push_back(y); } get(); scanf("%d",&m); while(m--){ int x,y; scanf("%d%d",&x,&y); int t=lca(x,y); cout<<level[x]-level[t]+level[y]-level[t]<<endl; } return 0; } ``` |