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

P3884 [JLOI2009] 二叉树问题

article 2025/1/14 17:12:15

题目描述：

如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：

- 深度：4
- 宽度：4
- 结点 8 和 6 之间的距离：8
- 结点 7 和 6 之间的距离：3

其中宽度表示二叉树上同一层最多的结点个数，节点 u, v 之间的距离表示从 u 到 v 的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。

给定一颗以 1 号结点为根的二叉树，请求出其深度、宽度和两个指定节点 x, y 之间的距离。

## 输入格式

第一行是一个整数，表示树的结点个数 n。
接下来 n - 1 行，每行两个整数 u, v，表示树上存在一条连接 u, v 的边。
最后一行有两个整数 x, y，表示求 x, y 之间的距离。

## 输出格式

输出三行，每行一个整数，依次表示二叉树的深度、宽度和 x, y 之间的距离。

## 样例 #1

## 样例输入 #1
10
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
6 10
8 6

## 样例输出 #1
4
4
8

## 提示

对于全部的测试点，保证 1 ≤ u , v , x , y ≤ n ≤ 100，且给出的是一棵树。保证 u 是 v 的父结点。

解题思路：

首先我们阅读题目，一是求树的深度，一个是求树的宽度，以及两个结点的距离（特殊）。我们一个一个来分析，求树的深度可以用到dfs的思想。观察输入的数据，首先是结点个数n，接下来的n-1行输入；第一位表示根结点，第二位表示该根结点的子结点。最后一行输入需要求得两个结点的距离。

根据结点的输入方式我们采用vector的二维数组来储存结点，例edges[1]数组存储结点1的子结点。

接着我们使用dfs进行搜索，从根结点开始，通过for循环遍历单个根结点的子结点，通过递归的方式进行深度搜索，直到遇到底部就进行返回。题目要求我们求出最大的深度，所以我们可以使用一个max来对数据进行实时更新取得最大值。最后返回到根结点，再加上根结点本身就是最大深度。

总结的出树的最大深度 = max（左子树最大深度，右子树最大深度）+ 1

模块代码：

int dfs1(int root)
{
	int ret = 0;
	for (auto e : edges[root])
	{
		ret = max(ret, dfs1(e));
	}
	return ret + 1;
}

下面我们要求最大的宽度，我们用一个队列来进行操作。首先对根结点进行入队，然后将该根结点的子结点全部入队，然后根结点出队。算一下现在队列的大小，紧接着将队列所有根结点的子结点入队，将所有根结点出队，算一算队列的大小。

最后通过一个max来更新数据，这样我们就能找到最大的宽度。

模块代码：

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 num = q.front();
			q.pop();
			for (auto e : edges[num])//让子结点入队列
			{
				q.push(e);
			}
		}
	}
	return ret;
}

最后是距离问题，阅读题目，结点u向上一条边的距离是2，而向下一条边的距离是1。例如从10到7的距离是5（2*2+1），但是从7到10的距离就是4（2+1*2）。

由于计算机不像我们人一样能分辨在哪个结点进行分叉能得到最短路径，所以我们统一以根节点（1）为终止位置。首先我们用一个数组 fa 储存每一个结点的父结点（因为我们先前的数组只允许从上往下寻找数），再开一个数组 dist 存储每个结点之间的距离。以u结点为起始点，它到它父结点的距离就等于该点的距离加上1，再将该结点u设置为其父结点，一直遍历到根结点（1）停止。接下来我们找到v，创建一个len变量记录边数，只要v不等于根结点或者 dist[v] 内的数据为0，就让v等于它的父结点。当dist[v] 内不为0时，说明走到了分叉口，就停止循环。

最后我们将 dist[v] * 2 + len 输出就是最终答案。

最后放上完整代码：

样例代码：

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

const int N = 110;
vector<int> edges[N];
int dist[N], fa[N];

int dfs1(int root)
{
	int ret = 0;
	for (auto e : edges[root])
	{
		ret = max(ret, dfs1(e));
	}
	return ret + 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 num = q.front();
			q.pop();
			for (auto e : edges[num])//让子结点入队列
			{
				q.push(e);
			}
		}
	}
	return ret;
}

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		edges[a].push_back(b);
		fa[b] = a;
	}
	int get1 = dfs1(1);
	cout << get1 << endl;
	int get2 = bfs();
	cout << get2 << endl;

	int u, v;//结点
	cin >> u >> v;

	while (u != 1)//算结点到1的距离
	{
		dist[fa[u]] = dist[u] + 1;
		u = fa[u];
	}
	int len = 0;
	while (v != 1 && dist[v] == 0)
	{
		len++;
		v = fa[v];
	}
	cout << len + dist[v] * 2 << endl;
	return 0;
}