树的直径问题

这篇具有很好参考价值的文章主要介绍了树的直径问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一,定义

树的直径就树中所有最短路经距离的最大值

求取树的直径可以使用两遍dfs或者树形dp获得

二,两遍dfs获得树的直径(注意,该方法边权必须都为正边权)

思路:

我们首先任取一点走dfs,然后拿深度最深的点a(必为直径的端点)为root再做一遍dfs,此时获得的最深深度就是树的直径(离直径端点最远的点当然是直径的另一端点)

证明:

  1. 如果s在ab上,假如遍历后深度最深不是a,而是t,那么有ts>as=>tb>ab(直径),不成立

树的直径问题

如果s不在直径上

 

  1. 当t与s在一块时,那么有ts>as=>tb>ab,仍然不成立
  2. 树的直径问题
  3. 当t与s不在一块 ,最深不是a而是t,还是有ts>as=>tb>ab,不成立
  4. 树的直径问题
  5.  综上,a必定是直径端点

三,树形dp

思路:

我们用len[i]数组存储i为根节点时,他的最长边,显然当i是直径端点时,len[i]就是直径,当i是直径上的点时,他的最长边必定是直径的一部分,另一部分就是他连接的其他边的其中一条(或者多条),匹配一下更新最长直径即可。具体如下图

树的直径问题

代码看下面例题即可,两道各用一种方法 

例题一:Problem - 2196 (hdu.edu.cn)

思路:

求每个点的最长距离,先说结论,每个点的最远距离点一定是直径端点。

树的直径问题

 所以我们两遍dfs求出树直径,那么第三遍从直径另一端点出发遍历,显然每个点的最远距离就是到其中一个端点的距离

#include <bits/stdc++.h>
using namespace std;
#define ll               long long
#define endl             "\n"
typedef pair<int, int> pii;
const int N = 2e5 + 10;

vector<pii>edge[N];

void dfs(int u,int f,int w,vector<int>&dis)
{
	dis[u]=dis[f]+w;
	for( pii k:edge[u])if(k.first!=f)dfs(k.first,u,k.second,dis);
}

void mysolve()
{
	int n;
	while(cin>>n)
		{
			int x,y;
			for(int i=1; i<=n; ++i)edge[i].clear();
			for(int i=2; i<=n; ++i)cin>>x>>y,edge[i].push_back({x,y}),edge[x].push_back({i,y});
			vector<int>dis1(n+1),dis2(n+1);
			dfs(1,0,0,dis1);//第一遍dfs确定第一个直径端点
			int a=max_element(dis1.begin()+1,dis1.end())-dis1.begin();
			dfs(a,0,0,dis1);//第二遍dfs确定直径另一个端点
			int b=max_element(dis1.begin()+1,dis1.end())-dis1.begin();
			dfs(b,0,0,dis2);//从另一个端点出发,每个点的最远距离就是到两个端点的最大值
			for(int i=1; i<=n; ++i)cout<<max(dis1[i],dis2[i])<<endl;
		}
}

int32_t main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll t=1;
	//cin >> t;
	while (t--)
		{
			mysolve();
		}
	system("pause");
	return 0;
}

例题二:Problem - 3534 (hdu.edu.cn)

思路:

我们用dp求,增添一个记录路径数的数组num。每次更新最长路径的时候更新该路径的路径数即可文章来源地址https://www.toymoban.com/news/detail-412170.html

#include <bits/stdc++.h>
using namespace std;
#define ll               long long
#define endl             "\n"
typedef pair<int, int> pii;
const int N = 2e5 + 10;
vector<pii>edge[N];
		
int len[N],num[N],ans,sum;
		
void dfs(int u,int f)
{
	len[u]=0,num[u]=1;
	for(pii k:edge[u])if(k.first!=f)
			{
				int v=k.first;
				dfs(v,u);
				int tmp=k.second+len[v];
				if(tmp+len[u]>ans)ans=tmp+len[u],sum=num[u]*num[v];//如果更新最长(待定)直径或者最长(待定)路径,顺便更新其数量
				else if(tmp+len[u]==ans)sum+=num[u]*num[v];
				if(tmp>len[u])len[u]=tmp,num[u]=num[v];
				else if(tmp==len[u])num[u]+=num[v];
			}
}
		
