umm 先总结下求 LCA 的几种方法
第一个是倍增 [X]
然后是 tarjan[ ]
还有树剖 [ ]
然后还有个什么, RMQ?[ ]
umm 然后还有约束 RMQ? 大概是优化?[ ]
然后事实上我现在只会倍增求 QAQ
所以先把倍增的写了 QAQ
倍增的就是傻逼无脑做就成了, 感觉都没什么好讲解的呢?
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define rp(i,x,y) for(register ll i=x;i<=y;++i)
- #define my(i,x,y) for(register ll i=x;i>=y;--i)
- const ll N=500000+10,M=500000+10;
- ll n,m,s,fa[N][20],head[N],deep[N],cjk;
- struct tr{ll to,next;}tree[M<<1];
- bool vis[N];
- queue<ll>Q;
- inline ll read()
- {
- char ch=getchar();ll x=0;bool y=1;
- while(ch!='-' && (ch>'9' || ch<'0'))ch=getchar();
- if(ch=='-')y=0,ch=getchar();
- while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
- return y?x:-x;
- }
- inline void add(ll x,ll y){tree[++cjk].to=x;tree[cjk].next=head[y];head[y]=cjk;}
- inline void bfs(ll x)
- {
- Q.push(x);deep[x]=1;fa[x][0]=0;
- while(!Q.empty())
- {
- ll u=Q.front();Q.pop();vis[u]=1;
- for(ll i=head[u];i;i=tree[i].next)
- {
- if(vis[tree[i].to])continue;
- fa[tree[i].to][0]=u;deep[tree[i].to]=deep[u]+1;
- rp(j,1,19)fa[tree[i].to][j]=fa[fa[tree[i].to][j-1]][j-1];
- Q.push(tree[i].to);
- }
- }
- }
- int main()
- {
- n=read();m=read();s=read();
- rp(i,1,n-1){ll t1=read(),t2=read();add(t1,t2);add(t2,t1);}
- bfs(s);
- rp(i,1,m)
- {
- ll x=read(),y=read();
- if(deep[x]<deep[y])swap(x,y);
- my(j,19,0)if(deep[fa[x][j]]>=deep[y])x=fa[x][j];
- if(x==y){printf("%lld\n",x);continue;}
- my(j,19,0)if(fa[x][j]!=fa[y][j])x=fa[x][j],y=fa[y][j];
- printf("%lld\n",fa[x][0]);
- }
- }
- View Code
算了随便港下? 就先读入加边, 然后 bfs 预处理所有祖先, 这个预处理就是先无脑 bfs 然后每次找到一个崽的时候把这个崽的祖宗们用它爹的祖宗们赋值一下就成
然后预处理完之后就依然是倍增基本套路, 先跳到同一高度, 然后一起跳直到跳不动, 这个时候他们的爹就是他们的 LCA 了
over
其他的几种解法大概过几天陆陆续续会学下 qwq 到时候再补上 qwq
来源: http://www.bubuko.com/infodetail-2868007.html