本文共 637 字，大约阅读时间需要 2 分钟。

BB

众所周知，LCA有N种方法。一种种慢慢学。。。

方法

1. 倍增求法

2. 待续…

Problem List

//POJ 1986 lca模板#include
   
    using namespace std;const int maxn=4e4+5;struct Edge{
   	int to;	int len;};vector
    
      G[maxn];int fa[maxn][21],dep[maxn],dist[maxn];void dfs(int u){
   	for(int i=1;(1<
     
      <=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1];//倍增DP	for(int i=0;i
      
       dep[y])swap(x,y);	int  f=dep[y]-dep[x];	for(int i=0;(1<
       
        <=f;i++)//二进制的思想，总能到达同dep		if((1<
        
         =0;i--)//二进制思想，由大到小的减，总能到达1 if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } return fa[x][0];}int main(){ int n,m; scanf("%d%d",&n,&m); int x,y,l; char c; for(int i=0;i
        
       
      
     
    
   

转载地址：http://lwuzi.baihongyu.com/