本文主要是介绍最近公共祖先（LCA），树上差分，树的直径总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最近也是一不小心就学到了树论，这方面确实太不行了，也该开始学习一下了，那么话不多说，进入今日份的树论学习，直接开冲
最近公共祖先（LCA）——倍增思想（可以结合我之前写的ST表学习）
我们来看什么是最近公共祖先，对于9和8来讲，其最近公共祖先为6，对于3和7来讲，其最近公共祖先为5，那么我们去求最近公共祖先总共要有两步
第一步就是深搜，我们这一遍的深搜主要是为了去统计每一个点的深度，以及往上走2的n次方步的能够达到的父亲结点吗
void dfs(int v,int father)
{dep[v]=dep[father]+1;f[v][0]=father;for(int i=1;i<20;i++){f[v][i]=f[f[v][i-1]][i-1];}for(int u:e[v]){if(u!=father){dfs(u,v);}}
}第二步就是去寻找公共祖先，首先我们要去确保u节点的深度一定要小于v节点，这样可以确保每次调用这个lca函数的时候不会出错，然后就是将u节点和v节点调到同一个深度，如果u节点和v节点相同，就说明v节点是u节点的祖先节点，直接返回v节点即可，如果不相同则就将这个两个节点一起向上推，直到这两个点相同
int lca(int u,int v)
{if(dep[u]<dep[v]){swap(u,v);}for(int i=19;i>=0;i--){if(dep[f[u][i]]>=dep[v]){u=f[u][i];}}if(u==v)return v;for(int i=19;i>=0;i--){if(f[u][i]!=f[v][i]){u=f[u][i];v=f[v][i];}}return f[u][0];
}树上差分
树上差分分为点差分和边差分
比如说我们想要将一条边上的权值都加1，那么我们需要在两个节点处先将这个1加上去，然后在最近公共祖先处-1，其父辈也要-1；
树的直径
树的直径有两种求法一种是树上dp去求树的直径，另一种就是两次dfs去求
树上dp
void dp(int x,int fa){//x表示当前的节点，fa是x
的父节点for(int i=head[x];i;i=next[i]){//前向星int y=ver[i],z=w[i];//y是下一个节点，z是x，y的距离，在本题就是1if(y==fa)continue;//只用遍历一次，不用回到父节点dp(y);ans=max(ans,dis[x]+dis[y]+z);dis[x]=max(dis[x],dis[y]+z);//dis[x]表示从节点x出发走到以x为根的子树//能够到的最远距离}
}两次dfs
void dfs1(int x,int fa){if(deep[x]>zj){zj=deep[x];num=x;}for(int i=head[x];i;i=next[i]){int y=ver[i];if(y==fa)continue;deep[y]=deep[x]+1;dfs1(y,x);}
}
void dfs2(int x,int fa){if(deep[x]>zj){zj=deep[x];num=x;}for(int i=head[x];i;i=next[i]){int y=ver[i];if(y==fa)continue;deep[y]=deep[x]+1;f[y]=x;//记录路径，表示y的父节点为xdfs2(y,x);}
}这篇关于最近公共祖先（LCA），树上差分，树的直径总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
