2014.软院.Problem C. 最近公共祖先

我就是我 2023-07-18 14:12 30阅读 0赞

**题目描述**  
给出一棵有N个节点的有根树TREE（根的编号为1），对于每组查询，请输出树上节点u和v的最近公共祖先。  
最近公共祖先：对于有向树TREE的两个结点u,v。最近公共祖先LCA（TREE u,v）表示一个节点x，满足x是u、v的祖先且x的深度尽可能大。

**输入格式**  
输入数据第一行是一个整数T（1<=T<=100），表示测试数据的组数。  
对于每组测试数据：  
第一行是一个正整数N（1<=N<=100），表示树上有N个节点。  
接下来N-1行，每行两个整数u,v(1<=u,v<=N)，表示节点u是v的父节点。  
接下来一行是一个整数M（1<=M<=1000），表示查询的数量。  
接下来M行，每行两个整数u,v(11<=u,v<=N)，表示查询节点u和节点v的最近公共祖先。

**输出格式**  
对于每个查询，输出一个整数，表示最近公共祖先的编号，

**输入样例**

2
    3
    1 2
    1 3
    1
    2 3
    4
    1 2
    1 3
    3 4
    2
    2 3
    3 4

**输出样例**

1
    1
    3

#include<bits/stdc++.h>
    using namespace std;
    int main() { 
    	int T,N,M;
    	int u,v;
    	int t[105];
    	scanf("%d",&T);
    	while(T--) { 
    		memset(t,0,sizeof(t));
    		scanf("%d",&N);
    		N--;
    		while(N--) { 
    			scanf("%d %d",&u,&v);// u -> v
    			t[v]=u;
    		}
    		cin>>M;
    		while(M--) { 
    			stack<int> s1;
    			stack<int> s2;
    			scanf("%d %d",&u,&v);
    			while(u) { 
    				s1.push(u);
    				u=t[u];
    			}
    			while(v) { 
    				s2.push(v);
    				v=t[v];
    			}
    			int ans=1;
    			while(!s1.empty()&&!s2.empty()&&s1.top()==s2.top()) { 
    				ans=s1.top();
    				s1.pop();
    				s2.pop();
    			}
    			printf("%d\n",ans);
    		}
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，30人围观）

还没有评论，来说两句吧...

相关阅读

相关 2014.软院.Problem C. 最近公共祖先

题目描述给出一棵有N个节点的有根树TREE（根的编号为1），对于每组查询，请输出树上节点u和v的最近公共祖先。最近公共祖先：对于有向树TREE的两个结点u,v。最近

我就是我/ 2023年07月18日 14:12/ 0 赞/ 31 阅读

相关 2014.软院.Problem A.奇偶求和

题目描述：给定N个数，分别求出这N个数中奇数的和以及偶数的和。输入格式第一行为测试数据的组数T（1<=T<=50）。请注意，任意两组测试数据之间是相互独立的。

谁借莪１个温暖的怀抱￠/ 2023年07月18日 14:12/ 0 赞/ 31 阅读

相关 lintcode88. 最近公共祖先

给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。最近公共祖先是两个节点的公共的祖先节点且具有最大深度。样例样例 1: 输入

￡神魔★判官ぃ/ 2023年07月03日 10:40/ 0 赞/ 32 阅读

相关最近公共祖先

> 语言： C++ > > 题目描述 : > > 有一棵无穷大的满二叉树，其结点按根结点一层一层地从左往右依次编号，根结点编号为1。现在有两个结点a，b。请设计一个算法，求

待我称王封你为后i/ 2023年06月13日 14:25/ 0 赞/ 20 阅读

相关 2014.网研院.Problem C. 进程管理

题目描述在操作系统中，进程管理是非常重要的工作，每个进程都有唯一的进程标识（PID）。每个进程都可以启动子进程，此时我们称它为其子进程的父进程，除了PID为0的进程之外，

末蓝、/ 2023年05月28日 11:11/ 0 赞/ 8 阅读

相关最近公共祖先（c++每日一练）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FtYmln

以你之姓@/ 2023年02月17日 05:04/ 0 赞/ 17 阅读

相关最近公共祖先LCA

最近公共祖先（Lowest Common Ancestors，LCA）指有根树中距离两个节点最近的公共祖先。祖先指从当前节点到树根路径上的所有节点。 ![2021042810

蔚落/ 2023年01月17日 08:29/ 0 赞/ 146 阅读

相关 leetcode---236. 二叉树的最近公共祖先(最近公共祖先)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是

矫情吗；*/ 2022年11月28日 00:42/ 0 赞/ 207 阅读

相关 LCA 最近公共祖先

[https://www.cnblogs.com/JVxie/p/4854719.html][https_www.cnblogs.com_JVxie_p_4854719.htm

Myth丶恋晨/ 2022年06月02日 11:37/ 0 赞/ 184 阅读

相关最近公共祖先

对于有根树上的两个节点u, v，最近公共祖先`lca(u, v) = x`，x是u, v的祖先并且深度尽可能大 ![一棵树][1240] 对于这棵树来说`lca(9, 1

喜欢ヅ旅行/ 2022年05月13日 07:56/ 0 赞/ 258 阅读