很久没写blog了，今天水一篇。
今天来讲讲树的直径

树的直径

什么？你不知道什么是树？点此处
什么是树的直径呢？
树的直径就是树中两个节点最远的距离。
那该如何求呢？
其实也很简单。

方法一：树形dp

我们可以运用树形dp，设

gx​ 表示从节点x出发走向以x为根的自述，能够到达最远节点的距离，若

edge(x,y) 表示边权，y表示x的子节点，则有：

gx​=max(gy​+edge(x,y))
接着，我们考虑经过节点x的最长链的长度，设为

Fx​，则答案为

maxx=1−n​(Fx​)
那么我们想如何转移

Fx​，显然

Fx​=max(gyi​​+gyj​​+edge(x,yi​)+edge(x,yj​))
但是这样去枚举的时间复杂度难道不是很不能接受吗？
那我们想一想怎么优化吧~
请大家想一想g数组是怎么弄成的？
在未转移完g数组时，g数组是不是就指的是已做的儿子的max？是吧
那么我们就可以先转移F，再转移g了，具体实现看代码。

void dfs(int u,int fa){

	for (int i=head[u];i;i=e[i].next){//链式前向星

		int v=e[i].to;

		if (v==fa) continue;

		dfs(v,u);

		ans=max(ans,g[u]+g[v]+e[i].w);//e[i].w指的是边权

		g[u]=max(g[u],g[v]+e[i).w;

	}

	return;

}



方法二：两次BFS/DFS

我们设一棵树的根为root，那么先用DFS/BFS求出离root最远的点p，再从点p开始DFS/BFS，求出最远的q，那么p和q的路径就是树的直径。

因为不是的话，一定能找到更长的链，但与直径定义矛盾

具体证明留给读者。

就不来程序了。
总结
大家应该能看懂！点个赞吧！

对了，我的blog！

若有不当的地方，欢迎大家指出！
原创：https://www.panoramacn.com

源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。
专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说


免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。
您必须遵守我们的协议，如果您下载了该资源行为将被视为对《免责声明》全部内容的认可->
联系客服
投诉资源
 www.panoramacn.com资源全部来自互联网收集，仅供用于学习和交流，请勿用于商业用途。如有侵权、不妥之处，请联系站长并出示版权证明以便删除。
敬请谅解！ 侵权删帖/违法举报/投稿等事物联系邮箱：2640602276@qq.com
                
                
未经允许不得转载：书荒源码源码网每日更新网站源码模板！ » 树：树的直径
                                
                                    
树：树的直径
                                
                    

        

            
            
关注我们小说电影免费看
            
关注我们，获取更多的全网素材资源，有趣有料！
            
120000+人已关注
        
    
 
                
                    


                    
分享到：
        
                                赞(0)
        
                    打赏