首页 > 编程语言 >浅谈图论中树及其相关知识点（树的遍历、直径、最近公共祖先）（c++）

浅谈图论中树及其相关知识点（树的遍历、直径、最近公共祖先）（c++）

时间：2024-07-28 20:54:33浏览次数：15  
标签：知识点 遍历 浅谈 int void c++ fa inline 节点

目录

前言

一.关于树

二.树的遍历

（一）遍历方式

常见遍历

1.DFS遍历

2.BFS遍历

二叉树遍历

1.先序遍历

2.中序遍历

3.后序遍历

（二）例题讲解

1.P1030 [NOIP2001 普及组] 求先序排列

思路

AC代码

 2.P5908 猫猫和企鹅

思路

AC代码

  3.P1395 会议

思路

AC代码

三.树的直径

（一）定义

（二）相关定理

1.证明

2.扩展定理

（三）树的直径求法

1.两次DFS法

2.树形DP法

伪码如下

（四）树的直径的性质

（五）例题讲解

1.SP1437 PT07Z - Longest path in a tree 

思路

AC代码

 2..P2195 HXY造公园

AC代码

 3.P3304 [SDOI2013] 直径

AC代码

四.树链剖分

（一）相关概念

求解伪码：

（二）作用

（三）性质

（四）例题讲解

P3384 【模板】重链剖分/树链剖分

AC代码

 五.最近公共祖先（LCA）

（一）定义

（二）求法

1.树链剖分法

思路

AC代码

 2.倍增法

思路

AC代码

 3.Tarjan法

思路

正确性证明

AC代码

4.欧拉序法

思路

AC代码

（三）复杂度分析

（四）例题讲解

格式化体面

思路

AC代码

前言

近几日在机房听讲，将听课笔记整理下来，希望对你有所帮助

一.关于树

在博客浅谈最小生成树算法（c++）中，树的概念以详细介绍，此处不展开叙述

二.树的遍历

一棵形如下图的图存在多种遍历顺序

（一）遍历方式

常见遍历

对于任意一棵树，都有以下两种遍历顺序：

1.DFS遍历

就是深搜，序列如下 12345678

2.BFS遍历

就是深搜，序列如下 12734856

二叉树遍历

对于一棵二叉树，还有以下三种遍历方法

1.先序遍历

根+左子树先序遍历+右子树先序遍历

序列如下 12345678

2.中序遍历

左子树中序遍历+根+右子树中序遍历

序列如下 32546187

3.后序遍历

左子树后序遍历+根+右子树后序遍历

序列如下 35642871

（二）例题讲解

1.P1030 [NOIP2001 普及组] 求先序排列

题目传送门

思路

由于最近还在学线段树，题目思路或多或少带一点线段树的感觉，见谅

我们考虑对于任何一棵树，它的后序遍历序列的最后一位一定是根

而在中序遍历中，树根正好将树分成了左子树，右子树两部分

所以，我们可以递归左右两棵子树，直到子树只包含一个节点为止

此外，由于题中提及的树是一颗二叉树，所以对于任何一个节点N，它的左子树的根即为2*n，柚子树的根为2*n+1;

存储会相对简洁

AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char a[100010],b[100010];
char tree[400010];
bool st[400010];
inline void build(int num,int l1,int r1,int l2,int r2){
	//printf("%d %d %d %d %d\n",num,l1,r1,l2,r2);
	if(r1<l1)return ;
	st[num]=true;
	tree[num]=b[r2];
	for(int i=l1;i<=r1;i++){
		if(a[i]==tree[num]){
			build(num*2,l1,i-1,l2,l2+i-l1-1);
			build(num*2+1,i+1,r1,l2+i-l1,r2-1);
		}
	}
	return ;
} 
inline void xxbl(int r){
	if(!st[r])return ;
	printf("%c",tree[r]);
	xxbl(r*2);
	xxbl(r*2+1);
}
int main(){
	memset(st,false,sizeof(st));
	int n;
	scanf("%s",a+1);
	scanf("%s",b+1);
	n=strlen(a+1);
	tree[1]=b[n];
	build(1,1,n,1,n);
	xxbl(1);
	puts("");
	//for(int i=1;i<=n*4;i++)cout<<i<<" "<<tree[i]<<endl;
}

 2.P5908 猫猫和企鹅

题目传送门

思路

从1号点开始，BFS搜索，如果距离大与d就continue

