客村网站建设,查询注册公司,成都计算机培训机构哪个最好,搜索引擎营销简称为文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴最近公共祖先一、题目
1、原题链接 3555. 二叉树 2、题目描述 给定一个 n 个结点#xff08;编号 1∼n#xff09;构成的二叉树#xff0c;其根结点为 1 号点。 进行 m…
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴最近公共祖先一、题目
1、原题链接 3555. 二叉树 2、题目描述 给定一个 n 个结点编号 1∼n构成的二叉树其根结点为 1 号点。 进行 m 次询问每次询问两个结点之间的最短路径长度。 树中所有边长均为 1。 输入格式 第一行包含一个整数 T表示共有 T 组测试数据。 每组数据第一行包含两个整数 n,m。 接下来 n 行每行包含两个整数其中第 i 行的整数表示结点 i 的子结点编号。如果没有子结点则输出 −1。 接下来 m 行每行包含两个整数表示要询问的两个结点的编号。 输出格式 每组测试数据输出 m 行代表查询的两个结点之间的最短路径长度。 数据范围 1≤T≤10,1≤n,m≤1000 输入样例 1
8 4
2 3
4 5
6 -1
-1 -1
-1 7
-1 -1
8 -1
-1 -1
1 6
4 6
4 5
8 1输出样例 2
4
2
4二、解题报告
1、思路分析 思路来源y总讲解视频 y总yyds 1可以将题目所求的两点之间的最短路径长度转化为两点距离其公共祖先的距离和。 2我们可以计算出所求两点距离根结点的距离d[x1]和d[x2]然后再求出其最近公共祖先距离根结点的距离d[x3]则两点之间的最短长度为d[x1]d[x2]-2*d[x3]。 3而上述距离可以利用深搜来求最近公共祖先可以利用爬山法先将深度较深的点往上爬爬到与另一个点的深度相同后两点一起往上爬爬到的第一个相同的点即为最近公共祖先。 4模拟上述过程求解即可。
2、时间复杂度
时间复杂度为O(n*m)
3、代码详解
#include iostream
#include cstring
using namespace std;
const int N1010;
int l[N],r[N],p[N]; //l[],r[]存储每个结点的左右儿子p[]存储每个结点的父结点
int dist[N]; //dist[]存储每个结点到根结点的距离
int T,n,m;
//dfs求每个点距离根结点的距离
void dfs(int u,int d){ //u代表当前点编号d代表距离dist[u]d; if(l[u]!-1) dfs(l[u],d1); //如果左儿子存在继续从左儿子向下延伸if(r[u]!-1) dfs(r[u],d1); //如果右儿子存在继续从右儿子向下延伸
}
//爬山法求最近公共祖先
int getLca(int x,int y){if(dist[x]dist[y]) swap(x,y); //始终保持y的深度比x大while(dist[y]dist[x]) yp[y]; //y向上爬到与x同一深度while(y!x) xp[x],yp[y]; //xy一起向上爬直到遇到第一个公共祖先return x;
}
int main(){cinT;while(T--){cinnm;memset(l,-1,sizeof l);memset(r,-1,sizeof r);for(int i1;in;i){int lc,rc;cinlcrc;l[i]lc,r[i]rc;if(lc!-1) p[lc]i;if(rc!-1) p[rc]i;}dfs(1,0);while(m--){int x,y;cinxy;int lcagetLca(x,y);int ansdist[x]dist[y]-2*dist[lca];coutansendl;}}return 0;
}三、知识风暴 最近公共祖先 可以利用爬山法进行求解先将位置较低的点往上爬爬到与另一个点高度一致然后两个点一起向上爬直到遇到第一个公共祖先为止即到达的点相同。
