• 每日一算,公共祖先问题 　分类 单根,那么 直接 dfs(root) #include<bits/stdc++.h> using namespace std; #define LOACL freopen("in","r",stdin);\ freopen("out","w",stdout); #define FOR(i, a...
每日一算,公共祖先问题
分类 单根,那么 直接 dfs(root)

#include<bits/stdc++.h>
using namespace std;
#define LOACL  freopen("in","r",stdin);\
freopen("out","w",stdout);
#define FOR(i, a, b)  for(int i=(a); i<(b); i++)
#define REP(i, a, b)  for(int i=(a); i<=(b); i++)
#define DOWN(i, a, b) for(int i=(a); i>=(b); i--)
#define sz 1000100
#define demen 21

struct node
{int t,nxt;}e[sz];

void dfs(int rt,int f)
{
d[rt] =d[f]+1;
fa[rt][0] = f;
REP(i,1,20)
fa[rt][i] =fa[fa[rt][i-1]][i-1];
if(e[i].t!=f)
dfs(e[i].t,rt);
}
int lca(int x,int y)
{
if(d[x]<d[y])swap(x,y);

int dre = d[x] - d[y];
DOWN(i,20,0)
if((1<<i)&dre)
x = fa[x][i];
if(x==y)return x;
DOWN(i,20,0)
if(fa[x][i]!=fa[y][i])
x = fa[x][i],y=fa[y][i];
return fa[x][0];
}

int main()
{
//LOACL
ios::sync_with_stdio(false);

cin>>n>>m>>s;
REP(i,1,n-1)
{
cin>>u>>v;

}
dfs(s,0);
REP(i,1,m)
{
cin>>u>>v;

printf("%d\n",lca(u,v));
}
return 0;
}

View Code
多个根 那么就记搜

