树的最长链-POJ 1985 树的直径（最长链）+牛客小白月赛6-桃花
求树直径的方法在此转载一下大佬们的分析：
可以随便选择一个点开始进行bfs或者dfs，从而找到离该点最远的那个点（可以证明，离树上任意一点最远的点一定是树的某条直径的两端点之一；树的直径：树上的最长简单路径）。再从找到的点出发，找到据该点的最远点，那么这两点就确定了树的一条直径，两点间距即为所求距离。
无意中看到一道水题，也就是POJ 1383
题目中给出了一个无环的迷宫，求出其中最长的一条路
我们知道无环图本质上可以认为就是树，所以此题完全可以使用树的最长链算法
即：随便从某个节点C开始DFS或BFS找到最远的一个点A，再从点A开始DFS或BFS找到最远的一点B，那么路径A->B必然是树上的最长路径。
这个算法很多人都知道并且当做结论使用，但很少看到有人给出正确性证明
所以本人简要分析后，给出一个简单的文字性证明：
（最好拿出纸笔画个图，有助于理解下面这段抽象的语死早描述）
首先我们知道对于一个图我们可以任取一个起始点C作为根来构造生成树（其实本来就是树，就是指定一个根C）
那么我们接下来可以分两种情况来讨论：
1. 若最长链包含树根（起始点C），那么DFS/BFS一次必然能够找到最长链的一端，再DFS/BFS一次必然找到最长链另一端。这种情况很容易理解。
2. 若最长链不包含树根（起始点C），在这里我们可以先做出【断言1】：从起始点C开始DFS/BFS查找最远节点A，一定会在中途遇到最长链上的点（暂且把首次遇到的最长链上的那个点称作TR）；只要遇到了最长链上的点之后，子问题变为从TR作为根寻找最长链，然后就和上面的情况1相同了。
为什么【断言1】一定成立？首先如果最长链不包含起始点C，则最长链必然完全包含于C手下的某个子树T中（而且这个子树的根就是上面所说的TR）。然后用反证法，假设这个子树T的最深节点B的对于起始点C的深度为h(B)，那么如果说从起始点C一直走到某个尽头A而没有经过TR的话，那么我们可以做出【断言2】：点A的深度h(A)必定小于等于h(B)；与前提“A是距离起始点C最远的节点”矛盾。
所以只要【断言2】成立则上述反证成功。
而说明【断言2】仍然是反证法，如果点A的深度h(A)大于h(B)，那么路径(A->C->TR)的长度至少为h(A)+1且大于h(B)，所以路径(A->C->TR->B)的长度一定比子树T中的最长链更长！与前提“最长链一定完全包含于C手下的子树T中”矛盾。
至此得证。原文出处https://blog.csdn.net/macuilxochitl/article/details/19157579
这里讲POJ-1985
题自己看
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #define INF 1e9+7 using namespace std; const int MAXN = 100005; const int MAXM = 111111; int n,m; struct EDGE { int v,next,w; }edge[MAXN]; int head[MAXN],e; int q[MAXN],vis[MAXN],d[MAXN]; void init() { e=0; memset(head,-1,sizeof(head)); } void add(int u,int v,int w)//链式前向星部分 { edge[e].v=v; edge[e].w=w;//权重 edge[e].next=head[u];//下一条边 head[u]=e++;//u为节点边的头节点 } void bfs(int src) { for(int i=1;i<=n;i++)vis[i]=0,d[i]=INF; int h=0,t=0; queue<int>q; q.push(src); vis[src]=1; d[src]=0; while(!q.empty()) { int u=q.front(); q.pop(); for (int i=head[u];i!=-1;i=edge[i].next) { int v = edge[i].v; int w = edge[i].w; if (d[u]+w<d[v]){ d[v]=d[u]+w; if (!vis[v]) { q.push(v);//把它存下来 vis[v]=1; } } } } } int main(){ int u,v,w; char k; scanf("%d%d",&n,&m); init(); for(int i=1;i<=m;i++) { scanf("%d%d%d%*s",&u,&v,&w); add(u,v,w); add(v,u,w); } bfs(1); int pos=-1,mx=-1; for (int i=1;i<=n;i++)//找到距离这个点最大的并记录下距离它最远的点 if (d[i]>mx) { mx=d[i]; pos=i; } bfs(pos);//从距离它最远的点出发，再次bfs找这样就能找到直径 mx=-1; for (int i=1;i<=n;i++) if (d[i]>mx)mx=d[i]; printf("%d\n",mx); return 0; }
类似题-牛客小白月赛6-桃花，这题没有边权值，可以给边一个权值1
这样答案就是最长链长度+1
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #define INF 1e9+7 using namespace std; const int MAXN = 2000000; const int MAXM = 2000000; int n,m; struct EDGE { int v,next,w; }edge[MAXN]; int head[MAXN],e; int q[MAXN],vis[MAXN],d[MAXN]; void init() { e=0; memset(head,-1,sizeof(head)); } void add(int u,int v,int w)//链式前向星部分 { edge[e].v=v; edge[e].w=w;//权重 edge[e].next=head[u];//下一条边 head[u]=e++;//u为节点边的头节点 } void bfs(int src) { for(int i=1;i<=n;i++)vis[i]=0,d[i]=INF; int h=0,t=0; q[t++]=src; vis[src]=1; d[src]=0; while(h<t) { int u=q[h++]; for (int i=head[u];i!=-1;i=edge[i].next) { int v = edge[i].v; int w = edge[i].w; if (d[u]+w<d[v]){ d[v]=d[u]+w; if (!vis[v]) { q[t++]=v;//把它存下来 vis[v]=1; } } } } } int main(){ int u,v,w; char k; scanf("%d",&n); init(); for(int i=1;i<=n-1;i++) { scanf("%d%d",&u,&v); add(u,v,1); add(v,u,1); } bfs(1); int pos=-1,mx=-1; for (int i=1;i<=n;i++) if (d[i]>mx) { mx=d[i]; pos=i; } bfs(pos); mx=-1; for (int i=1;i<=n;i++) if (d[i]>mx)mx=d[i]; printf("%d\n",mx+1); return 0; }
投递蚂蚁集团等公司10个岗位 >