洛谷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;
}