#include<bits/stdc++.h>
using namespace std;
#define LOACL  freopen("in","r",stdin);\
freopen("out","w",stdout);
#define FASTIO  ios::sync_with_stdio(false);
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define DBG(x) cout<<(#x)<<"="<<x<<endl
#define DBG2(x,y) cout<<(#x)<<"="<<x<<"\t"<<(#y)<<"="<<y<<endl
#define DBG3(x,y,z) cout<<(#x)<<"="<<x<<"\t"<<(#y)<<"="<<y<<"\t"<<(#z)<<"="<<z<<endl

#define FOR(i, a, b)  for(int i=(a); i<(b); i++)
#define REP(i, a, b)  for(int i=(a); i<=(b); i++)
#define DOWN(i, a, b) for(int i=(a); i>=(b); i--)

#define INF 999999999
const int sz = 30000*2;
int n,m,x,y,z,tot,q;
bool vis[sz];
struct node
{
int u,v,w;
}a[sz];
struct edge
{
int v,nxt,w;
}e[sz<<1];
bool cmp(node l ,node r)
{
return l.w>r.w;
}
int getf(int x)
{
if(x!=fa[x])fa[x]=getf(fa[x]);
return fa[x];
}
void add(int u ,int v,int w )
{
}

void krusual()
{
sort(a+1,a+m+1,cmp);
REP(i,1,n) fa[i]=i;
REP(i,1,m)
{
if(getf(a[i].u)!=getf(a[i].v))
{
fa[getf(a[i].u)] = getf(a[i].v);
}
}
}

void dfs(int x)
{
vis[x] = true;
{
int v = e[i].v;
if(vis[v]) continue;
deep[v] =deep[x]+1;
f[v][0] = x;
w[v][0] = e[i].w;
dfs(v);
}
}
int lca (int x,int y)
{

if(getf(x)!=getf(y)) return -1;
int ans=INF;
if(deep[x]<deep[y])swap(x,y);

DOWN(i,20,0)
if(deep[f[x][i]]>=deep[y])
{

ans=min(ans,w[x][i]);
x = f[x][i];
}

if(x==y) return ans;

DOWN(i,20,0)
{
if(f[x][i]!=f[y][i])
{
ans=min(ans,min(w[x][i],w[y][i]));
x=f[x][i],y=f[y][i];
}
}
ans = min(ans,min(w[x][0],w[y][0]));
return ans;

}

int lca1(int x,int y)
{
if(getf(x)!=getf(y)) return -1;
int ans=INF;
if(deep[x]>deep[y]) swap(x,y);
DOWN(i,20,0)
{
if(deep[f[y][i]] >=deep[x])
{
ans = min(ans,w[y][i]);
y=f[y][i];
}
}
if(x==y) return ans;
DOWN(i,20,0)
{
if(f[x][i]!=f[y][i])
{
ans=min(ans,min(w[x][i],w[y][i]));
x=f[x][i],y=f[y][i];
}
}
ans = min(ans,min(w[x][0],w[y][0]));
return ans;
}

int main()
{
LOACL
FASTIO
cin>>n>>m;
REP(i,1,m)
cin>>a[i].u>>a[i].v>>a[i].w;
krusual();

//先 dfs 一下 然后 init lca
REP(i,1,n)
{
if(!vis[i])
{
deep[i]=1;
dfs(i);
f[i][0]=i;
w[i][0]=INF;
}
}

//   REP(i,1,n) DBG3(i,f[i][0],w[i][0]);

REP(j,1,20) REP(i,1,n)
{
f[i][j] =f[f[i][j-1]][j-1];
w[i][j] =min(w[i][j-1],w[f[i][j-1]][j-1]);
}
//REP(i,1,n) DBG3( w[i][0],f[i][0], deep[i]);
cin>>q;
REP(i,1,q)
{
cin>>x>>y;
cout<<lca(x,y)<<endl;
}

return 0;
}

View Code
涉及到一个lca(x,y) 这个函数 的注意事项:
需要的 核心跳转 倍增思想,什么意思呢,记得做填那个神奇算法,硬币分包问题吗?
2^i 会产生对2^(i+1) 影响跳转 ,是不是很神奇,一下子就 砍到了 lg(n) 完全符合算法的思维,n===>lgn 的进化.

转载于:https://www.cnblogs.com/corx/p/8824245.html
展开全文
• LCA是在一棵树上求两个点的最近公共祖先。两个点共同能到达的点，这样的点我们称它为公共祖先，那么两个点共同能到达的第一个点，这样的点我们称它为最近公共祖先 算法内容 前置技能 您需要去了解 邻接表存图 倍增...

学习LCA前提须知
LCA是在一棵树上求两个点的最近公共祖先。两个点共同能到达的点，这样的点我们称它为公共祖先，那么两个点共同能到达的第一个点，这样的点我们称它为最近公共祖先
算法内容
前置技能
您需要去了解 邻接表存图 倍增算法基本原理 高中必修一log函数计算
竞赛需要用到的点
1、LCA常作为思维题的工具，不单独考
2、倍增LCA必加优化，或者可以选择常数更优秀的树剖求LCA
倍增求LCA略讲
考虑常规算法求LCA，我们需要知道当前查找的两个点是否遍历过了同一个点上，若一旦有被两点都遍历到的点，那么当前点就是我们的最近公共祖先。我们现在的问题就是，如何找到这样的点？考虑从路径入手，我们一开始的朴素算法能够想到的就是一个一个往上走，但实际上走的很多点都不会用到，我们考虑一个二分的逆运算，倍增
我们从倍增入手，倍增的基本原理就是，从某一个点（数）出发，进行二的次幂级别的运动，并且判断当前是否满足条件，若不满足再次进行跳跃，每一次跳跃都是上一次跳跃路径长度的 2 倍。那就这样跳？肯定是不行的，因为你不知道何时停止，如果不加限制条件，那么就可能判断整棵树的根节点为它们的最近公共祖先，这肯定是错误的，那如何加限制条件呢？
我们现在的目标很明确，就是用倍增向上跳找到最近公共祖先，那我们应该怎样加限制条件呢？我们可以很轻松得到，当它们在同一深度时，若它们的节点不同，那么肯定是还没到达任何一个公共祖先，那么当我们满足 当前两点同深度，不同点并且不能够再往上跳 的时候，是不是意味着再往上走一个点就是我们的最终答案了呢？答案是肯定的。
那我们就可以开始写代码了
部分代码展现
首先是设变量和邻接表
//#define fre yes

#include <cstdio>
#include <cstring> // memset

const int N = 100005;
int head[N << 1], to[N << 1], ver[N << 1];
int depth[N], f[N][22], lg[N];
// depth代表深度 设f[x][k]的话就是 x点向上走2^k步
// lg就是我们的优化

int tot;
void addedge(int x, int y) {
ver[tot] = y;
}

int main() {
...
}
然后我们需要来一个先将我们的depth数组和f数组起始化的函数，并且加上我们的优化
void dfs(int x, int fa) { //x为当前节点 fa为x的上一个节点
depth[x] = depth[fa] + 1;
f[x][0] = fa;
for (int i = 1; (1 << i) <= depth[x]; i++) {
f[x][i] = f[f[x][i - 1]][i - 1];
//这里是一个推导公式
//x向上走2^i 相当于x向上走2^{i - 1} + 2^{i - 1}
}

for (int i = head[x]; ~i; i = to[i]) {
int v = ver[i];
if(v != fa) {
dfs(v, x);
}
}
}

int main() {
static int n; //n个点
...
for (int i = 1; i <= n; i++) {
lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
}
dfs(root, -1);
...
}
起始化了之后就可以求我们的LCA了
#include <iostream>
int lca(int x, int y) {
if(depth[x] < depth[y]) {
std::swap(x, y);
}

while(depth[x] > depth[y]) {
x = f[x][lg[depth[x] - depth[y]] - 1];
//这样就能让x能跑到y的深度
}

if(x == y) return x; //如果直接相等了 那么x肯定是的最近公共祖先

for (int k = lg[depth[x]] - 1; i >= 0; i--) {
//这里也是一句优化 即跑到顶最少需要多少次2^k
if(fa[x][k] != fa[y][k]) {
//如果不相等 那么满足条件 向上跳
x = fa[x][k];
y = fa[y][k];
}
} return fa[x][0];
}
完整代码
//#define fre yes

#include <cstdio>
#include <cstring>
#include <iostream>

const int N = 500005;
int head[N << 1], ver[N << 1], to[N << 1];
int lg[N], depth[N], f[N][22];

int tot;
void addedge(int x, int y) {
ver[tot] = y;
}

void dfs(int x, int fa) {
depth[x] = depth[fa] + 1;
f[x][0] = fa;
for (int i = 1; (1 << i) <= depth[x]; i++) {
f[x][i] = f[f[x][i - 1]][i - 1];
}

for (int i = head[x]; ~i; i = to[i]) {
int v = ver[i];
if(v != fa) {
dfs(v, x);
}
}
}

int lca(int x, int y) {
if(depth[x] < depth[y]) {
std::swap(x, y);
}

while(depth[x] > depth[y]) {
x = f[x][lg[depth[x] - depth[y]] - 1];
}

if(x == y) return x;

for (int k = lg[depth[x]] - 1; k >= 0; k--) {
if(f[x][k] != f[y][k]) {
x = f[x][k]; y = f[y][k];
}
} return f[x][0];
}

int main() {
static int n, m, s;
scanf("%d %d %d", &n, &m, &s);
for (int i = 1; i < n; i++) {
int x, y;
scanf("%d %d", &x, &y);
}

for (int i = 1; i <= n; i++) {
lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
} dfs(s, 0);

for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d %d", &x, &y);
printf("%d\n", lca(x, y));
} return 0;
}

