4329 树的连边II

 通过链式前向星来求树的直径

主要包括：链式前向星的初始化，遍历，使用

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+9;
int n,head[N],to[N<<1],nx[N<<1],cnt=0;
int ans=0;
int dp[N][2];//表示i子树的最长链和次长链void add(int x,int y)
{++cnt;nx[cnt]=head[x];head[x]=cnt;to[cnt]=y;return ;//返回
}//for循环说明
//head[i]:初始条件
//nx[i]:当前节点是否有子结点（是否存在其他边）
//to[i]:边i指向的节点编号
//dfs(x,y)以x为子结点，y为父节点的搜索
//循环的条件：当前节点还有边(i)
void dfs(int x,int fa)
{for(int i=head[x];i;i=nx[i])//i=nx[i]{//在循环结束之后并不是i=nx[i]//然后i=head[i] 。这个条件是一个初始化，之后的更新都是i=nx[i];int y=to[i];if(y==fa)continue;dfs(y,x);//dfs放在更新状态的前面//程序运行的时候对于一个子结点完成遍历//然后状态更新，接着是下一个子结点if((dp[y][0]+1)>dp[x][0]){dp[x][1]=dp[x][0];dp[x][0]=dp[y][0]+1;}else if((dp[y][0]+1)>dp[x][1]){dp[x][1]=dp[y][0]+1;}}return ;
}int  main()
{cin>>n;for(int i=2;i<=n;i++){int x,y;cin>>x>>y;add(x,y);add(y,x);
}dfs(1,0);for(int i=1;i<=n;i++) ans=max(ans,dp[i][1]+dp[i][0]+1);cout<<ans-1<<endl;return 0;
}