10 条题解

  • 11
    @ 2021-10-6 20:41:44

    本题的核心思路：倍增。 如果暴力求LCA，要从两个节点开始，一步一步往根节点方向走，记录路径，再从路径最后（就是根节点）开始比较，比较什么时候后出现不同。代码如下：

    #include<bits/stdc++.h>
using namespace std;

const int MAXN=500000+5;
const int MAXM=500000+5;

int head[MAXN];
int father[MAXN];
bool visited[MAXM];
int bianshu;

struct edge
{
	int v,next;
}g[2*MAXM];

void addedge(int u,int v)
{
	g[++bianshu].next=head[u];
	g[bianshu].v=v;
	head[u]=bianshu;
	return;
}

queue <int> q;
int s;
void bfs()
{
	q.push(s);
	while(!q.empty())
	{
		int ppp=q.front();
		q.pop();
		for(int i=head[ppp];i;i=g[i].next)
		{
			if(!visited[g[i].v])
			{
				visited[g[i].v]=true;
				father[g[i].v]=ppp;
				q.push(g[i].v);
			}
		}
	}
	
}

int path1[MAXN];
int path2[MAXN];
int cntp1,cntp2;
int ans;
int main()
{
	int n,q;
	int uu,vv;
	int a,b;
	int LCA,a1,a2;
	scanf("%d%d%d",&n,&q,&s);
	for(int i=1;i<=n-1;++i)
	{
		scanf("%d%d",&uu,&vv);
		addedge(uu,vv);
		addedge(vv,uu);
	}
	father[s]=s;
	visited[s]=true;
	bfs();
	for(int i=1;i<=q;++i)
	{
		scanf("%d%d",&a,&b);
		for(int j=a;j!=s;j=father[j])
		{
			path1[++cntp1]=j;
		}
		path1[++cntp1]=s;
		for(int j=b;j!=s;j=father[j])
		{
			path2[++cntp2]=j;
		}
		path2[++cntp2]=s;
		while(path1[cntp1--]==path2[cntp2--])
		{
			ans=path1[cntp1+1];
		}
		printf("%d\n",ans);
		memset(path1,0,sizeof(path1));
		memset(path2,0,sizeof(path2));
		cntp1=0;
		cntp2=0;
		ans=0;
	}
	return 0;
}

    然而，暴力的时间和空间复杂度根本无法接受。 我们来思考下面这个问题：我为什么要一个一个跳到根节点呢？ 于是乎，“倍增”就出现了。 定义jump[a][b]数组的意义如下： 编号为a的点往根节点方向走(2^b)次之后的点的编号。 每一次不需要一个一个往根节点方向走，而是采取了一种类似于跳跃的模式。 往根节点方向走（2^0)次，即得到这个点的父亲节点。所以先初始化数组：

    for(int i=1;i<=n;++i)
	{
		jump[i][0]=father[i];
	}//jump初值

    然后，再将jump[i][1] jump[i][2]等求出来。 jump[i][j]可以通过jump[i][j-1]再往根节点方向走j-1次得到。 推得状态转移方程：jump[i][j]=jump[jump[i][j-1]][j-1];

    for(int j=1;j<=30;++j)
	{
		for(int i=1;i<=n;++i)
		{
			jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}//初始化jump数组

    接下来我们要开始求最近公共祖先了。然而，如果节点a深度为16，节点b深度为32，所求得的跳跃次数、路径长度都是不一样的，我们又要记录路径然后从后往前比较。 于是乎，我们想了一个办法：先把a，b跳跃到同一深度，再进行剩下的跳跃。（有更简便写法）

    if(dep[a]>dep[b]) //每次判断是否跳跃(1<<k)次，跳跃到同一深度 
		{
			for(int k=30;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					a=jump[a][k];
				}
			} 
		}
		else if(dep[b]>dep[a]) 
		{
			for(int k=30;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					b=jump[b][k];
				}
			} 
		}//使得a,b位于同一深度

    如果这个时候已经跳到同一个点，即a==b，则直接输出，否则进行我们最后的跳跃。只要jump[i][k]!=jump[j][k]（k取值可以不做限制，因为无意义的那些范围的jump值均会是0）我们就跳跃。跳跃完之后，你会惊奇的发现father[a]==father[b];（可以自己模拟一下）所以我们输出任意一边的father均可。 一些没提到的细节和代码如下：

    #include<bits/stdc++.h>
