如何建单页网站栏目,推广方法的总结,做网站网站代理的犯法么,推广网站站群题目链接#xff1a;P3884 [JLOI2009] 二叉树问题 - 洛谷 | 计算机科学教育新生态 1.题目解析
1#xff1a;从8走向6的最短路径#xff0c;向根节点就是向上走#xff0c;从8到1会经过三条边#xff0c;向叶节点就是向下走#xff0c;从1走到6需要经过两条边#xff0c…题目链接P3884 [JLOI2009] 二叉树问题 - 洛谷 | 计算机科学教育新生态 1.题目解析
1从8走向6的最短路径向根节点就是向上走从8到1会经过三条边向叶节点就是向下走从1走到6需要经过两条边再用向上的边数×2向下的边数所以是3*22所以8到6的距离是8我们可以发现8到6的距离和6到8的距离是不一样的8到6是86到8是7 2这道题跟二叉树没什么关系如果他告诉我们的是树上一条边一条边的形式来让我们建图的话我们并不知道左右节点我们都不知道左右节点那该怎么还原二叉树所以这道题的名字虽然是二叉树问题本质上他跟二叉树没什么关系他如果告诉我们的是uv表示树上存在一条连接uv的边这样的信息的话就不能用二叉树的方式来存储它了因为我们不知道左右节点所以我们要不就用链式前向星要不用vecrot数组用存树的方式来存这
3存的时候只用u指向v的这条边就行了不用存v指向u他给了我们两条边我们本来不清楚谁是父亲谁是孩子但这道题已经保证了u是v的父亲
2.讲解算法原理
1.建树 - vector数组
const int N 110;
int n;
vectorint 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()
{queueint 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*215我们可以先让10这个点向上爬并标记向上爬的所有路径比如10爬到6就标记6到10之间的距离是1继续爬到3标记3到10的距离等于2爬到1标记1到10的距离是3爬到不能再爬的时候停止
当标记完10爬到1的路径之后让7开始向上爬7向上爬一个点的时候就发现标记点了这个路径就是1刚刚标记的过程中3到10的距离是2所以2*21就是10到7的距离了
1.如何向上爬?
创建数组 int fa[N]; fa[i] 表示 i 这个点的父亲是谁比如fa[6] 36的父亲就是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;
vectorint 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()
{queueint 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;
}
