luogu3379 最近公共祖先

luogu3379 最近公共祖先

​​ 题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入输出格式

输入格式：

第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。

接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。

输出格式：

输出包含M行，每行包含一个正整数，依次为每一个询问的结果。

输入输出样例

输入样例#1：

5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5 输出样例#1：

4 4 1 4 4 说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=10，M<=10

对于70%的数据：N<=10000，M<=10000

对于100%的数据：N<=500000，M<=500000

样例说明：

该树结构如下：

第一次询问：2、4的最近公共祖先，故为4。

第二次询问：3、2的最近公共祖先，故为4。

第三次询问：3、5的最近公共祖先，故为1。

第四次询问：1、2的最近公共祖先，故为4。

第五次询问：4、5的最近公共祖先，故为4。

故输出依次为4、4、1、4、4。

当年写的神奇的lct做法

#include#define N 550000inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while(ch<='9'&&ch>='0') { x=x*10+ch-'0';ch=getchar(); } return x;}int ans,top,n,m,s;int father[N],child[N][2],rev[N],q[N];bool isroot(int x){ int fa=father[x]; return child[fa][0]!=x&&child[fa][1]!=x;}inline void swap(int &x,int &y){ int t=x;x=y;y=t;}void pushdown(int x){ int l=child[x][0],r=child[x][1]; if (rev[x]){ rev[x]^=1;rev[l]^=1;rev[r]^=1; swap(child[x][0],child[x][1]); }}void rotate(int x){ int y=father[x],z=father[y]; int l=(child[y][1]==x),r=l^1; if (!isroot(y)) child[z][child[z][1]==y]=x; father[child[x][r]]=y;father[y]=x;father[x]=z; child[y][l]=child[x][r];child[x][r]=y;}void splay(int x){ q[++top]=x;int i=x; while (!isroot(i)){ q[++top]=father[i];i=father[i]; } while(top) pushdown(q[top--]); while (!isroot(x)){ int y=father[x],z=father[y]; if (!isroot(y)){ if (child[z][1]==y^child[y][1]==x) rotate(x);else rotate(y); } rotate(x); }}void access(int x){ int y=0;ans=0; while(x!=0){ splay(x);child[x][1]=y;y=x;ans=x; x=father[x]; }}void makeroot(int x){ access(x);splay(x);rev[x]^=1;}void link(int u,int v){ makeroot(u);father[u]=v;}int main(){ freopen("3379.in","r",stdin); freopen("3379.out","w",stdout); n=read();m=read();s=read(); top=0; for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。