洛谷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 -> vedges[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;
}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 -> vedges[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 = fa[x];}int len = 0;while (y != 1 && dist[y] == 0) //没经过x经过的点，dist的值为0{len++;y = fa[y];}cout << dist[y] * 2 + len;return 0;
}