using namespace std;

const int MAXN=500000+5;
const int MAXM=1000000+5;

int head[MAXN];//链式前向星 

int father[MAXN];//父亲节点 

bool visited[MAXN];

int bianshu;

struct edge//链式前向星 
{
	int v,next;
}g[2*MAXM];//双向边，记得开2倍范围 

void addedge(int u,int v)//链式前向星无权值加边 
{
	g[++bianshu].next=head[u];
	g[bianshu].v=v;
	head[u]=bianshu;
	return;
} 

queue <int> q;//bfs用
 
int dep[MAXN];//每个点的深度 

void bfs(int s,int depth)//求father 
{
	q.push(s);
	dep[s]=depth;
	while(!q.empty())
	{
		int ppp=q.front();
		q.pop();
		for(int i=head[ppp];i;i=g[i].next)//遍历 
		{
			if(!visited[g[i].v])
			{
				visited[g[i].v]=true;
				father[g[i].v]=ppp;
				dep[g[i].v]=dep[ppp]+1;//存储深度，比父亲节点深度大1 
				q.push(g[i].v);
			}
		}
	}
}

int jump[MAXN][35];//定义：j[a][b]为a号点往根节点方向走(1<<b)次后的节点编号 

int main()
{
	int n,q,s;
	int uu,vv;
	int a,b;
	int tmp;//深度差 
	
	scanf("%d%d",&n,&q);//有时候需要读入s 
	s=1; 
	
	for(int i=1;i<=n-1;++i)
	{
		scanf("%d%d",&uu,&vv);
		addedge(uu,vv);
		addedge(vv,uu);
	}//加边 
	
	father[s]=0;//注意：father[根]一定要设为0，否则后面跳跃时出问题 
	visited[s]=true;
	bfs(s,1);//求father数组 
	
	for(int i=1;i<=n;++i)
	{
		jump[i][0]=father[i];
	}//jump初值 
	for(int j=1;j<=30;++j)
	{
		for(int i=1;i<=n;++i)
		{
			jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}//初始化jump数组 
	 
	while(q--)//操作 
	{
		scanf("%d%d",&a,&b);
		
		tmp=(dep[a]>dep[b]?dep[a]-dep[b]:dep[b]-dep[a]);//深度差值 
		
		if(dep[a]>dep[b]) //每次判断是否跳跃(1<<k)次，跳跃到同一深度 
		{
			for(int k=30;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					a=jump[a][k];
					tmp-=(1<<k);
				}
			} 
		}
		else if(dep[b]>dep[a]) 
		{
			for(int k=30;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					b=jump[b][k];
					tmp-=(1<<k);
				}
			} 
		}//使得a,b位于同一深度 
		
		if(a==b)//跳到同一个点，即LCA就是当前的点，需要特判。 
		{
			printf("%d\n",a);
			continue;
		}
		for(int k=30;k>=0;--k)
		{
			if((jump[a][k]^jump[b][k]))//异或符号^在此处等价于！= 符号 
			{
				a=jump[a][k];
				b=jump[b][k];
			}
		}//跳2的k次方次
		 
		printf("%d\n",father[a]);
	}
	return 0;
}

    感谢阅读我这一篇又臭又长的题解。

    • @ 2021-10-15 20:59:27

      好像有一句写错了 求jump[i][1] jump[i][2]的时候 jump[i][j]是要通过jump[i][j-1]再往根节点方向走2（j−1）2^（j-1）次得到

    • @ 2021-10-15 21:00:08

      就是说2的j-1次方 次

    • @ 2023-10-17 20:07:21

      %%%

    • @ 2024-10-23 18:11:13

      @ 试过了代码，TLE了

    • @ 2024-10-23 18:11:34

      试过了代码，TLE了

  • 4
    @ 2022-2-2 17:03:34

    tg重点知识点：LCA

    文件头

    求LCA的基本方式：

    1. 在线法

    代表：倍增，rmq

    这里介绍倍增法。

    先预处理出每一个节点的 2k2^k 级祖先以及深度。

    求LCA时，先让两个节点深度相同，再从大到小枚举 kk ，如果 xx 的 kk 级祖先不等于 yy 的 kk 级祖先就往上跳。

    因为我们跳的是LCA的下一层，所以要输出 xx 的 00 级祖先。

    核心代码：

    vector<int> g[500001];