void mysolve()
{
	int n;
	while(cin>>n)
		{
			for(int i=1; i<=n; ++i)edge[i].clear();
			int x,y,w;
			for(int i=1; i<n; ++i)cin>>x>>y>>w,edge[x].push_back({y,w}),edge[y].push_back({x,w});
			ans=sum=0;
			dfs(1,0);
			cout<<ans<<" "<<sum<<endl;
		}
}
		
int32_t main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll t=1;
	//cin >> t;
	while (t--)
		{
			mysolve();
		}
	system("pause");
	return 0;
}

到了这里,关于树的直径问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 关于树的直径的一切

    本文使用 CC BY-NC-SA 4.0 许可 。 本文为笔者在 OI 学习中的复习向学习笔记。 部分内容会比较简略。 如有好的习题会不断补充。 以下部分详细证明可见 OI Wiki 。 树的直径 指树上任意两点间距离的最大值。 先以任意点为根找到最远点 (v) 。 再以 (v) 为根找到最远点 (u) 。

    2024年04月08日
    浏览(46)
  • leetcode543--二叉树的直径

    1. 题意 求二叉树上最远两个节点之间的距离。 2. 题解 2.1 暴力 最长路径的三种情况 通过根节点 在左子树 在右子树 通过根节点的最长路径长度一定是左右子树深度之和。 但是这样求左右子树的深度会不断重复,所以复杂度很高。 2.2 动态规划 我们可以在求深度的时候,更新

    2024年04月26日
    浏览(34)
  • LeetCode: 二叉树的直径(java)

    543题:二叉树的直径 给你一棵二叉树的根节点,返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。 输入:root = [1,2,3,4,5] 输出:3 解释:3 ,取路径

    2024年02月06日
    浏览(42)
  • LeetCode 热题 100 JavaScript--543. 二叉树的直径

    给你一棵二叉树的根节点,返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。

    2024年02月14日
    浏览(40)
  • 【图论C++】树的直径(DFS 与 DP动态规划)

    UpData Log👆 2023.9.27 更新进行中 Statement0🥇 一起进步 Statement1💯 有些描述是个人理解,可能不够标准,但能达其意 21-1-1 定义 树上 最远的两个节点之间 的距离被称为 树的直径 ,连接这两个点的路径 被称为 树的最长链 。 21-1-2 性质 1 、这两个最远点一定是叶子节点 1、这 两

    2024年02月07日
    浏览(42)
  • 【ccf-csp题解】第四次csp认证-第四题-网络延时-树的直径

    本题所求的实际上是树的直径,即树中的任意两个结点之间的最大距离 采用的方法是dfs 从根节点开始遍历,对于每一个被dfs的结点m,返回此结点m到所有叶子结点的距离最大的那个即d1,同时在dfs过程当中记录结点m到所有叶子结点的距离第二大的那个,即d2 那么最终答案就是

    2024年02月09日
    浏览(43)
  • 863. 二叉树中所有距离为 K 的结点

    863. 二叉树中所有距离为 K 的结点 C代码:dfs

    2024年02月09日
    浏览(35)
  • 算法刷题Day 22 二叉搜索树的最近公共祖先+二叉搜索树中的插入操作+删除二叉搜索树中的节点

    根据二叉搜索树的性质,相比普通二叉树可以极大程度的简化代码,作为公共祖先其值一定在两个给定节点值之间,从树根往下遍历,第一次出现两个给定节点值之间的值,那个节点即为最近公共祖先(为什么是最近不是最远?根节点一般为最远,第一次出现的值处于两个给

    2024年02月17日
    浏览(44)
  • day21 | 530.二叉搜索树的最小绝对差、 501.二叉搜索树中的众数、 236. 二叉树的最近公共祖先

    目录: 530.二叉搜索树的最小绝对差 链接:https://leetcode.cn/problems/minimum-absolute-difference-in-bst/ 给你一个二叉搜索树的根节点  root  ,返回  树中任意两不同节点值之间的最小差值  。 差值是一个正数,其数值等于两值之差的绝对值。 示例 1: !https://assets.leetcode.com/uploads/202

    2024年02月09日
    浏览(39)
  • 算法刷题Day 21 二叉搜索树的最小绝对差+二叉搜索树中的众数+二叉树的最近公共祖先

    递归 递归中保存前一个节点的指针的方法,需要再学习,巩固一下 迭代 一下子就想到的方法:遍历一遍二叉搜索树,把各个节点的值存进哈希表里(节点值——键,出现频率——值),再遍历哈希表找众数 一般方法 既然是二叉搜索树,中序遍历就是有序的。有序的话,我

    2024年02月16日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包