首页 > 代码库 > 求树的最长链
求树的最长链
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 }
求树的最长链
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。