两个节点的最近公共祖先_今日排列三21253

两个节点的最近公共祖先_今日排列三21253原题链接题目描述如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。输入格式第一行包含三个正整数 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/169178.html原文链接:https://javaforall.cn

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

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

(0)


相关推荐

  • ps磨皮插件portraiture「建议收藏」

    ps磨皮插件portraiture「建议收藏」相信大家在使用photoshop的时候经常会配合插件来进行修图,而ps磨皮插件portraiture也是大多数人的必备插件,因为当你需要处理人像照片的话,那么磨皮将是必不可少的一个步骤,而该插件正是一个功能强大的磨皮滤镜插件,不仅为用户们提供了强大的磨皮效果,还使用起来十分的简单,无需繁琐的使用步骤,只需要简简单单的设置下磨皮参数再随意的调整下即可快速的帮助用户进行磨皮处理啦,非常方便,所以如果你要用ps的话怎么可以缺少这款ps磨皮插件呢?另外,使用这款插件的时候,你会发现它直接为用户们提供了一个单独的面板

  • 圆周率的前十万亿位_圆周率算到60万亿位

    圆周率的前十万亿位_圆周率算到60万亿位3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644…

  • 整流桥厂家ASEMI的插件整流桥和贴片整流桥型号大全[通俗易懂]

    整流桥厂家ASEMI的插件整流桥和贴片整流桥型号大全[通俗易懂]编辑-Z整流桥厂家ASEMI的整流桥型号琳琅满目,太多的型号很多用户在选型的时候就犯难了,下面是整流桥厂家ASEMI的插件整流桥和贴片整流桥型号大全,给大家做一个类别整理。0.5A-0.8A50V~1000V贴片整流桥堆MBS-4贴片整流桥:MB2S,MB4S,MB6S,MB8S,MB10S,HD02,HD04,HD06,HD08,HD10;MBF-4贴片整流桥:MB2F,MB4F,MB6F,MB8F,MB10F;MBM-4插件整流桥:MB2M,MB4M,MB6M,..

  • 怎么查看数据库端口(sqlserver数据库端口查看)

    more$ORACLE_HOME/db/install/portlist.ini 或者使用netmanager

  • JY02调试-无刷电机驱动芯片[通俗易懂]

    JY02调试-无刷电机驱动芯片[通俗易懂]JY02是国内研制的无刷电机驱动芯片,相比于之前的DRV11873,少了集成的MOSFET,只能通过外部扩展MOSFET驱动芯片和功率管达到功率输出的目的,虽然在电路设计上增加了复杂度,但可以极大的提高电机驱动的输出功率,由于使用了外部的MOSFET,输出功率基本由功率MOSFET的驱动能力决定。JY02是硬件应用,不需要编写驱动固件,内部集成反电动势检测电路,支持’Y’形和三角形电机,支持过流检…

  • STM32F407 + LAN8720A + LWIP 实现TCP服务器

    STM32F407 + LAN8720A + LWIP 实现TCP服务器STM32F407+LAN8720A+LWIP实现TCP客户端环境说明:开发板:某宝买的,STM32F407IGSTM32CUBEMX5.6HALLibVersion1.25(一)配置时钟(二)配置调试串口(三)配置以太网ETH(1)基础配置顺序依次说明:LAN8720A使用的是RMII接口进行配置寄存器自动重连使能MAC地址LAN8720A的物理地址(类似IIC的从设备地址),可配置为0或者1,由LAN8720A的RXER/PHYAD0引脚控制

发表回复

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

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