倍增法求LCA

电玩女神 2022-05-09 05:54 186阅读 0赞

#include <bits/stdc++.h>
    #define rep(i,a,b) for(int i = a; i <= b; ++i)
    #define per(i,a,b) for(int i = a; i >= b; --i)
    const int MAXN = 4E4+5;
    const int MAXDEP = 15;
    struct Edge{ 
    	int v,next;
    } e[2*MAXN];
    using namespace std;
    int f[MAXN][MAXDEP+1];
    int head[MAXN],ecnt;
    int dep[MAXN];
    int n,m,root;
    void dfsDep(int u, int fa){ 
    	for (int i=head[u],v=e[i].v; i; i=e[i].next,v=e[i].v) if (v!=fa) { 
    		dep[v]=dep[u]+1;
    		f[v][0]=u;
    		dfsDep(v,u);
    	}
    }
    inline void addEdg(int u,int v){ 
    	e[++ecnt].v = v; e[ecnt].next = head[u]; head[u] = ecnt;
    }
    inline void lcaInit(){ 
    	rep(i,1,MAXDEP)
    		rep(j,1,40000) f[j][i] = f[f[j][i-1]][i-1];
    }
    inline int lca(int x,int y){ 
    	if (dep[x]<dep[y]) swap(x,y);
    	int d = dep[x]-dep[y];
    	for (int i=0; d; ++i,d>>=1)	if (d&1) x = f[x][i];
    	if (x==y) return x;
    	for (int i=MAXDEP; i>=0; --i) if (f[x][i]!=f[y][i]) x = f[x][i] , y = f[y][i];
    	return f[x][0];
    }
    
    int main(){ 
    
    	int size = 256 << 20; // 256MB 
        char *p = (char*)malloc(size) + size;  
        __asm__("movl %0, %%esp\n" :: "r"(p));	//手动扩系统栈 g++32位
        
    	scanf("%d",&n);
    	rep(i,1,n){ 
    		int u,v;
    		scanf("%d%d",&u,&v);
            if (v!=-1) addEdg(u,v), addEdg(v,u); else root = u;
    	}
    	dfsDep(root,0);
    	lcaInit();
    	scanf("%d",&m);
    	rep(i,1,m){ 
    		int x,y;
    		scanf("%d%d",&x,&y);
    		printf("%d\n",lca(x,y));
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，186人围观）

还没有评论，来说两句吧...

相关阅读

相关最近公共祖先LCA(离线Tarjan+在线倍增+MRQ)

[基础理解][Link 1] [全面][Link 2] [Link 1]: https://blog.csdn.net/my_sunshine26/article/de

约定不等于承诺〃/ 2022年10月11日 12:16/ 0 赞/ 164 阅读

相关【基础练习】【倍增LCA】codevs1503 愚蠢的宠物

题目描述 Description 大家都知道，sheep有两只可爱的宠物（一只叫神牛，一只叫神菜）。有一天，sheep带着两只宠物到狗狗家时，这两只可爱的宠物竟然迷路了……

今天药忘吃喽~/ 2022年08月09日 00:50/ 0 赞/ 159 阅读

相关【基础练习】【倍增LCA】codevs1036 商务旅行题解

题目描述 Description 某首都城市的商人要经常到各城镇去做生意，他们按自己的路线去做，目的是为了更好的节约时间。假设有N个城镇，首都编号为1，商人从首都出发，其

客官°小女子只卖身不卖艺/ 2022年08月09日 00:50/ 0 赞/ 163 阅读

相关【日常学习】【倍增LCA】codevs2370 小机房的树题解

题目描述 Description 小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上

小灰灰/ 2022年08月08日 15:52/ 0 赞/ 153 阅读

相关倍增法求LCA

include <bits/stdc++.h> define rep(i,a,b) for(int i = a; i <= b; ++i) define

电玩女神/ 2022年05月09日 05:54/ 0 赞/ 187 阅读

相关倍增法实现LCA（以HDU - 2586为例）

题目：[点击打开链接][Link 1] 题意：求树上任意两点之间的距离。分析：LCA模板题，这是一棵无根树，把它转化为有根树，再用倍增LCA求出每个结点到根节点的距

Bertha 。/ 2022年05月05日 09:56/ 0 赞/ 177 阅读

相关 [KMP][倍增求LCA]JZOJ 4669 弄提纲

Description 新日暮里中，比冲是一位博学的哲学教授。由于最近要帮学生准备考试，他决定弄个提纲给学生。然而同事van不服气，觉得这样学生就没有了自我思考，便在提纲

Bertha 。/ 2021年12月16日 01:07/ 0 赞/ 264 阅读

相关求公共祖先LCA

树剖： include<bits/stdc++.h> using namespace std; const int N=5e5+10; str

男娘i/ 2021年12月14日 03:45/ 0 赞/ 199 阅读

相关倍增入门

今天看不懂倍增代码，只好学了呀首先倍增，顾名思义就是一倍一倍的增加。举个例子你每次可以跳2的k次方步。现在你要跳到距离7步的地方。跳8步跳过了（不跳）跳4

约定不等于承诺〃/ 2021年11月30日 00:58/ 0 赞/ 261 阅读

相关倍增求LCA

1 include<iostream> 2 include<cstdio> 3 include<cstring> 4 include<cs

青旅半醒/ 2021年10月26日 18:31/ 0 赞/ 268 阅读