转载于:https://www.cnblogs.com/Nicoppa/p/11471149.html
展开全文
• LCA是啥呢，LCA就是一棵树里两个节点的最近公共祖先，如下图 2号节点和3号节点的LCA就是1, 5号节点和11号节点的LCA就是2，8号节点和4号节点的lca就是4 那么怎么求LCA呢。首先要建树，然后最容易想到的就是两个...
LCA是啥呢，LCA就是一棵树里两个节点的最近公共祖先，如下图

2号节点和3号节点的LCA就是1, 5号节点和11号节点的LCA就是2，8号节点和4号节点的lca就是4

那么怎么求LCA呢。首先要建树，然后最容易想到的就是两个节点一起向上跳，第一个相遇的节点就是LCA

输入输出格式可参考洛谷P3379 LCA模板题

输入格式：

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

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

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

输出格式：

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

先用邻接表存路径。

void add(int x,int y)
{
to[++cnt]=y;
}

int main()
{
int i,x,y;
for(i=1;i<n;i++)
{
}
return 0;
}

存路径后，我们用dfs建树，把每个节点的深度记录下来

void dfs(int x,int fa)//fa表示父节点编号
{
int i;
f[x]=fa;//f[x]表示x节点的父节点
d[x]=d[fa]+1;
if(to[i]!=fa)
dfs(to[i],x);
}

