首页 > 代码库 > 求树的最长链

求树的最长链

2次dfs的方法:

 1 void dfs(int u,int step) 2 { 3     int tmp=0; 4     if (step>t) 5     { 6         max_dist=step; 7         max_point=u; 8     } 9     for (int i=0;i<ch[u].size();i++)10     {11         int v=ch[u][i];12         if (!visit[v])13         {14             visit[v]=true;15             dfs(v,step+1);16             visit[v]=false;17         }18     }19 }s


dp方法:

 1 void dfs(int u) 2 { 3     int v,max1=-1,max2=-1; 4     visit[u]=true; 5     for (int i=0;i<ch[u].size();i++) 6     { 7         v=ch[u][i]; 8         if (!visit[v]) 9         {10             dfs(v);11             if (d[v]>=max1)12             {13                 max2=max1;14                 max1=d[v];15             }16             else if (d[v]>max2)17                 max2=d[v];18         }19     }20     d[u]=max1+1;21     ans=max(ans,max1+max2+2);22 }

 

求树的最长链