最低公共祖先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)


相关推荐

  • Red Hat Enterprise Linux ISO 全镜像下载

    Red Hat Enterprise Linux ISO 全镜像下载1、iso网盘下载地址:https://wanghualang.pipipan.com/dir/13133650-26232498-a8efb3/2、中国大陆开源镜像站汇总,企业贡献: 搜

  • 51单片机IIC通信协议

    51单片机IIC通信协议/*——————————————————————————*@fileI2C.H*@authorByron(from3900@gmail.com)*@versionV1.0.0*@date05/12/2020*@brief51系列单片机I2C通信协议头文件*——————————————-

  • 软件工程与软件测试_软件工程导论第三版课后答案

    软件工程与软件测试_软件工程导论第三版课后答案1.软件测试基础2.单元测试3.集成测试4. 确认测试5.白盒测试技术6.黑盒测试技术7.调试8.软件可靠性

  • 补码的表示 以及+-0的问题「建议收藏」

    补码的表示 以及+-0的问题「建议收藏」正数的补码是其本身,也就是原码.负数的补码是各位取反后加1.也就是其反码加1.+0的补码就是其原码,也就是说是00000000而已(对于8位来说)-0的补码是其反码加1,其反码是11111111,当然,其反码加1后就是溢出一个进位后,仍然是00000000.问题出现在(+0)和(-0)上,在人们的计算概念中零是没有正负之分的。于是就引入了补码概念。负数的补码就是对反码加一,而正数不…

  • (转)算法帝国:华尔街交易怪兽的核武器缔造史

    (转)算法帝国:华尔街交易怪兽的核武器缔造史算法帝国:华尔街交易怪兽的核武器缔造史华尔街见闻2017-02-01访问量5701980年华尔街的黑客生涯:天时地利http://wallstreetcn.com/node/28758320世纪70年代末期,算法开始进入人们的工作,这一趋势席卷了世界各地的金融市场,标志着华尔街黑客时代已然来临。华尔街逐渐吸引了美国越来越多杰出的数学家和科学家投身于编写交易算法的工作。在布莱克?

  • C语言实现【关机程序】「建议收藏」

    C语言实现【关机程序】「建议收藏」在讲解关机程序前,必须得先知道一个库函数system(“shutdown-s-t60”)和system(“shutdown-a),其中“shutdown-s”表示关机,“shutdown-a”表示取消关机,“-t60”表示延迟60秒;而要使用该库函数就得引头文件#include<stdlib.h>。下面开始实现关机程序了:#include<stdio.h>#include<stdlib.h>#include<string.h>int.

发表回复

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

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