其次需要先把两个节点跳到同一深度，然后一起往上跳即可

int work(int x,int y)
{
int i;
if(d[x]<d[y])
swap(x,y);
while(d[x]>d[y])
x=f[x];//移动至同一深度
while(x!=y)
x=f[x],y=f[y];
return x;
}

以上就是暴力求LCA，以为能AC吗？？妥妥的TLE！！！

那么为什么Ｔ呢？是因为一次只移动到父亲节点要跳好多次，这样太慢了！

那么怎么才能快点呢？就要用倍增了！设一个grd[x][i]数组表示x节点想上跳2的i次方后的节点。所以i<=log2(n)

这个数组怎么用呢？令d[x]>=d[y]。首先还是要跳到同一深度中，先让x跳2^20次（最大）。假设我们发现深度比y小了，这就表示跳过了，我们再试试跳2^19次，如果还过了，那就再变小。如果发现深度还没到，那就跳呗，接着我们再跳，就该试试跳2^18次了，为什么不能跳两个2^19次呢？这是以为两个2^19次就是2^20次啊，肯定可以不用跳两次相同的。这样跳就能大大减少时间了。

到同一深度后，就是两个点一起往上跳了。我们还是让两个点跳2^20次，如果发现跳完后相同了，就可以确定跳到祖先了，但不一定是最近的，所以我们先不着急跳，接着，试试跳2^19次，如果还是相同，那就再变小，如果不相同，那就跳（跟上面差不多），最后跳完，可以确定x和y再向上跳一次就是LCA了，因为我们跳的时候判定了如果跳之后相同那就不跳。但是注意，当y是x的祖先时，跳到同一深度时x==y已经是LCA了，此时就不用再往上跳了。

举个栗子，还是刚才那张图，我们模拟一下求11和7的LCA

首先移动到同一深度，d[7]=3，d[11]=4，所以我们从2^20次（最大）开始，一直到2^1都不行，所以节点11跳了2^0次跳到了节点6。

接着两个节点一块儿跳，从2^20次，最后还是只能跳2^0次，变成了节点2和节点3，最终再跳一次即节点1就是LCA。

em……这个栗子有点小。。。。。。。

好了，那怎么预处理grd数组呢？我们可以在dfs建树的时候预处理，那么我们可以确定grd[x][0]就是他的爸爸，那么怎么确定grd[x][1]呢？grd[x][1]不就是爸爸的爸爸（爷爷）嘛，所以grd[x][1]=grd [ grd [ x ] [ 0 ] ] [ 0 ]（为了让大家看清楚特意用空格隔开嘿嘿嘿），那么grd[x][2]呢（注意这是爷爷的爷爷，而不是爷爷的爸爸）？爷爷的爷爷不就等于grd [ grd [ x ] [ 1 ] ] [ 1 ]嘛。

以此类推，我们得出grd[x][i]=grd[ grd [ x ] [ i - 1 ] ] [ i - 1 ]。是因为2^(i-1)+2(i-1)=2^i，即往上跳两次2^(i-1)就是往上跳2^i

好了我们再捋一遍思路，邻接表+预处理grd数组+跳到相同深度+一起往上跳，代码如下。

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>

using namespace std;

