【算法】最近公共祖先（LCA）

【题解】

点x，y到最近公共祖先z的距离之和相当于x，y到根的距离减去两倍z到根的距离，

即ans=dis[x]+dis[y]-2*dis[z]

记得边数组要开两倍！！！T_T

#include
      
       #include
       
        using namespace std;const double eps=1e-3;const int maxn=1010;struct cyc{
    int from,to,w;}e[maxn*2];int dis[maxn],deep[maxn],f[maxn][15],n,q,cnt,head[maxn];bool vis[maxn];void insert(int u,int v,int w){cnt++;e[cnt].from=head[u];e[cnt].to=v;e[cnt].w=w;head[u]=cnt;}void dfs(int x){    vis[x]=1;    for(int i=1;(1<
        
         <=deep[x];i++)     f[x][i]=f[f[x][i-1]][i-1];    for(int i=head[x];i;i=e[i].from)     if(!vis[e[i].to])      {          int now=e[i].to;          deep[now]=deep[x]+1;          dis[now]=dis[x]+e[i].w;          f[now][0]=x;          dfs(now);      }}int lca(int x,int y){    if(deep[x]
         
          =0;i--)     if(f[x][i]!=f[y][i])      x=f[x][i],y=f[y][i];     return f[x][0];}int main(){    scanf("%d%d",&n,&q);    for(int i=1;i
         
        
       
      

也可以记录g[x][i]，则不必减去多余的。

事实证明在一些简单的树上路径问题上，倍增比链剖更有优势。

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=1010;struct edge{
    int v,from,w;}e[maxn*3];int n,first[maxn],deep[maxn],f[maxn][20],g[maxn][20],v[maxn],tot,lca,q;void insert(int u,int v,int w){tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;}void dfs(int x,int fa){    for(int i=1;(1<
         
          <=deep[x];i++)    {        f[x][i]=f[f[x][i-1]][i-1];        g[x][i]=g[x][i-1]+g[f[x][i-1]][i-1];    }    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa)    {        int y=e[i].v;        f[y][0]=x;        deep[y]=deep[x]+1;        g[y][0]=e[i].w;        dfs(y,x);    }}int find(int x,int y){    int ans=0;    if(deep[x]
          
           =0;i--)    if((1<
           
            <=deep[x]&&f[x][i]!=f[y][i]) { ans+=g[x][i]+g[y][i]; x=f[x][i];y=f[y][i]; } lca=f[x][0]; return ans+g[x][0]+g[y][0];}int main(){ scanf("%d%d",&n,&q); for(int i=1;i