最低公共祖先java_洛谷是啥

最低公共祖先java_洛谷是啥原题链接题目描述如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。输入格式第一行包含三个正整数 N,M,SN,M,S,分别表示树的结点个数、询问的个数和树根结点的序号。接下来 N-1N−1 行每行包含两个正整数 x, yx,y,表示 xx 结点和 yy 结点之间有一条直接连接的边(数据保证可以构成树)。接下来 MM 行每行包含两个正整数 a, ba,b,表示询问 aa 结点和 bb 结点的最近公共祖先。输出格式输出包含 MM 行,每行包含一个正整数,依次为每一个询问的结果。输入

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题链接

题目描述
如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。

输入格式
第一行包含三个正整数 N,M,SN,M,S,分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 N-1N−1 行每行包含两个正整数 x, yx,y,表示 xx 结点和 yy 结点之间有一条直接连接的边(数据保证可以构成树)。

接下来 MM 行每行包含两个正整数 a, ba,b,表示询问 aa 结点和 bb 结点的最近公共祖先。

输出格式
输出包含 MM 行,每行包含一个正整数,依次为每一个询问的结果。

输入输出样例
输入

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

输出

4
4
1
4
4

题解
Tarjan离线求lca

#include<bits/stdc++.h>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef struct Node * pnode;
const int N = 5e5 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int Mod = 1e9;
vector<PII>query[N];
int fa[N],vis[N],res[N];
int head[N],cnt;
struct Edge{ 

int v,next;
}edge[M];
void add(int u,int v){ 

edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
void init(){ 

for(int i = 0;i < N;i ++)fa[i] = i;
}
int Find(int x){ 

return fa[x] = (fa[x] == x ? x : Find(fa[x]));
}
void Tarjan(int u,int f){ 

vis[u] = true;
for(auto &q : query[u]){ 

int y = q.x,id = q.y;
if(vis[y])res[id] = Find(y);    //如果之前遍历过另一个节点
}
for(int i = head[u];~i;i = edge[i].next){ 

int ver = edge[i].v;
if(ver == f)continue;
Tarjan(ver,u);
fa[ver] = u;
}
}
int main(){ 

memset(head,-1,sizeof head);
init();
int n,m,root,x,y;
cin>>n>>m>>root;
for(int i = 0;i < n - 1;i ++){ 

cin>>x>>y;
add(x,y);
add(y,x);
}
for(int i = 0;i < m;i ++){ 

cin>>x>>y;
query[x].push_back({ 
y,i});
query[y].push_back({ 
x,i});
}
Tarjan(root,-1);
for(int i = 0;i < m;i ++)cout<<res[i]<<endl;
return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169022.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 卷积神经网络和图像识别[通俗易懂]

    卷积神经网络和图像识别[通俗易懂]卷积神经网络与图像识别我们介绍了人工神经网络,以及它的训练和使用。我们用它来识别了手写数字,然而,这种结构的网络对于图像识别任务来说并不是很合适。本文将要介绍一种更适合图像、语音识别任务的神经网络结构——卷积神经网络(ConvolutionalNeuralNetwork,CNN)。说卷积神经网络是最重要的一种神经网络也不为过,它在最近几年大放异彩,几乎所有图像、语音识别领域的…

  • 国内IT公司速查手册

    国内IT公司速查手册可以看到网友们对国内IT公司的评价:)

  • 罗马字符的读音「建议收藏」

    罗马字符的读音「建议收藏」Αα阿尔法alfaΒβ贝塔bitaΓγ伽马gamaΔδ德耳塔dêltaΕε艾普西龙êpsilonΖζ度截塔zitaΗη艾塔yitaΘθ西塔sitaΙι约塔yotaΚκ卡帕kapa∧λ兰布达lamdaΜμ米尤miuΝν纽niuΞξ克西ksaiΟο奥密克戎oumikelong∏π派paiΡρ版若rou…

  • SMO算法最通俗易懂的解释[通俗易懂]

    SMO算法最通俗易懂的解释[通俗易懂]我的机器学习教程「美团」算法工程师带你入门机器学习已经开始更新了,欢迎大家订阅~任何关于算法、编程、AI行业知识或博客内容的问题,可以随时扫码关注公众号「图灵的猫」,加入”学习小组“,沙雕博主在线答疑~此外,公众号内还有更多AI、算法、编程和大数据知识分享,以及免费的SSR节点和学习资料。其他平台(知乎/B站)也是同名「图灵的猫」,不要迷路哦~SVM通常用对偶问题来求解,这…

  • TextMate 激活成功教程

    TextMate 激活成功教程网上google来两个方法,如下:(目的还只是个人学习只用,如果今后用于商业目的,一定支持正版)方法1:关于TextMate的注册这个号称TheMissingEditorfor Mac OSX的编辑器我就不介绍了,我就说说如何注册吧。第一种方法:花39欧元第二种方法:UninstallfirstandInstalagain,justopenthe TextMate unix

  • idea创建springboot父子工程_Springboot框架

    idea创建springboot父子工程_Springboot框架在本系列第一篇文章,我们讲解了如何在IDEA中搭建第一个SpringBoot项目:【SpringBoot】一、创建第一个SpringBoot项目,本篇文章,我们讲解如何在IDEA中搭建SpringBoot的父子Module工程项目1、Module工程项目简介多模块项目,适用于一些比较大的项目,通过合理的模块拆分,实现代码的复用,便于维护和管理。尤其是一些开源框架,也是采用多模块的方式,提供插件集成,用户可以根据需要配置指定的模块。2、创建一个SpringBoot项目就是创

    2022年10月13日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号