仓鼠找sugar(倍增LCA)
发布日期:2021-07-14 01:03:51 浏览次数:48 分类:技术文章

本文共 1823 字,大约阅读时间需要 6 分钟。

传送门

题目描述

小仓鼠的和他的基(mei)友(zi)sugar住在地下洞穴中,每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室(a)到餐厅(b),而他的基友同时要从他的卧室(c)到图书馆(d)。他们都会走最短路径。现在小仓鼠希望知道,有没有可能在某个地方,可以碰到他的基友?

小仓鼠那么弱,还要天天被zzq大爷虐,请你快来救救他吧!

输入

第一行两个正整数n和q,表示这棵树节点的个数和询问的个数。

接下来n-1行,每行两个正整数u和v,表示节点u到节点v之间有一条边。
接下来q行,每行四个正整数a、b、c和d,表示节点编号,也就是一次询问,其意义如上。

输出

对于每个询问,如果有公共点,输出大写字母“Y”;否则输出“N”。

样例

  • Input

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

  • Output

    Y
    N
    Y
    Y
    Y

题解

  • 如果两个仓鼠走的路有交集的话,那么其中一个的LCA一定在另一个路径上。
  • 设a,b的LCA为x,c,d的LCA为y,如果depth[x] > depth[y],x必然在cy或者dy上,即x必然和c、d其中一个点有公共祖先,并且这个点的在x下面;
    同理,如果depth[x] < depth[y],y必然和a、b其中一个有公共祖先,并且这个点在y下面。

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
#include
using namespace std; #define INIT(a,b) memset(a,b,sizeof(a)) const int maxn=1e5+7; int Begin[maxn],fa[maxn][30],lg[maxn],depth[maxn]; struct Edge{
int to,next; }ae[maxn<<1]; int tot=0,n,q; int a,b,c,d; void Add(int x,int y){
ae[tot]=(Edge){y,Begin[x]}; Begin[x]=tot++; } void Dfs(int now,int f){
fa[now][0]=f; depth[now]=depth[f]+1; for(int i=1;(1<
<=depth[now];i++) fa[now][i]=fa[fa[now][i-1]][i-1]; for(int i=Begin[now];~i;i=ae[i].next) if(ae[i].to!=f)Dfs(ae[i].to,now); } int Lca(int x,int y){
if(depth[x]
depth[y]) x=fa[x][lg[depth[x]-depth[y]]-1]; if(x==y) return x; for(int i=lg[depth[x]];i>=0;i--){
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; } return fa[x][0]; } bool Judge(int x,int y){
if(depth[x]
depth[y]) x=fa[x][lg[depth[x]-depth[y]]-1]; if(x==y) return true; return false; } int main(){
INIT(Begin,-1); scanf("%d %d",&n,&q); for(int i=0;i

转载地址:https://blog.csdn.net/cpongo3/article/details/89334353 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Is the Information Reliable?(判负环)
下一篇:Balanced Lineup——RMQ

发表评论

最新留言

关注你微信了!
[***.104.42.241]2024年03月08日 13时57分48秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php tire树,Immutable.js源码之List 类型的详细解析(附示例) 2019-04-21
matlab转差频率控制,转差频率控制的异步电机调速系统的研究 2019-04-21
oracle错误1327,Oracle中的PGA监控报警分析(r11笔记第97天) 2019-04-21
php函数内的循环,PHP 循环列出目录内容的函数代码 2019-04-21
oracle树状排序,Oracle树状结构查询 2019-04-21
深度linux内核升级,深度操作系统 2020.11.11 更新发布:内核升级 2019-04-21
sql 拆解函数_SQL入门50题详解(含知识点讲解及代码运行步骤拆解) 2019-04-21
java和python交互 jni_Python基于pyjnius库实现访问java类 2019-04-21
macbook pro 卸载mysql_MacBook Pro全新重装OS X Yosemite 2019-04-21
已达到计算机的连接数最大值无法再同此远程计算机连接_电脑远程访问已达到计算机的连接数最大值怎么办?解决方法很简单... 2019-04-21
mysql表名长度_JavaWeb之MySQL(一) 2019-04-21
mysql服务器语法_Mysql语法 2019-04-21
pdf 模版 汉字和数字_《吉林大学珠海学院毕业论文(设计)模板》(汉字标题版) .pdf... 2019-04-21
python bottle部署_nginx+uwsgi+bottle python服务器部署 2019-04-21
python双击py一闪_Python脚本在双击.py时无法正常运行 2019-04-21
redis logfile为空_关于Redis(二) 2019-04-21
mysql 设计两个主键都不可重复_程序员面试备战篇:18个经典MySQL面试专题解析(干货分享答案)... 2019-04-21
下列关于python2.x和3.x的区别说法正确_Python 2.x和Python 3.x版本有哪些区别?【面试题详解】... 2019-04-21
git更换_git命令 2019-04-21
hp-ux 查看系统负载_Linux性能调优 | 平均负载的理解和分析 2019-04-21