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


相关推荐

  • ip addr add配置ip_ip helper-address

    ip addr add配置ip_ip helper-addressbroadcastADDRESS—-协议广播地址,可以简写成brd,此外可以简单的在后面加上”+”表示广播地址由协议地址加主机位全置1组成,”-“则表示主机位全置0。例如你的配置:ipaddradd127.0.0.1/8devlobrd+则表示广播地址为127.255.255.255,网络地址(前8位)为127,主机地址(后面的24位)全为1,加起来为广播地址。扩展:ipad…

  • 破解压缩文件密码rarcrack

    破解压缩文件密码rarcrack破解压缩文件密码rarcrack常见的压缩文件格式有ZIP、RAR和7z。这三种格式都支持使用密码进行加密压缩。前面讲过破解ZIP压缩文件,可以使用fcrackzip。对于RAR和7z格式,可以使用rarcrack。该工具也是一款知名的加密压缩文件破解工具,它支持ZIP、RAR和7z三种格式。它采用暴力破解的模式进行破解。同时,用户可以修改破解配置文件,指定密码所使用的字符集和起始密码。…

  • Linux kworker 占用CPU过高

    Linux kworker 占用CPU过高先打开HTOPhtop如何按HK(大写)我们看到Kworker/0:0+events,下面参考下人家的回答什么是kworker?kworker表示进行“工作”(处理系统调用)的Linux内核进程。在进程列表中可以有多个:kworker/0:1在第一个CPU内核上kworker/1:1是一个,在第二个CPU内核上是一个,依此类推。为什么kworker占用您的CPU?…

  • 步入正轨——以客户的视角审视软件交付

    步入正轨——以客户的视角审视软件交付

  • Android ViewPager使用详解

    Android ViewPager使用详解这是谷歌官方给我们提供的一个兼容低版本安卓设备的软件包,里面包囊了只有在安卓3.0以上可以使用的api。而viewpager就是其中之一利用它,我们可以做很多事情,从最简单的导航,到页面菜单等等。那如何使用它呢,与LisstView类似,我们也需要一个适配器,他就是PagerAdapter。看一下api的图片, ViewPager的功能就是可以使视图滑动,就像Lanucher左右滑动那样。分三个步

  • 区块链–Arbitrum Rollup(Layer2)

    区块链–Arbitrum Rollup(Layer2)Arbitrum是OffchainLabs团队开发的以太坊Layer2层扩容方案,可以实现高吞吐量,让开发者以低成本部署、运营智能合约,同时可以保持无需信任的安全性总结:Rollup的主要特点是所有交易数据都记录在链上,也就是说,Arbitrum把关乎安全的部分放在以太坊链上,将实际计算和存储放在链下执行。

发表回复

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

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