PJOI PKU Campus 2011 B:A Problem about Tree LCA 求随意点x为根的y的父节点
节点 Tree Problem 2011 about 随意 LCA
2023-09-14 09:06:25 时间
题目链接:点击打开链接
题意:给定n个点 m个询问
以下n-1行给定一棵树
m个询问 x y
问把树转成以x为根 y的父节点是谁
第一种情况lca==y那就是x的第 dep[x] - dep[y] -1 父亲,依次向上爬山坡,利用倍增的二进制加速。
另外一种就是Father[y];
#include"cstdio" #include"iostream" #include"queue" #include"algorithm" #include"set" #include"queue" #include"cmath" #include"string.h" #include"vector" using namespace std; #define N 10050 #define e 2.718281828459 struct Edge{ int from, to, dis, nex; }edge[5*N]; int head[N],edgenum,dis[N],fa[N][20],dep[N]; void add(int u,int v,int w){ Edge E={u,v,w,head[u]}; edge[edgenum] = E; head[u]=edgenum++; } void bfs(int root){ queue<int> q; fa[root][0]=root;dep[root]=0;dis[root]=0; q.push(root); while(!q.empty()){ int u=q.front();q.pop(); for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=head[u]; ~i;i=edge[i].nex){ int v=edge[i].to;if(v==fa[u][0])continue; dep[v]=dep[u]+1;dis[v]=dis[u]+edge[i].dis;fa[v][0]=u; q.push(v); } } } int Lca(int x,int y){ if(dep[x]<dep[y])swap(x,y); for(int i=0;i<20;i++)if((dep[x]-dep[y])&(1<<i))x=fa[x][i]; if(x==y)return x; for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0]; } void init(){memset(head, -1, sizeof head); edgenum = 0;} int n, m; int main(){ int T, i, j, x, y;scanf("%d",&T); while(T--){ scanf("%d %d",&n,&m); init(); for(i=1;i<n;i++){scanf("%d %d",&x,&y);add(x,y,1);add(y,x,1);} bfs(1); while(m--){ scanf("%d %d",&x,&y); int lca = Lca(x,y); if(lca==y){ int D = dep[x] - dep[y]-1; while(D){ int z = (int)(log10(1.0*D)/log10(2.0)); x = fa[x][z]; D-=1<<z; } printf("%d\n",x); } else printf("%d\n",fa[y][0]); } } return 0; }
相关文章
- python使用单链表节点类
- Java实现 LeetCode 24 两两交换链表中的节点
- json树递归js查询json父子节点
- SQL 语句递归查询 With AS 查找所有子节点
- 自定义ConfigurationSection,创建多个嵌套的ConfigurationElementCollection节点
- kubernetes多节点部署解析
- 理解linux 块, i节点
- SAP Spartacus里unit list tree节点collapse all按钮的实现逻辑
- ML之DL:机器学习领域发展最快的分支【深度学习】的发展史及其重要性节点之详细攻略
- 电力系统潮流计算(牛顿-拉夫逊法、高斯-赛德尔法、快速解耦法)【6节点 9节点 14节点 26节点 30节点 57节点】(Matlab代码实现)
- 基于蜻蜓优化算法的配电网重构求解(Python代码实现)【IEEE123节点算例】
- LabVIEW错误“内存已满 - 应用程序停止在节点”
- Selenium定位class包含空格的元素-复合class节点
- 错误:启动spark后在web页面看不到worker节点的信息
- (B20_01) 查看pb模型的输入输出节点
- ElasticStack----使用Docker方式安装单节点的8.1.3版本的ElasticSearch