AC代码
#include<bits/stdc++.h>
using namespace std;
vector<int>ve[100010];
vector<int>::iterator it;
int st[100010];
int main(){
	memset(st,-1,sizeof(st));
	int n,d;
	scanf("%d%d",&n,&d);
	for(int i=1;i<=n-1;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		ve[a].push_back(b);
		ve[b].push_back(a);
	}
	queue<int >qu;
	qu.push(1);
	st[1]=0;
	int ans=0;
	while(!qu.empty()){
		int a=qu.front();
		//cout<<a<<endl;
		qu.pop();
		for(it=ve[a].begin();it!=ve[a].end();it++){
			int o=*it;
			if(st[o]==-1){
				st[o]=st[a]+1;
				if(st[o]>d)continue;
				ans++;
				qu.push(o);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

  3.P1395 会议

题目传送门

思路

1，暴力+LCA TLE

2.树形DP+DFS

AC代码
#include<cstdio>
#define N 50005
using namespace std;
int d[N],f[N],n,idx,size[N],head[N];
struct Edge{
    int to,nxt;
}edge[N<<1];
void add(int x,int y){
    edge[++idx].to=y;
    edge[idx].nxt=head[x];
    head[x]=idx;
}
void dfs1(int o){
    size[o]=1;
    for(int i=head[o];i;i=edge[i].nxt){
        int to=edge[i].to;
        if(d[to]) continue;
        d[to]=d[o]+1;
        dfs1(to);
        size[o]+=size[to];
    }
}
void dfs(int o,int fa){
    f[o]=f[fa]+n-2*size[o];
    for(int i=head[o];i;i=edge[i].nxt){
        int to=edge[i].to;
        if(to==fa) continue;
        dfs(to,o);
    }
}
int main(){
    scanf("%d",&n);
    for(int x,y,i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        add(x,y);
		add(y,x);
    }
    d[1]=1;
    dfs1(1);
    int maxn=0,idx=1;
    for(int i=1;i<=n;i++) maxn+=d[i];
    maxn-=n;
    f[1]=maxn;
    for(int i=head[1];i;i=edge[i].nxt){
        int to=edge[i].to;
        dfs(to,1);
    }
    for(int i=2;i<=n;i++){
        if(f[i]<maxn) maxn=f[i],idx=i;
    }
    printf("%d %d",idx,maxn);
    return 0;
}

三.树的直径

（一）定义

树的直径是指树中最长的一条简单路径 一棵树可以有多条直径 可以用 DFS 或者树形 DP 在 O ( n ) 时间内求出一棵树的直径

（二）相关定理

从树的某个节点开始DFS（BFS），能遍历到的最远的点一定是树的直径端点

1.证明

反证：记真实的直径是 ( s , t ) ，从 x 开始做 DFS ，到达了最 远的节点 y ，且 y 不是 s 或 t 分三种情况讨论： x 在 ( s , t ) 上、 ( x , y ) 与 ( x , t ) 有重叠路 径、 ( x , y ) 与 ( x , t ) 没有重叠路径

（1）x在（s,t）边上

若：

\left ( x,y \right )\geqslant \left ( x,t \right )

\therefore \left ( s,x \right )+ \left ( x,y \right )\geqslant\left ( s,x \right )+ \left ( x,t \right )

\therefore \left ( s,y \right )\geqslant\left ( s,t \right )

\because \varnothing > \left (s,t \right )

\therefore \left ( s,y\right )=\left ( s,t \right )

所以y为直径端点

（2）(s,y)与(s,t)有相同路径

\because \left (x,y \right )\geq \left (x,t\right )

\therefore \left (s,q \right )+ \left (q,y \right )\geq \left (t,q \right )+ \left (q,x\right )

\therefore \left ( s,y \right )\geqslant\left ( s,t \right )

\because \varnothing > \left (s,t \right )

\therefore \left ( s,y\right )=\left ( s,t \right )

所以y为直径端点

（3）

\because (s,p) or (p,t) \geq \frac{1}{2}(s,t)

(x,q) or (q,y)\geq \frac{1}{2}(x,y)

(x,y)\geq (s,t)

\therefore (x,q)\geq \frac{1}{2}(x,y)\geq \frac{1}{2}(s,t)

(p,t)\geq \frac{1}{2}(s,t)

(p,q)\geq 1

\therefore (x,t)>(s,t)

不符合题意

命题得证

这个定理的限制：树中不允许出现负权边

2.扩展定理

且如果一棵树有多条直径，则这几条直径必定交于一点

（三）树的直径求法

1.两次DFS法

        （1）从1节点开始DFS，找到最远点k

        （2）从k节点开始DFS，找到最远点p，则（k,p），即为所求

2.树形DP法

  对于每个点，我们维护以下三个量

                （1）d1表示最长路径长度

                （2）d2表示次长路径长度

                （3）son最长路径儿子

伪码如下
void dfs(k,f){
    for(v in son(k))dfs(v,k);
    d1[k]=max v in son(k) {d1[v]}+1;
    d2[k]=max v in son(k)!dq[k] {d1[v]}+1;\
}

（四）树的直径的性质

1.从任意点出发，能到达的最远的点，一定是某条直径的端点

2.用一条边将两棵树连接，合成的新树的直径的两端点必定在原来的树中也是直径

（五）例题讲解

1.SP1437 PT07Z - Longest path in a tree 

题目传送门

思路
钦定 1 为树根，对每个节点 k，维护它向子树内延伸的最长 路径 d1，记该最长路径经过 k 的子节点 i，同时维护一个不经过 i 的最长路径 d2（可以看做与最长路径不同方向的次 长路径） 此时树的直径长度就是对于每一个点的 d 1 + d 2 的最大值
AC代码
#include<cstdio>
#include<queue>
using namespace std;
const int N=100010;
int n,d[N];
bool vis[N];
vector<int>ve[N];
int bfs(int s)
{
	for(int i=1;i<=n;i++) d[i]=1e9;
	queue<int>q;
	d[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int v=q.front();
		q.pop();
		for(int i=0;i<ve[v].size();i++)
		{
			int e=ve[v][i];
			if(d[e]>d[v]+1&&e)
			{
				d[e]=d[v]+1;
				q.push(e);
			}
		}
	}
	int nn=0;
	int V=0;
	for(int i=1;i<=n;i++) if(nn<d[i]&&d[i]!=1e9) nn=d[i],V=i;
	return V; 
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v; 
		scanf("%d%d",&u,&v);
		ve[u].push_back(v);
		ve[v].push_back(u);
	}
	int r=bfs(1);
	r=bfs(r);
	printf("%d\n",d[r]);
	return 0;
}

 2..P2195 HXY造公园

题目传送门

AC代码
#include<cstdio>
#include<cstring>
using namespace std;
const int N=3e6+10;
struct edge{
	int to,next;
}map[N];
int n,m,q,fa[N],X,dis[N],st;
int cnt,head[N];
bool vis[N],vis2[N];

 inline int read(){
    char ch=getchar();int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
template<typename T>
inline void write(T x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
 inline void add(int x,int y){
	map[++cnt].to=y;
	map[cnt].next=head[x];
	head[x]=cnt;
}

 inline int find(int x){
 	return fa[x]==x?x:fa[x]=find(fa[x]);
}
 inline void merge(int x,int y){
	int xx=find(x),yy=find(y);
	fa[xx]=yy;
}

 inline void dfs(int x,int val){
	if(X<val) X=val,st=x;
	for(int i=head[x];i;i=map[i].next){
		int y=map[i].to;
		if(!vis[y]){
			vis[y]=true;
			dfs(y,val+1);
		}
	}
	vis[x]=false;
}

 inline void dfs2(int x,int val){
	if(X<val) X=val;
	for(int i=head[x];i;i=map[i].next){
		int y=map[i].to;
		if(!vis[y]){
			vis[y]=true;
			dfs2(y,val+1);
		}
	}
	vis[x]=false;
}

 inline int max(int a,int b){return a>b?a:b;}

int main(){
	n=read(),m=read(),q=read();
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int x=read(),y=read();
		add(x,y),add(y,x);
		merge(x,y);
	}
	for(int i=1;i<=n;i++){
		int x=find(i);
		if(vis2[x]) continue;
		X=-1;
		vis[x]=true;
		dfs(x,0);
		X=-1;
		vis[st]=true;
		dfs2(st,0);
		vis2[x]=true;
		dis[x]=X;
	}
	for(int i=1;i<=q;i++){
		int opt=read(),x=read(),y;
		if(opt==1){
			write(dis[find(x)]);
			printf("\n");
		} 
		else{
			y=read();
			int xx=find(x),yy=find(y);
			if(xx==yy) continue;
			dis[yy]=max(max((dis[xx]+1)/2+(dis[yy]+1)/2+1,dis[xx]),dis[yy]);
			merge(x,y);
		}
	}
	return 0;
}

 3.P3304 [SDOI2013] 直径

题目传送门

AC代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 400010;
const int MAXM = 100010;
const int MAXINT = 2147483647;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int n, m, k;
int ans, tot = 1, cnt;
ll clen, mlen;
int a[N];
int h[N], pre[N];
ll dis[N];
string s;
inline int read() {
    int s = 0, f = 1;
    char ch = getchar();
    while ('0' > ch || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while ('0' <= ch && ch <= '9') {s = (s << 3) + (s << 1) + ch - 48; ch = getchar();}
    return s * f;
}

struct edge {
    int to, ne;
    ll w;
}e[N * 2];

void add(int x, int y, ll w) {
    e[++tot].to = y;
    e[tot].w = w;
    e[tot].ne =h[x];
   h[x] = tot;
    return;
}

void Init() {
    for (int i = 1; i <= n; i++) {
        dis[i] = 1ll << 60;
        pre[i] = 0;
    }
    return;
}

inline int bfs(int s) {
    Init();
    dis[s] = 0;
    pre[s] = 0;
    queue<int> q;
    q.push(s);
    int res = 1;
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i =h[x]; i; i = e[i].ne) {
            int y = e[i].to;
            ll w = e[i].w;
            if (dis[y] != 1ll << 60) continue;
            dis[y] = dis[x] + w;
            pre[y] = i;
            if (dis[y] > dis[res]) res = y;
            q.push(y);
        }
    }
    return res;
}

inline void dfs(int x, int fa) { 
    for (int i =h[x]; i; i = e[i].ne) {
        int y = e[i].to;
        ll w = e[i].w;
        if (y == fa) continue;
        dfs(y, x);
        clen = max(clen, dis[x] + dis[y] + w);
        dis[x] = max(dis[x], dis[y] + w);
    }
    return;
}

inline void dfs1(int x, int fa) {
    for (int i =h[x]; i; i = e[i].ne) {
        int y = e[i].to, w = e[i].w;
        if (y == fa) continue;
        dfs1(y, x);
        dis[x] = max(dis[x], dis[y] + w);
        mlen = max(dis[x], mlen);
    }
    return;
}

int main(){
    int T;
    scanf("%d", &n);
    for (int i = 1, x, y; i < n; i++) {
        ll w;
        scanf("%d%d%lld", &x, &y, &w);
        w *= 1000;
        if (!w) exit(0);
        add(x, y, w);
        add(y, x, w);
    }
    int p = bfs(1);
    int q = bfs(p);
    ll len = dis[q];
    printf("%lld\n", len / 1000);
    int mid, sum = 0;
    for (; pre[q]; q = e[pre[q] ^ 1].to) {
        --e[pre[q]].w;
        --e[pre[q] ^ 1].w;
        sum += e[pre[q]].w;
        if (sum == len / 2) mid = e[pre[q]].to; 
    }
    int ok = 0;
    memset(dis, 0, sizeof(dis));
    dfs1(mid, 0);
    if (mlen == len / 2) ok = 1;
    memset(dis, 0, sizeof(dis));
    dfs(1, 0);
    if (len / 1000 % 2 == 0 && ok) {
        printf("0\n");
    }
    else {
        printf("%lld\n", len - clen);
    }
    return 0;
}

四.树链剖分

常说的树链剖分是重链剖分，除此之外还有长链剖分和实链剖分 重链剖分可以将树上的任意一条路径剖分成 O ( log n ) 条链，每条链的形态是自底向上的 因此对于每条链上的节点，可以做很多在数列上的操作

（一）相关概念

重儿子：一个节点的所有儿子中，子树包含节点最多的那个儿子

轻儿子：不是重儿子就是轻儿子

重链：由重儿子构成的链

第一次 DFS ：求出每个节点的父节点、深度、子树大小和重 儿子（即子树大小最大的儿子）  第二次 DFS：求出每个节点的所在重链的链顶、DFS 序

求解伪码：

void dfs1()size[k];
void dfs2(){
	for(v in son[k])max siz[v]
	hson[k]=v;
}

如图红色部分便为图中的一条重链。

（二）作用

由于链上的 DFN 是连续的，可以用线段树/树状数组维护路径上 的权值和。共有 O(log n) 条链，每条链对线段树/树状数组的影 响是 O(log n) 的，因此总的时间复杂度是 O(log2 n) 维护树上的值

有时会对子树上的值进行操作（子树加、子树求和等），由于子树的 DFN 连续，所以可以在以 DFN 为下标的线段树 / 树状数组上操作。操作前需要预处理得到每个子树的最后一个节点的 DFN 。

（三）性质

1.在重链优先的DFS上，重链上的节点的DFN是连续的

2.两个节点的LCA等于它们所在重链的LCA

3.沿树边向下从k走到v，v子树的大小不超过k子树的一半

4.树上的每一条路径可以被剖分成O(logn)条链

（四）例题讲解

P3384 【模板】重链剖分/树链剖分

题目传送门

AC代码

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define mem(a,b) memset(a,(b),sizeof(a))
#define Temp template<typename T>
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define len (r-l+1)
using namespace std;
typedef long long LL;
template<typename T>
inline void read(T &x)
{
    x=0;char c = getchar();int s = 1;
    while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}
    while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}
    x*=s;
}
template<typename T>
inline void write(T x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=200000+10;
int n,m,r,mod;
int idxx,h[N],ne[N],e[N],w[N],wt[N];
int a[N<<2],laz[N<<2];
int son[N],id[N],fa[N],cnt,dep[N],siz[N],top[N];  
int res=0;
inline void add(int x,int y){
    e[++idxx]=y;
    ne[idxx]=h[x];
    h[x]=idxx;
}

inline void pushdown(int rt,int lenn){
    laz[rt<<1]+=laz[rt];
    laz[rt<<1|1]+=laz[rt];
    a[rt<<1]+=laz[rt]*(lenn-(lenn>>1));
    a[rt<<1|1]+=laz[rt]*(lenn>>1);
    a[rt<<1]%=mod;
    a[rt<<1|1]%=mod;
    laz[rt]=0;
}
inline void build(int rt,int l,int r){
    if(l==r){
        a[rt]=wt[l];
        if(a[rt]>mod)a[rt]%=mod;
        return;
    }
    build(lson);
    build(rson);
    a[rt]=(a[rt<<1]+a[rt<<1|1])%mod;
}

inline void query(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R){res+=a[rt];res%=mod;return;}
    else{
        if(laz[rt])pushdown(rt,len);
        if(L<=mid)query(lson,L,R);
        if(R>mid)query(rson,L,R);
    }
}

inline void update(int rt,int l,int r,int L,int R,int k){
    if(L<=l&&r<=R){
        laz[rt]+=k;
        a[rt]+=k*len;
    }
    else{
        if(laz[rt])pushdown(rt,len);
        if(L<=mid)update(lson,L,R,k);
        if(R>mid)update(rson,L,R,k);
        a[rt]=(a[rt<<1]+a[rt<<1|1])%mod;
    }
}

inline int qRange(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        res=0;
        query(1,1,n,id[top[x]],id[x]);
        ans+=res;
        ans%=mod;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    res=0;
    query(1,1,n,id[x],id[y]);
    ans+=res;
    return ans%mod;
}

inline void updRange(int x,int y,int k){
    k%=mod;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        update(1,1,n,id[top[x]],id[x],k);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    update(1,1,n,id[x],id[y],k);
}

inline int qSon(int x){
    res=0;
    query(1,1,n,id[x],id[x]+siz[x]-1);//子树区间右端点为id[x]+siz[x]-1 
    return res;
}

inline void updSon(int x,int k){//同上 
    update(1,1,n,id[x],id[x]+siz[x]-1,k);
}

inline void dfs1(int x,int f,int deep){
    dep[x]=deep;
    fa[x]=f;
    siz[x]=1;
    int maxson=-1;
    for(int i=h[x];i;i=ne[i]){
        int y=e[i];
        if(y==f)continue;
        dfs1(y,x,deep+1);
        siz[x]+=siz[y];
        if(siz[y]>maxson)son[x]=y,maxson=siz[y];
    }
}

inline void dfs2(int x,int topf){
    id[x]=++cnt;
    wt[cnt]=w[x];
    top[x]=topf;
    if(!son[x])return;
    dfs2(son[x],topf);
    for(int i=h[x];i;i=ne[i]){
        int y=e[i];
        if(y==fa[x]||y==son[x])continue;
        dfs2(y,y);
    }
}

int main(){
    read(n);read(m);read(r);read(mod);
    for(int i=1;i<=n;i++)read(w[i]);
    for(int i=1;i<n;i++){
        int a,b;
        read(a);read(b);
        add(a,b);add(b,a);
    }
    dfs1(r,0,1);
    dfs2(r,r);
    build(1,1,n);
    while(m--){
        int k,x,y,z;
        read(k);
        if(k==1){
            read(x);read(y);read(z);
            updRange(x,y,z);
        }
        else if(k==2){
            read(x);read(y);
            printf("%d\n",qRange(x,y));
        }
        else if(k==3){
            read(x);read(y);
            updSon(x,y);
        }
        else{
            read(x);
            printf("%d\n",qSon(x));
        }
    }
}

 五.最近公共祖先（LCA）

（一）定义

对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u和v的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先。

（二）求法

此处所有求法均解决P3379

【模板】最近公共祖先（LCA）

1.树链剖分法

思路
重链剖分：对于每个节点，将它的重儿子作为同一条链的一 部分，递归处理 重链剖分的性质：两个节点的 LCA 等于它们所在重链的 LCA 求树上节点 x 和 y 的 LCA ： • 比较 top[x] 和 top[y] ，若相同则直接返回 x 和 y 中深度 较小的那个 •   若 top[x] 和 top[y] 不同，则将 x 和 y 中链顶深度较大的 那个上移至 top[x] 和 top[y] 的父节点，返回 1
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=500020,M=1000020;
template<typename T>
inline void read(T &x)
{
    x=0;char c = getchar();int s = 1;
    while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}
    while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}
    x*=s;
}
template<typename T>
inline void write(T x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
int n,m,s;
int h[N],ne[M],e[M];
int idx;
inline void add(int x,int y){
	e[++idx]=y;
	ne[idx]=h[x];
	h[x]=idx;
}

int fa[N],dep[N],siz[N],son[N],top[N];
inline void dfs1(int u){
	son[u]=-1;
	siz[u]=1;
	dep[u]=dep[fa[u]]+1;
	for(int i=h[u];i;i=ne[i]){
		int v=e[i];
		if(v!=fa[u]){
			fa[v]=u;
			dfs1(v);
			siz[u]+=siz[v];
			if(son[u]==-1||siz[v]>siz[son[u]])son[u]=v;
		}
	}
}
inline void dfs2(int u,int t){
	top[u]=t;
	if(son[u]==-1)return;
	dfs2(son[u],t);
	for(int i=h[u];i;i=ne[i]){
		int v=e[i];
		if(v!=son[u]&&v!=fa[u])dfs2(v,v);
	}
}
inline int LCA(int a,int b){
    while(top[a]!=top[b]){
        if(dep[top[a]]>dep[top[b]]){
            a = fa[top[a]];
        }
        else{
            b = fa[top[b]];
        }
    }
    return dep[a]<dep[b]? a:b;
}
int main(){
	int n,m,s;
	read(n),read(m),read(s);
	for(int i=1;i<n;i++){
		int x,y;
		read(x),read(y);
		add(x,y);
		add(y,x);
	}
	dfs1(s);
	dfs2(s,s);
	for(int i=1;i<=m;i++){
		int x, y;
		read(x),read(y);
		write(LCA(x,y));
		printf("\n");
	}
	return 0;
}

 2.倍增法

思路

维护一个数组fa[k][i]，表示从k向上2^k步的父亲

并且 fa[now][i]=fa[fa[now][i-1]][i-1];

只要两个点的祖先不同，就继续往上跳

AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=500010;
template<typename T>
inline void read(T &x)
{
    x=0;char c = getchar();int s = 1;
    while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}
    while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}
    x*=s;
}
template<typename T>
inline void write(T x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
int e[N<<1],ne[N<<1],h[N],idx;
inline void add(int x,int y){
	e[++idx]=y;
	ne[idx]=h[x];
	h[x]=idx;
}
int dep[N],fa[N][25],lg[N];
inline void dfs(int now,int fath){
	fa[now][0]=fath;
	dep[now]=dep[fath]+1;
	for(int i=1;i<=lg[dep[now]];i++)
		fa[now][i]=fa[fa[now][i-1]][i-1];
		for(int i=h[now];i;i=ne[i]){
			int o=e[i];
			if(o!=fath)dfs(o,now);
		}
		
}
inline int LCA(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	while(dep[x]>dep[y])
		x=fa[x][lg[dep[x]-dep[y]]-1];
	if(x==y)return x;
	for(int k=lg[dep[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;
	read(n),read(m),read(s);
	for(int i=1;i<n;i++){
		int x,y;
		read(x),read(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;
		read(x),read(y);
		write(LCA(x,y));
		printf("\n");
	}
	return 0;
}

 3.Tarjan法

tarjan算法之前有写博客讲解

tarjan求LCA是一种离线算法

点这里

思路

初始化并查集，遍历树上所有点

将当前节点k标记为已访问

递归遍历当前节点k的所有子节点v，每个子树递归完成后，用并查集将k和v合并

遍历当前节点k的所有询问，若询问的另一个节点已经被访问过，输出并查集的根

正确性证明

当a就是b的祖先时，LCA（a,b）=a;

否则，必定存在r使得getfa(a)=r,getfa(b)=r,则LCA（a,b）=r

AC代码
#include<iostream>
#include<algorithm>
#include<vector>
#define x first
#define y second
using namespace std;
typedef unsigned long long ll;
const int N = 5e+5+100;
typedef pair<int,int> PII;
int n,m,vis[N],fa[N],lca[N];
vector<int>g[N];
vector<PII>query[N];
ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
int find(int x)  //并查集的find函数
{
    if(fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}
void tarjan(int q)  //q表示当前遍历的节点
{
    vis[q]++;  //标记为1
    for(int t:g[q])  //枚举子节点
    {
        if(!vis[t])  //如果子节点还没有被访问
        {
            tarjan(t);     //遍历子节点
            fa[t] = q;    //合并子节点到当前节点
        }
    }
    for(auto t:query[q])//与q结点有关的询问t.second是问题编号，t.first是询问的另一个结点
    {
        int v = t.x, id = t.y;
        if(vis[v] == 2 && !lca[id])  //如果第id个问题还没有找到lca并且v节点已回溯
        {
            lca[id] = find(v);
        }

    }
    vis[q]++;  //标记为2 表示已回溯
}
int main()
{
    int s;
    cin >> n >> m >> s;
    for(int i = 1; i < n; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i = 1; i <= n; i++) fa[i] = i;

    for(int i = 1; i <= m; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a == b)
        {
            lca[i] = a;
            continue;
        }
        query[a].push_back({b,i});
        query[b].push_back({a,i});
    }
    tarjan(s);
    for(int i = 1; i <= m; i++)
    {
        printf("%d\n",lca[i]);
    }

    return 0;
}

4.欧拉序法

思路

从根节点出发，DFS 遍历树上的所有节点，所经过的所有节点组成的序列

注意：欧拉序中节点是可以多次重复出现的，欧拉序的长度是2n − 1从 u 走到 v 的过程中经过的欧拉序最小的结点就是 LCA ( u , v ) ，从而将这个问题转化为 RMQ 问题
AC代码
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
inline int read(){
    int x=0,s=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')s=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*s;
}
#define maxn 500005
int n,m,s,h[maxn],cnt;
int lg[maxn<<1],first[maxn],f[maxn<<1][20],dep[maxn<<1],val[maxn<<1],tot;//log值；某个点第一次在欧拉序中出现的位置；st表；欧拉序得到的深度；欧拉序得到的值；树的当前位置；
struct node{
    int to,next;
}b[maxn<<1];
void add(int u,int v){//链式前向星存图
    b[++cnt].to=v;
    b[cnt].next=h[u];
    h[u]=cnt;
}
void dfs(int u,int d,int fa){//当前节点；深度；父亲节点
    dep[++tot]=d,first[u]=tot,val[tot]=u;//记录节点第一次出现时欧拉序及深度
    for(int i=h[u];i;i=b[i].next)//从当前节点向下深搜
        if(b[i].to!=fa){
            dfs(b[i].to,d+1,u);
            dep[++tot]=d,val[tot]=u;//返回时记录欧拉序及深度
        }
}
void st(){
    rep(i,2,tot) lg[i]=lg[i>>1]+1;//前期log处理
    rep(i,1,tot) f[i][0]=i;//当前节点向后2的0次方-1得到的最小深度节点是本身
    rep(i,1,lg[tot])
        rep(j,1,tot+1-(1<<i)){//st表处理方式将一个区间分为两个有覆盖的小区间
            int ta=f[j][i-1];
            int tb=f[j+(1<<(i-1))][i-1];
            if(dep[ta]<=dep[tb]) f[j][i]=ta;//根据小区间最小深度更新大区间最小深度
            else f[j][i]=tb;
        }
}
int main(){
    n=read(),m=read(),s=read();
    int x,y;
    rep(i,1,n-1){
        x=read(),y=read();
        add(x,y),add(y,x);
    }
    dfs(s,1,0);//根节点出发得到欧拉序
    st();
    rep(i,1,m){
        x=read(),y=read();
        x=first[x],y=first[y];//求lca必须为第一次写出现的位置
        if(x>y) swap(x,y);//保证x为小值
        int t=lg[y-x+1];
        int ta=f[x][t];
        int tb=f[y-(1<<t)+1][t];
        if(dep[ta]<=dep[tb]) printf("%d\n",val[ta]);
        else printf("%d\n",val[tb]);
    }
    return 0;
}

（三）复杂度分析

 

（四）例题讲解

 P4281 [AHOI2008] 紧急集合 / 聚会

题目传送门

格式化体面
给定一棵 n 个节点的树，共有 m 次询问，每次询问给出三个节 点 x , y , z ，找到一个节点 p ，最小化 dist ( p , x ) + dist ( p , y ) + dist ( p , z ) n , m ≤ 5 e5
思路
证明 p 一定是 x , y , z 中某两个点的 LCA
AC代码
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
long long ans=0;
int fa[500010][25],lg[500010],dep[500010],t;
struct node
{
	int from;
	int to;
	int ne;
}edge[2*500001];
int v[2*500001],tot=0;
void add(int x,int y)
{
	edge[++tot].from=x;
	edge[tot].to=y;
	edge[tot].ne=v[x];
	v[x]=tot;
}
inline int lca(int x,int y)
{
	if(dep[x]<dep[y])		
		swap(x,y);
	while(dep[x]>dep[y])	
	{
		x=fa[x][lg[dep[x]-dep[y]]-1];
	}
	if(x==y)
		return x;
	for(int k=lg[dep[x]];k>=0;k--)		
	{
	    if(fa[x][k]!=fa[y][k])
	    {
	    	x=fa[x][k];
			y=fa[y][k];
	    }
	}
    return fa[x][0];
	
}
inline void dfs(int x,int fath)				
{
	dep[x]=dep[fath]+1;				
	fa[x][0]=fath;
	for(int i=1;(1<<i)<=dep[x];i++)
	{
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(int i=v[x];i;i=edge[i].ne)
		if(edge[i].to!=fath)
			dfs(edge[i].to,x);
}
int n,m;
int a,b,c;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)					
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	for(int i=1;i<=m;i++)
	{
		ans=0;
		scanf("%d%d%d",&a,&b,&c);
		int t1=lca(a,b);					
		int t2=lca(a,c);
		int t3=lca(b,c);
		if(t1==t2)t=t3;
		else if(t1==t3)t=t2;
		else if(t2==t3)t=t1;
		ans=dep[a]+dep[b]+dep[c]-dep[t1]-dep[t2]-dep[t3];		
		printf("%d %lld\n",t,ans);
	}
	return 0;
}

这是我的第八篇文章，如有纰漏也请各位大佬指正

辛苦创作不易，还望看官点赞收藏打赏，后续还会更新新的内容。

标签：知识点,遍历,浅谈,int,void,c++,fa,inline,节点
From： https://blog.csdn.net/2301_79587247/article/details/140682749

相关文章

  • 三种语言实现浮点数二分（C++/Python/Java)
    题目给定一个浮点数......
  • C++ 多态
    多态基本概念多态是C++面向对象三大特性之一多态分为两类静态多态：函数重载和运算符重载属于静态多态，复用函数名动态多态：派生类和虚函数实现运行时多态静态多态和动态多态区别：静态多态的函数地址早绑定——编译阶段确定函数地址动态多态的函数地址晚绑定——运行阶段确......
  • 全网最全最新100道C++面试题：20-40
    前述：本文初衷是为了总结本人在各大平台看到的C++面经，我会在本文持续更新我所遇到的一些C++面试问题，如有错误请一定指正我。新建立了一个收集问答的仓库，欢迎各位小伙伴来更新鸭interview_experience:本仓库初衷是想为大家提供一个便利，全面，准确的面试题学习场地，大家都可以对仓库......
  • C++题解(17) 狐猬编程: 640.线段覆盖
    题目描述在一条数轴上，有N条线段，第i条线段的左端点是s[i]，右端点是e[i]。如果线段有重叠（即使是端点重叠也算是重叠），则输出“impossible”，如果没有重叠则输出“possible”。输入格式输入文件名：640.in多组测试数据。第一行，一个整数G，表示有G组测试数据。1<=G<=10。每组......
  • Win11系统下Yolov8的C++编译环境实践
    Date：2024年1月24日概要说明yolo简介及背景    yolo（YouOnlyLookOnce）是目前一种普及性较高的人工智能目标检测方法，它将目标检测任务重新定义为单一的回归问题，从而实现了从图像像素到边界框坐标和类别概率的直接映射。在业界，Yolo的新应用层出不穷，其需求多样变化、源......
  • C++ 数据结构体解析
    文章目录1.定义结构体2. 访问结构成员3. 结构作为函数参数4. 指向结构的指针5. typedef关键字1.定义结构体C/C++数组允许定义可存储相同类型数据项的变量，但是结构是C++中另一种用户自定义的可用的数据类型，它允许存储不同类型的数据项。结构用于表示一条记......
  • C++和R穿刺针吸活检肿瘤算法模型模拟和进化动力学量化差异模型
    ......
  • C++自学笔记29（多维数组）
    我们在之前的笔记中知道数组解决了重复变量的赋值问题，也知道数组就是指针可以用指针的方式修改内容。现在有一个数组对50个变量赋值a[50],我们有50个这样的数组a[50][50],对于这样的数组我们还有50个a[50][50][50]。这就是一维数组、二维数组、三维数组......我们拿堆上建立......
  • C++自学笔记30（类型双关）
    上栗子#include<iostream>intmian(){inta=50;doublever=a;std::cout<<ver<<std::endl;std::cin.get();}a是一个占据4字节的数据，将a复制给ver并转换为double8个字节。这其中就是隐式的类型转换。第一个是int类型的50，第二个是类型转换后的......
  • 【C++】实验五
    题目：1、五角数被定义为n(3n-1)/2，n=1，2，……，以此类推。因此最初的几个五角数为1,5,12,22，……，请使用下面的函数头编写函数，返回五角数：intgetPentagonaNumber（intn）编写程序，使用这个程序展示前20个五角数，每行打印5个。思路：首先需要编写一个返回五角数的函数，输出20个数需要在主函数......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99