最低公共祖先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/169006.html原文链接:https://javaforall.cn

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

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

(0)


相关推荐

  • 关于pin码破解的原理和reaver参数的解释「建议收藏」

    关于pin码破解的原理和reaver参数的解释「建议收藏」  路由器开启wps功能后,会随机生成一个8位的pin码,通过暴力枚举pin码,达到破解的目的,尤其现在很多路由器默认开启了wps功能。大家可能会想到8位的随机pin码将会有100000000种情况,这要pin到何年何月呀。。。。。。不过接下来讲解一下原理,大家会发现其实没多少种情况,这也是这种攻击方式比较流行的原因。 1.pin码破解的原理:  pin码是由8位纯数字组成的识别码,pin码破解是分三部分进行的,规律是这样的:pin码分为三部分,如图:      前4位为…

  • python屏幕文字识别_python 图片文字识别 可截图识别

    python屏幕文字识别_python 图片文字识别 可截图识别[Python]纯文本查看复制代码importosfromaipimportAipOcrimportkeyboardfromPILimportImageGrabfromtimeimportsleepdefget_reuslt(img_name):a=input(‘是否添加可信度?(建议字多不加)(y/n):’)ifa==’y’:APP_ID=’xxxxxx…

  • COM编程之三 QueryInterface

    COM编程之三 QueryInterface【1】IUnknown接口客户同组件交互都是通过接口完成的。在客户查询组件的其它接口时,也是通过接口完成的。而那个接口就是IUnknown。IUnknown接口的定义包含在Win32SDK中的U

  • 10种用于渗透测试的漏洞扫描工具有哪些_渗透测试和漏洞扫描区别

    10种用于渗透测试的漏洞扫描工具有哪些_渗透测试和漏洞扫描区别漏洞扫描工具是IT部门中必不可少的工具之一,因为漏洞每天都会出现,给企业带来安全隐患。漏洞扫描工具有助于检测安全漏洞、应用程序、操作系统、硬件和网络系统。黑客在不停的寻找漏洞,并且利用它们谋取利益。网络中的漏洞需要及时识别和修复,以防止攻击者的利用。漏洞扫描程序可连续和自动扫描,可以扫描网络中是否存在潜在漏洞。帮助It部门识别互联网或任何设备上的漏洞,并手动或自动修复它。在本文中,我们将介绍市场上可用的十大最佳漏洞扫描工具。1.OpenVAS漏洞扫描工具OpenVAS漏洞扫描器是

  • java基础——java.util.ConcurrentModificationException

    在编写代码的时候,有时候会遇到List里有符合条件的的对象,就移除改对象! 但是这中操作如:使用了 List 的remove,会导致一些很严重的问题!

  • 《前端运维》二、Nginx–3静态资源服务、跨域与其他「建议收藏」

    一、静态资源服务首先,静态资源一般是指客户端发送请求到Web服务器,web服务器从内存中取得相应的文件,返回给客户端,客户端解析并渲染出来。动态资源呢,则是由客户端发起请求,先交由web容器,web

发表回复

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

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