int n,q;
int depth[500001],f[500001][31];
void dfs(int x, int fa)
{
	depth[x]=depth[fa]+1;
	f[x][0]=fa;
	For(i,1,log2(depth[x])+1)
		f[x][i]=f[f[x][i-1]][i-1];
	For(i,0,g[x].size()-1)
		if(g[x][i]!=fa)
			dfs(g[x][i],x);
}
int lca(int x, int y)
{
	if(depth[y]<depth[x]) swap(y,x);
	while(depth[y]>depth[x]) y=f[y][(int)log2(depth[y]-depth[x])];
	if(x==y) return x;
	ForDown(k,log2(depth[y]),0)
	{
		if(f[x][k]!=f[y][k])
		{
			x=f[x][k],y=f[y][k];
		}
	}
	return f[x][0];
}
signed main()
{
	read(n,q);
	For(i,1,n-1)
	{
		int u,v;
		read(u,v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,1);
	//cout<<"wedrftgyhujikoswerdtfyguh"<<endl;
	while(q--)
	{
		int x,y;
		read(x,y);
		write_with_endl(lca(x,y));
	}
	return 0;
}

    复杂度 O(qlogn)O(qlogn)

    1. 离线法

    代表：tarjan

    把所有询问存下来，然后在回溯时将并查集中当前节点的“父亲”设为它的父节点。然后如果有一个询问的两个点都算过了，从并查集中找结果存进来。最后输出。

    核心代码：

    int n,m,s;
struct Edge
{
    int v,nxt;
}query[1000001];
int head[500001],cnt=0;
vector<int> g[500001];
int lca[1000001];
void add(int x, int y)
{
    query[++cnt]=(Edge){y,head[x]};
    head[x]=cnt;
}

bool used[500001];
int f[500001];
int find(int x)
{
    return f[x]==x ? f[x] : f[x]=find(f[x]);
}
void tarjan(int x)
{
    used[x]=1;
    For(i,0,g[x].size()-1)
    {
        if(used[g[x][i]]) continue;
        tarjan(g[x][i]);
        f[g[x][i]]=x;
    }
    for(int i=head[x];i;i=query[i].nxt)
    {
        if(used[query[i].v])
        {
            lca[i%2+i]=find(query[i].v);
        }
    }
}

int main()
{
    read(n);read(m);read(s);
    For(i,1,n) f[i]=i;
    For(i,1,n-1)
    {
        int u,v;
        read(u);read(v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    For(i,1,m)
    {
        int u,v;
        read(u);read(v);
        add(u,v);
        add(v,u);
    }
    tarjan(s);
    For(i,1,m)
    {
        write(lca[2*i]);
        putchar('\n');
    }
    return0;
}

    复杂度 O(n)O(n)。

    • 3
      @ 2022-5-21 7:46:40

      来点不一样的，用树链剖分求LCA。 先把树剖成链，记录每个点uu所在链的最顶端节点 toputop_u， 每次往上跳即可。

      #include <bits/stdc++.h>
using namespace std;

/***********************

Author : ACgod
Date : 2022/5/21
School : Xiamen No.1 High School of Fujian

***********************/

#define reg register
#define rep(i, a, b) for(register int i = a; i <= b; i ++)
#define pb push_back

vector<int> e[500005];
int n, q;

template <class T> T read() {
  reg T s=0,f=1; reg char ch = getchar();
  while(ch<'0'||ch>'9')ch=getchar();
  while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
  return f*s;
}

int maxson[500005], size[500005];
int top[500005], dep[500005];
int fat[500005];

void dfs1(int u, int fa) {
  dep[u] = dep[fa] + 1;
  fat[u] = fa;
  int sizeofson = 0;
  for(int i = 0; i < e[u].size(); i ++) {
    int to = e[u][i];
    if(to == fa) continue;
    dfs1(to, u);
    size[u] += size[to];
    if(size[to] > sizeofson) {
      maxson[u] = to;
      sizeofson = size[to];
    }
  }
  size[u]++;
}

void dfs2(int u, int topf, int fa) {
  top[u] = topf;
  for(int i = 0; i < e[u].size(); i ++) {
    int to = e[u][i];
    if(to == fa) continue;
    if(maxson[u] == to) {
      dfs2(to, topf, u);
    }
    else dfs2(to, to, u);
  }
}

int lca(int x, int y) {
  if(dep[top[x]] < dep[top[y]]) swap(x, y);
  return top[x] == top[y] ? (dep[x] < dep[y] ? x : y ): lca(fat[top[x]], y);
}

int main() {
  n = read<int>(), q = read<int>();
  rep(i, 1, n - 1) {
    int u, v;
    u = read<int>(), v = read<int>();
    e[u].pb(v), e[v].pb(u);
  }
  dfs1(1, 0);
  dfs2(1, 1, 0);
  rep(i, 1, q) {
    int x, y;
    x = read<int>(), y = read<int>();
    printf("%d\n", lca(x, y));
  }
  return 0;
}
      • 3
        @ 2021-12-5 21:03:51

        倍增法求 LCA 。

        #include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;

int n, q, u, v, fa[500005][20], dep[500005];
std::vector<int> g[500005];

void bfs(int root) {
    memset(dep, 0x3f, sizeof(dep));
    std::queue<int> q;
    dep[0] = 0;
    dep[root] = 1;
    q.push(root);
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        for (int v : g[t]) {
            if (dep[v] > dep[t] + 1) {
                dep[v] = dep[t] + 1;
                q.push(v);
                fa[v][0] = t;
                for (int k = 1; k < 20; k++) {
                    fa[v][k] = fa[fa[v][k - 1]][k - 1];
                }
            }
        }
    }
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) std::swap(a, b);
    for (int k = 19; k >= 0; k--) {
        if (dep[fa[a][k]] >= dep[b]) {
            a = fa[a][k];
        }
    }
    if (a == b) return a;
    for (int k = 19; k >= 0; k--) {
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs(1);
    while (q--) {
        scanf("%d%d", &u, &v);
        printf("%d\n", lca(u, v));
    }
    return 0;
}
        • 1
          @ 2024-9-14 17:58:04

          LCA，最近公共祖先问题。

          给定一颗有根树，若节点 k 既是节点 x 的祖先，又是节点 y 的祖先，则称 k 是 \lbrack x, y \rbrack 的公共祖先。在 \lbrack x, y \rbrack 的所有公共祖先中，深度最大的称为最近公共祖先，记作 LCA⁡(x,y)\operatorname*{LCA}(x, y)。

          LCA⁡(x,y)\operatorname*{LCA}(x, y) 即为节点 x→1x \rightarrow 1 和节点 y→1y \rightarrow 1 的第一个中途交汇点。

          因为讲解倍增，所以这里使用 树上倍增法 求解。

          设 fx,kf_{x, k} 表示从 xx 节点走 2k2^k 步到达的祖先节点，若此节点不存在则设 fx,k=0f_{x, k} = 0；显然，fx,0f_{x, 0} 就是 xx 的父节点。

          神奇小公式：$\text{if } k \in \lbrack 1, \log n \rbrack, f_{x, k} = f_{f_{x, k - 1}, k - 1}$

          要解决这个问题，我们还要求出每个节点的深度，可以使用 dfs 解决。

          在处理 LCA 时，我们以 [x,y]\lbrack x, y \rbrack 中深度较大的开始，先使深度较大的缩短到最接近另一个深度的节点（自己 / 最近的祖先），然后一直向上即可。

          完整代码：

          #include <bits/stdc++.h>
#define int long long
#define il inline
using namespace std;

il int read()
{
    int x = 0;
	char c = getchar();
    while (c < '0')
		c = getchar();
    while (c >= '0')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}    
    return x;
}

int n, m, s;
vector<int> edge[500005];
int lca[500005][25], dep[500005];
void dfs(int x, int fa)
{
    lca[x][0] = fa;
    dep[x] = dep[fa] + 1;
    int now = edge[x].size();
    for (int i = 0; i < now; i++)
    {
        if (edge[x][i] == fa)
			continue;
        dfs(edge[x][i], x);
    }
    return ;
}
void pre()
{
    for (int j = 1; j <= 20; j++)
    {
        for (int i = 1; i <= n; i++)
            lca[i][j] = lca[lca[i][j - 1]][j - 1];
    }
    return ;
}
il int LCA(int x, int y)
{
    if (dep[x] < dep[y])
		swap(x, y);
    for (int i = 20; i >= 0; i--)
    {
        if (dep[lca[x][i]] >= dep[y])
            x = lca[x][i];
    }
    if (x == y)
		return x;
    for (int i = 20; i >= 0; i--)
    {
        if (lca[x][i] != lca[y][i])
            x = lca[x][i], y = lca[y][i];
    }
    return lca[x][0];
}
signed main()
{
    n = read(); m = read(); s = read();
    for (int i = 1; i < n; i++)
    {
    	int x, y;
        x = read(); y = read();
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs(s, 0);
    pre();
    for (int i = 1; i <= m; i++)
    {
    	int x, y;
        x = read(); y = read();
        cout << LCA(x, y) << "\n";
    }
    return 0;
}

          时间复杂度：O(qlog⁡n)O(q \log n)。

          • 1
            @ 2024-6-30 10:43:54

            深度 depdep。

            深度最大的公共祖先。

            1. 先把 xx 的祖先进行标记，再让 yy 一路往上遍历祖先，第一个碰到的被 xx 标记过得祖先即为最近公共祖先，复杂度 O(n)O(n)。
            int LCA(int x, int y) {
	memset(vis, 0, sizeof(vis));
	while (x != 0) {
		vis[x] = 1;
		x = fa[x];
	}
	while (vis[y] == 0) {
		y = fa[y];
	}
	return y;
}
            1. 两个点同时走，移动到一个深度，然后同时往上走，直到碰到的时候，就找到了。
            void dfs(int u) {//深度
	dep[u] = dep[fa[u]] + 1;
	for (int i = head[u]; i != -1; i = E[i].next) {//链式前向星
		int v = E[i].v;
		if (v != fa[u]) {
			fa[v] = u;
			dfs(v);
		}
	}
}

int LCA(int x, int y) {
	if (dep[x] < dep[y]) {
		swap(x, y);
	}
	while (dep[x] > dep[y]) {
		x = fa[x];
	}
	while (x != y) {
		x = fa[x];
		y = fa[y];
	}
	return x;
}
            1. 以二进制的方式往上跳。

            求出 2K≤dep[x]2^K \le dep[x]。

            int K = 0;
while ((1 << (K + 1)) <= dep[x]) {
	K++;
}
for (int i = K; i >= 0; i--) {
	//如果 x 的 2 ^ i 的祖先深度 >= dep[y]，那么就让 x 跳到 2 ^ i 这个祖先的位置。
	
}

            设 len=dep[x]−dep[y]len = dep[x] - dep[y]，那么 lenlen 的二进制下中的 11 的位置就表示 xx 要跳 2i2^i 步，因为方案是唯一的，所以从大到小凑，一定不会错。

            如果 dep[x]+2i≥dep[y]dep[x] + 2^i \ge dep[y]，那么 2i2^i 这一步是必须跳的。

            如果这一步不跳，那就永远不能跳到 dep[y]dep[y]。

            2i>2i−1+2i−2+⋯+202^i > 2^{i - 1} + 2^{i - 2} + \dots + 2^0。

            任意整数都可以被表示成多个不同的二进制幂次数字之和。

            表示方式是唯一的。

            1. 状态：fa[i][j]fa[i][j] 表示 ii 的距离为 2j2^j 的祖先是谁。
            2. 状态转移方程：fa[i][j]=fa[fa[i][j−1]][j−1]fa[i][j] = fa[fa[i][j - 1]][j - 1]。

            ii 的 2j2^j 的祖先其实就是 ii 的 2j−12^{j - 1} 祖先的 2j−12^{j - 1}。

            #include <bits/stdc++.h>
using namespace std;


typedef long long ll;
int n, q, F;
int d[600005];
int fa[600005][25];

int head[600005];
struct Node {
    int v, nex;
} e[12000005]; 
int ecnt;
void add(int u, int v) {
    ecnt++;
    e[ecnt].v = v;
    e[ecnt].nex = head[u];
    head[u] = ecnt;
}

void dfs(int father, int root) {
    d[root] = d[father] + 1;
    fa[root][0] = father;
    for (int i = 1; i <= 19; i++) {
        fa[root][i] = fa[fa[root][i - 1]][i - 1];
    }
    for (int i = head[root]; i != 0; i = e[i].nex) {
        int v = e[i].v;
        if (v != father) {
            dfs(root, v);
        }
    }
    return;
}

int LCA(int x, int y) {
    if (d[x] < d[y]) { 
        swap(x, y);
    }
    for (int i = 19; i >= 0; i--) {
        if (d[fa[x][i]] >= d[y]) {
            x = fa[x][i];
        }
    }
    if (x == y) {
        return x;
    }
    for (int i = 19; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

int main() {
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    dfs(0, 1);
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << LCA(a, b) << "\n";
    }
    return 0;
}
            • -1
              @ 2024-8-18 14:50:42

              #include<bits/stdc++.h> using namespace std;

              const int MAXN=500000+5; const int MAXM=500000+5;

              int head[MAXN]; int father[MAXN]; bool visited[MAXM]; int bianshu;

              struct edge { int v,next; }g[2*MAXM];

              void addedge(int u,int v) { g[++bianshu].next=head[u]; g[bianshu].v=v; head[u]=bianshu; return; }

              queue q; int s; void bfs() { q.push(s); while(!q.empty()) { int ppp=q.front(); q.pop(); for(int i=head[ppp];i;i=g[i].next) { if(!visited[g[i].v]) { visited[g[i].v]=true; father[g[i].v]=ppp; q.push(g[i].v); } } }

              }

              int path1[MAXN]; int path2[MAXN]; int cntp1,cntp2; int ans; int main() { int n,q; int uu,vv; int a,b; int LCA,a1,a2; scanf("%d%d%d",&n,&q,&s); for(int i=1;i<=n-1;++i) { scanf("%d%d",&uu,&vv); addedge(uu,vv); addedge(vv,uu); } father[s]=s; visited[s]=true; bfs(); for(int i=1;i<=q;++i) { scanf("%d%d",&a,&b); for(int j=a;j!=s;j=father[j]) { path1[++cntp1]=j; } path1[++cntp1]=s; for(int j=b;j!=s;j=father[j]) { path2[++cntp2]=j; } path2[++cntp2]=s; while(path1[cntp1--]==path2[cntp2--]) { ans=path1[cntp1+1]; } printf("%d\n",ans); memset(path1,0,sizeof(path1)); memset(path2,0,sizeof(path2)); cntp1=0; cntp2=0; ans=0; } return 0; }

              • -5
                @ 2022-1-22 22:11:04 
                #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct zzz {
    int t, nex;
}e[500010 << 1]; int head[500010], tot;
void add(int x, int y) {
	e[++tot].t = y;
	e[tot].nex = head[x];
	head[x] = tot;
}
int depth[500001], fa[500001][22], lg[500001];
void dfs(int now, int fath) {
	fa[now][0] = fath; depth[now] = depth[fath] + 1;
	for(int i = 1; i <= lg[depth[now]]; ++i)
		fa[now][i] = fa[fa[now][i-1]][i-1];
	for(int i = head[now]; i; i = e[i].nex)
		if(e[i].t != fath) dfs(e[i].t, now);
}
int LCA(int x, int y) {
	if(depth[x] < depth[y]) swap(x, y);
	while(depth[x] > depth[y])
		x = fa[x][lg[depth[x]-depth[y]] - 1];
	if(x == y) return x;
	for(int k = lg[depth[x]] - 1; k >= 0; --k)
		if(fa[x][k] != fa[y][k])
			x = fa[x][k], y = fa[y][k];
	return fa[x][0];
}
int main() {
	int n, m, s = 1; scanf("%d%d", &n, &m);
	for(int i = 1; i <= n-1; ++i) {
		int x, y; scanf("%d%d", &x, &y);
		add(x, y); add(y, x);
	}
	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;
}
                • -7
                  @ 2021-11-6 16:57:08

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

                  输入格式 第一行包含三个正整数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。

                  做这个题之前，刚学了树链剖分，这就用上了，求最近公共祖先（LCA）其实就是用树链剖分后，进行简单的链查询即可（让那两个结点的指针中所处链的顶端结点深度小的（也就是靠下的那条链）的指针不断向上跳啊，跳啊。。。直到两指针在同一条链时返回深度较小的那个指针所指的结点编号（即为LCA）即可）。

                  完整代码：

                  #include #include #include #include #define int long long using namespace std; const int maxn=5e5+5; typedef struct Edge { int next,to; }edg; edg e[maxn<<1]; int n,m,s,cnt,head[maxn<<1];

                  void AddEdge(int u,int v) { e[cnt].to=v; e[cnt].next=head[u]; head[u]=cnt++; }

                  int fa[maxn],son[maxn],depth[maxn],siz[maxn]; void dfs1(int u,int f) { fa[u]=f; depth[u]=depth[f]+1; siz[u]=1; int maxsize=-1; for(int i=head[u];~i;i=e[i].next) { int v=e[i].to; if(v==f) continue; dfs1(v,u); siz[u]+=siz[v]; if(siz[v]>maxsize) { maxsize=siz[v]; son[u]=v; } } }

                  int tim,dfn[maxn],top[maxn]; void dfs2(int u,int t) { dfn[u]=++tim; top[u]=t; if(!son[u]) return; dfs2(son[u],t); for(int i=head[u];~i;i=e[i].next) { int v=e[i].to; if(vfa[u]||vson[u]) continue; dfs2(v,v); } }

                  int query(int x,int y) { while(top[x]!=top[y]) { if(depth[top[x]]<depth[top[y]]) swap(x,y); x=fa[top[x]]; } if(depth[x]>depth[y]) swap(x,y); return x; }

                  signed main() { // ios::sync_with_stdio(false); // cin.tie(0); memset(head,-1,sizeof(head)); scanf("%lld%lld%lld",&n,&m,&s); int N=n-1; while(N--) { int u,v; scanf("%lld%lld",&u,&v); AddEdge(u,v); AddEdge(v,u); } dfs1(s,s); dfs2(s,s); while(m--) { int x,y; scanf("%lld%lld",&x,&y); int ans=query(x,y); cout<<ans<<endl; } }

                  • -20
                    @ 2021-9-21 19:19:45

                    az

                  • 1

                  【模板】最近公共祖先

                  信息

                  ID
                  121
                  时间
                  2000ms
                  内存
                  256MiB
                  难度
                  6
                  标签
                  递交数
                  653
                  已通过
                  191
                  上传者
                  1. 关于
                  2. 联系我们
                  3. 隐私
                  4. 服务条款
                  5. 版权申诉
                  6. Language
                  7. 兼容模式
                  8. 主题
                  2. © 2021-2024 Hydro.ac
                  4. Worker 0 in 1958ms
                  5. Hydro v4.17.3 Professional