当前位置: 首页 > article >正文

洛谷P3884 [JLOI2009] 二叉树问题(详解)c++

题目链接:P3884 [JLOI2009] 二叉树问题 - 洛谷 | 计算机科学教育新生态

   

1.题目解析

1:从8走向6的最短路径,向根节点就是向上走,从8到1会经过三条边,向叶节点就是向下走,从1走到6需要经过两条边,再用向上的边数×2+向下的边数,所以是3*2+2,所以8到6的距离是8,我们可以发现8到6的距离和6到8的距离是不一样的,8到6是8,6到8是7

                                              

2:这道题跟二叉树没什么关系,如果他告诉我们的是树上一条边一条边的形式来让我们建图的话,我们并不知道左右节点,我们都不知道左右节点那该怎么还原二叉树,所以这道题的名字,虽然是二叉树问题,本质上他跟二叉树没什么关系,他如果告诉我们的是u,v表示树上存在一条连接u,v的边这样的信息的话,就不能用二叉树的方式来存储它了,因为我们不知道左右节点,所以我们要不就用链式前向星,要不用vecrot数组,用存树的方式来存这

3:存的时候只用u指向v的这条边就行了,不用存v指向u,他给了我们两条边,我们本来不清楚谁是父亲谁是孩子,但这道题已经保证了u是v的父亲

2.讲解算法原理

1.建树 - vector数组

const int N = 110;
int n;
vector<int> edges[N]; //存树

int main()
{
	cin >> n;
	for (int i = 1; i < n; ++i)
	{
		int u, v; cin >> u >> v;
		//u -> v
		edges[u].push_back(v);
	}

	return 0;
}

2.求树的深度(高度):树高=max(子树的高度)+1

当我们站在根节点的角度求深度的时候,你只要告诉我左子树以及右子树这两颗子树的深度比较出来的最大值,再加1返回就行(树高=max(子树的高度)+1),如何求子树的高度?我们发现子树本身还是一个树,就可以继续套用这个公式(树高=max(子树的高度)+1),就可以用递归来实现求深度

int dfs(int u)
{
	int ret = 0;
	for (auto v : edges[u])
	{
		ret = max(ret, dfs(v));
	}
	return ret + 1;
}

3.树的宽度:借助bfs过程,每次入队出队一层、

树的宽度和一层一层有关系,如果涉及一层一层的话,用bfs比较好解,因为用bfs,每次循环就是把一层加入到队列里面

   

int bfs()
{
	queue<int> q;
	q.push(1);

	int ret = 0;

	while (q.size())
	{
		//记录比较队列元素个数
		int sz = q.size();
		ret = max(ret, sz);
		//把每层孩子加入队列之后循环结束
		while (sz--)
		{
			int u = q.front(); q.pop();
			for (auto v : edges[u])
			{
				q.push(v);
			}
		}
	}
	return ret;	
}

4.求x到y到距离:1.先从x向上爬,同时标记路径中,所有的点到 x的距离 2.接下来从y开始向上爬,当第一次遇到标记点时,更新结果

                                  

假设我们要求10到7之间的距离,2*2+1=5,我们可以先让10这个点向上爬,并标记向上爬的所有路径,比如10爬到6,就标记6到10之间的距离是1,继续爬到3,标记3到10的距离等于2,爬到1,标记1到10的距离是3,爬到不能再爬的时候停止

当标记完10爬到1的路径之后,让7开始向上爬,7向上爬一个点的时候就发现标记点了,这个路径就是1,刚刚标记的过程中3到10的距离是2,所以2*2+1就是10到7的距离了

1.如何向上爬?

创建数组 int fa[N];  fa[i] 表示 i 这个点的父亲是谁,比如fa[6] = 3,6的父亲就是3

                                     

2.如何标记当前点到x的距离

创建数组int dsit[N]; //dist[i] 表示 i 这个点到x的最短距离,让x指向10,如果10有父亲,更新父亲到10的距离,dist[fa[x]] = dist[x] + 1; 更新完后,让x向上移动,x = fa[x];一直重复此过程,直到走到顶

                                            

3.如何标记y到相遇点的距离

创建变量 int len = 0;假设刚开始变量y指向7,如果7有父亲,并且当前点不是相遇点就让y往上爬,直到爬到相遇点为止,y = fa[y],len++;直到y走到相遇点为止或是走到不能在走走到1为止,此时len里面就存着y到相遇点的距离

代码实现:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 110;
int n;
vector<int> edges[N]; //存树

int fa[N]; //fa[i]表示i结点的父亲
int dist[N]; //dist[i]表示i到x的最短距离

int dfs(int u)
{
	int ret = 0;
	for (auto v : edges[u])   //遍历父亲的每个孩子
	{
		ret = max(ret, dfs(v));  //记录最高层数 
	} 
	return ret + 1;   //每层加1
}

int bfs()
{
	queue<int> q;
	q.push(1);

	int ret = 0;

	while (q.size())
	{
		//记录比较队列元素个数
		int sz = q.size(); 
		ret = max(ret, sz);  //记录每层元素个数最大值
		//把每层孩子加入队列之后循环结束
		while (sz--)
		{
			int u = q.front(); q.pop();  //记录队顶元素在删除
			for (auto v : edges[u])
			{
				q.push(v); //孩子进队
			}
		}
	}
	return ret;	
}

int main()
{
	cin >> n;
	for (int i = 1; i < n; ++i)
	{
		int u, v; cin >> u >> v;
		//u -> v
		edges[u].push_back(v); //孩子v存到各自的父亲u里
		fa[v] = u; //v的父亲是u
	}

	//求深度
	cout << dfs(1) << endl;
	//求宽度
	cout << bfs() << endl;
	//求距离
	int x, y; cin >> x >> y;
	while (x != 1) //向上爬到不能再爬
	{
		dist[fa[x]] = dist[x] + 1; //记录上层节点到x的距离
		x = fa[x]; //x往上爬一层
	}

	int len = 0;
	while (y != 1 && dist[y] == 0) //没经过x经过的点,dist的值为0
	{
		len++;      //每向上一层路径加1
		y = fa[y];  //y向上爬一层
	}
	
	cout << dist[y] * 2 + len; 

	return 0;
}


http://www.kler.cn/a/525397.html

相关文章:

  • 登录授权流程
  • selenium自动化测试框架——面试题整理
  • 深度学习在金融风控中的应用:突破传统模型的瓶颈
  • ML基础-Jupyter notebook中的魔法命令
  • 2024 年度技术总结:从实践到成长
  • 深入剖析TCP协议:原理, 机制与应用
  • 【计算机视觉】目标跟踪应用
  • 文献分享:Informational ecosystems提供了分析数据和代码
  • RK3568中使用QT opencv(显示基础图像)
  • 预测不规则离散运动的下一个结构
  • mT5:一种大规模多语言预训练文本到文本Transformer
  • KVM/ARM——基于ARM虚拟化扩展的VMM
  • 评估训练模型所需的算力
  • 基于Cipher的Java加密工具类
  • C++11新特性之使用using(代替typedef)定义别名
  • CAPL与外部接口
  • ORA-04031 错误
  • 简要介绍C语言和c++的共有变量,以及c++特有的变量
  • 亚博microros小车-原生ubuntu支持系列:16 机器人状态估计
  • Windows安装Milvus