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;
}