{
int f=1,x=0;
char c=getchar();
while(!isdigit(c)){if(c=='-')f*=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}

const int N=5e5+5;

{
to[++cnt]=y;
}

void dfs(int x,int fa)
{
int i;
grd[x][0]=fa;//父节点
d[x]=d[fa]+1;
for(i=1;i<21;i++)//其实到本题19就可以了，习惯到20整一点哈哈哈
grd[x][i]=grd[grd[x][i-1]][i-1];//预处理grd数组
if(to[i]!=fa)
dfs(to[i],x);
}

int lca(int x,int y)
{
int i;
if(d[x]<d[y])
swap(x,y);
for(i=20;i>=0;i--)//从大到小枚举
if((1<<i)<=d[x]-d[y])//1<<i就是2^i,也可以预处理成数组
x=grd[x][i];
if(x==y)
return x;//当y是x的祖先时
for(i=20;i>=0;i--)
if(grd[x][i]!=grd[y][i])
x=grd[x][i],y=grd[y][i];//一起往上跳
return grd[x][0];//返回父节点
}

int main()
{
int i,j,x,y;
for(i=1;i<n;i++)
{
}
dfs(s,0);//预处理
for(i=1;i<=m;i++)
{
printf("%d\n",lca(x,y));
}
return 0;
}

当然，遇到相应的题可再加数组，比如有时可定义dis[x][i]表示x节点向上跳2^i的距离（权），或者表示最大最小值等。
展开全文
• 这道题很明显的LCA了 一般求LCA方法 先建树,求U,VU,VU,V的...在1的基础上改进,引入了一个预处理好的表来记录往上跳20,21,22...2k2^0,2^1,2^2...2^k20,21,22...2k步的祖先 需要先dfsdfsdfs把这个表预处理出来
这道题很明显的LCA了

一般求LCA方法

先建树,求$U,V$的$LCA$
如果$U和V$深度不相同,先把深的那个点向上爬到同一层
如果已经跳到相同层了,就$U,V$一起向上跳,直到$U==V$

2. 倍增求LCA $O(nlogn)$

在1的基础上改进,引入了一个预处理好的表来记录往上跳$2^0,2^1,2^2...2^k$步的祖先
需要先$dfs$把这个表预处理出来(可以在建树的时候就预处理出跳表)

void dfs_build(vector<string>& mtx, int u, int father) {
vis[u] = true;
level[u] = level[father]+1;          //更新当前递归到的点的深度
up[u][0] = father;                   //向上跳2^0=1,就是跳到爹上

for(int i=1; (1<<i)<=level[u]; i++)  //2^j = (2^j-1) + 2^(j-1)
up[u][i] = up[up[u][i-1]][i-1];

for(int i=0; i<n; i++) {
int v = i;
if(v == u || vis[v] || mtx[u][v] == '0') continue ;
fa[v] = u;                      //建立父子关系
dfs_build(mtx, v, u);
}
}

求LCA
int lca(int u, int v) {
if(level[u] > level[v]) swap(u, v);
for(int i=L; i>=0; i--)
if(level[u] <= level[v]-(1<<i))
v = up[v][i];
if(u == v) return u;
for(int i=L; i>=0; i--)
if(up[u][i] == up[v][i]) continue ;
else {
u = up[u][i];
v = up[v][i];
}
return up[u][0];
}


3. Tarjan求LCA (离线算法)

不会

本题代码
#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN (2048)
#define ll long long
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#define show(x...) \
do { \
cout << "\033[31;1m " << #x << " -> "; \
err(x); \
} while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO {

char print_f[105];
void print() { putchar('\n'); }

template <typename T, typename... T2>
inline void read(T &x, T2 &... oth) {
x = 0;
char ch = getchar();
ll f = 1;
while (!isdigit(ch)) {
if (ch == '-') f *= -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - 48;
ch = getchar();
}
x *= f;
}
template <typename T, typename... T2>
inline void print(T x, T2... oth) {
ll p3=-1;
if(x<0) putchar('-'), x=-x;
do{
print_f[++p3] = x%10 + 48;
} while(x/=10);
while(p3>=0) putchar(print_f[p3--]);
putchar(' ');
print(oth...);
}
} // namespace FastIO
using FastIO::print;

int n, m, Q, K;
#if 0 //非倍增的普通求LCA
bool vis[MAXN];
int level[MAXN], fa[MAXN];                  //fa[i]表示i的父节点

#define cls(x) (memset(x, false, sizeof(x)))

class Solution {
public:
int n;

void init(vector<string>& mtx) {
n = mtx.size();
cls(level), cls(fa), cls(vis);
}

void dfs_build(vector<string>& mtx, int u, int dep) {
vis[u] = true;
level[u] = dep;                     //更新当前递归到的点的深度
for(int i=0; i<n; i++) {
int v = i;
if(v == u || vis[v] || mtx[u][v] == '0') continue ;
fa[v] = u;                      //建立父子关系
dfs_build(mtx, v, dep+1);
}
}

int getSplitNode(vector<string>& mtx, int u, int v) {
init(mtx);
dfs_build(mtx, 0, 0);               //先dfs建树

int lu = level[u], lv = level[v];

while(lu < lv)                      //把u和v爬到同一层
lv = level[fa[v]], v = fa[v];
while(lv < lu)
lu = level[fa[u]], u = fa[u];

while(u != v)                       //u和v一起向上爬
u = fa[u], v = fa[v];
return u;
}
};

#else  //倍增求LCA

#define L (20)
bool vis[MAXN];
int level[MAXN], fa[MAXN];                  //fa[i]表示i的父节点
int up[MAXN][L+5];                            //跳表

#define cls(x) (memset(x, false, sizeof(x)))

class Solution {
public:
int n;

void init(vector<string>& mtx) {
n = mtx.size();
cls(level), cls(fa), cls(vis), cls(up);
}

void dfs_build(vector<string>& mtx, int u, int father) {
vis[u] = true;
level[u] = level[father]+1;          //更新当前递归到的点的深度
up[u][0] = father;                   //向上跳2^0=1,就是跳到爹上

for(int i=1; (1<<i)<=level[u]; i++)  //2^j = (2^j-1) + 2^(j-1)
up[u][i] = up[up[u][i-1]][i-1];

for(int i=0; i<n; i++) {
int v = i;
if(v == u || vis[v] || mtx[u][v] == '0') continue ;
fa[v] = u;                      //建立父子关系
dfs_build(mtx, v, u);
}
}

int lca(int u, int v) {
if(level[u] > level[v]) swap(u, v);
for(int i=L; i>=0; i--)
if(level[u] <= level[v]-(1<<i))
v = up[v][i];
if(u == v) return u;
for(int i=L; i>=0; i--)
if(up[u][i] == up[v][i]) continue ;
else {
u = up[u][i];
v = up[v][i];
}
return up[u][0];
}

int getSplitNode(vector<string>& mtx, int u, int v) {
init(mtx);
#if 0
fori(0, n-1)
forj(0, n-1)
if(mtx[i][j] == '1') printf("%d %d\n", i, j);
#endif
dfs_build(mtx, 0, 0);               //先dfs建树
#if 0
forarr(level, 0, n-1, "level");
forarr(fa, 0, n-1, "fa   ");
#endif
return lca(u, v);
}
};

#endif

#if 1
int main() {
#ifdef debug
freopen("test", "r", stdin);
// freopen("out_main", "w", stdout);
clock_t stime = clock();
#endif

vector<string> mtx = {
"0110000000","1000101000","1001000000","0010000000","0100000101",
"0000001000","0100010010","0000100000","0000001000","0000100000"
};
Solution s;
int U = 6, V = 7;
cout << s.getSplitNode(mtx, U, V);

#ifdef debug
clock_t etime = clock();
printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif
return 0;
}

#endif




展开全文
• 解题思路:这是一道比较标准的最近公共祖先的模板题，所以就根据这道题总结一下这类算法，做这道题采用的方法是倍增法，思路如下 1.建图完成后，我们根据从其中任意点开始标记层次，最近公共祖先的原理就是根据...
• 最近公共祖先 LCA 倍增算法倍增算法可以在线求树上两个点的LCA，时间复杂度为nlogn预处理：通过dfs遍历，记录每个节点到根节点的距离dist[u]，深度d[u]init()求出树上每个节点u的2^i祖先p[u][i]求最近公共祖先，根据...
• LCA 最近公共祖先倍增算法） 首先了解一下我们 最近公共祖先 E和G的LCA为A L和J的LCA为D K和F的LCA为B 然后 倍增 用到了二进制和 dp 的思想 倍增 就是 1 2 4 8 16 …任何一个数 都是可以右 这些数相加得到的。...
• 模板题是这个样子的：给你一颗有根树，每次查询两个节点的最近公共祖先。 &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;最近公共祖先为何物？简单来说，就是两点间的路径中深度最小的那个节点。 &...
• 描述：倍增法用于很多算法当中，通过字面意思来理解就是翻倍增加嘛，...LCA是啥呢 在一棵树当中 lca表示的是两个节点最近公共祖先， 大家看这课树哈节点5 ，3的lca就是1，13和11的LCA就是6。节点8,12的lca就是8...
• lac即最近公共祖先，u和v最近公共祖先就是两节点公用的祖先中深度最大的 比如 其中 lca(1,2)=4, lca(2,3)=4, lca(3,5)=1, lca(2,5)=4; 如何求LCA？ 树上倍增版： 预处理每一个节点的深度depth[i]; 选定两节点; 将...
• 通常在OI中最近公共祖先的解决办法分为在线做法和离线做法，离线做法也就是Tarjan算法，而在线做法则是倍增做法。========================================= Tarjan做法：利用并查集优越的时空复杂度，我们可以...
• 最近公共祖先有多种算法 如倍增，RMQ，树链剖分等这里先介绍倍增算法 预处理复杂度nlog(n); 询问复杂度log(n);倍增与二进制息息相关 与分块的算法有些相似之处使用倍增算法时开一个fa[n][S]数组 fa[i][j] 表示 ...
• 最近公共祖先, 树上倍增,LCA, fa [ i ] [ j ] 表示 i 节点向上 2j 的祖先 很像dp, k 属于 [ 1 , log ( n ) ] ,f [ x ][ k ] = f [ f [ x ] [ k-1 ]] [k-1] 算lca时, 先不妨设 d [ x ] >= d [ y ] 二进制...
• 注意是最近公共祖先。 #include #include #include #include #include using namespace std; const int maxN=20+2; int anc[1005][25]; vector <int > tree[1005]; int deep[1005],n; void dfs...
• --i){//跳到最近公共祖先的下一层 if(father[u][i] != father[v][i]){ u = father[u][i]; v = father[v][i]; } } return father[u][0]; } int main(){ scanf("%d%d%d", &n, &m, &s); int x, y; for...
• 【简介】 解决LCA问题的倍增法是一种基于倍增思想的在线算法。... 对于每个节点u , ancestors[u][k] 表示 u 的第2k个祖先是谁。很容易就想到递推式：ancestors[j][i]=ancestors[ancestors[j][i-1]][i...
• 最近公共祖先（LCA) 倍增优化 定义 最近公共祖先（Lowest Common Ancestor）：两个节点的公共祖先节点中离根最远（即深度最深）的节点。 性质 uuu是vvv的祖先，当且仅当LCA(u,v)=uLCA(u,v)=uLCA(u,v)=u 如果uuu不为...
• //循环过程中不加判断可能会超过最近公共祖先，所以跟新到lca的儿子节点即可 return dp[u][0]; } int main() { int n,m,u,v; scanf("%d %d",&n,&m); cnt=0; memset(head,-1,sizeof(head)); for(int i=1; i; +...
• 洛谷 P3379 【模板】最近公共祖先倍增LCA） 题解： 一道LCA的模板题，用倍增LCA来做再合适不过了~时间复杂度为O(nlogn) 倍增的思想可以用在很多地方，这里就说说如何用倍增来解决LCA的问题吧~ 自己画的图比较丑 ....
• 如图，3和5的最近公共祖先是1，5和2的最近公共祖先是4 在本篇中我们先介绍一下倍增算法 我们需要一个数组de[i]来表示每一个节点i的深度，用另一数组parent[i][j]来表示每一节点j向上走2的i次方是哪个节点 我们...
• 给出一颗二叉树的后序遍历和中序遍历，你能计算出两个结点的最近公共祖先吗？ 输入格式: 第一行给出两个整数N(N<=10000)和M(M<=10000)，分别代表二叉树的结点数和我们接下来的询问数。 第二行和第三行分别给出...
• 最近公共祖先LCA(倍增) 给定一棵 以 sss 为根节点，共有 nnn 个点的树。 有 mmm 次查询 任意两点 u,vu ,vu,v 的最近公共祖先 一、前置知识点 1.邻接链表 存图 2.倍增原理 ( 2n2^n2n 的预处理应用 ) 二、算法流程 1...
• 输入格式 第一行输入一个整数 n（2≤n≤10,000），表示树上有 n 个节点。...（1≤q≤1,000） 接下来的 q 行，每行输入俩个整数 c，d（1≤c,d≤n）代表询问 c，d 俩个节点的最近公共祖先。 输出格式 对于每次...

...