题目链接

题目描述

有一棵具有 n 个节点的树，在这棵树上将有 m 次询问。
每次询问将给出三个点：a，b，c，你需要在这三个点中选出两个点作为起点，一个点作为终点，由此得到两条路径，且两条路径不能完全重合。
例如：你可以选择 a，c 作为起点，b 作为终点，从而得到路径 (a,b)，(b,c)。
求选出的两条路径能够得到的最多公共节点数。

解题思路

我们考虑对于一个树，在选取的三个节点中，求出两两对应的三个LCA，此时我们可以找到每个 lca 和终点的距离再比较距离的大小就可以得到结果。其实如果我们仔细想一下，我们只要找到深度最深的 lca 再比较它到每个点的距离就可以了。因为最深的 lca 点一定是会经过两条路径的点。这里给个图帮助大家理解。

这里求 lca 的方法有很多，倍增方法可以，树链剖分方法也可以，我个人用的是树链剖分的方法。

代码示例

#include
#include
#include
#include
#include
using namespace std;
 
const int maxn=2010000;
int n,m,s;
int cnt;
int tot;
int head[maxn];
int dep[maxn];
int fa[maxn];
int top[maxn];
int siz[maxn];
int son[maxn];
int dfn[maxn];
 
struct edge{
    int to;
    int from;
    int nxt;
}e[2*maxn];
 
void add(int x,int y){
    tot++;
    e[tot].to=y;
    e[tot].from=x;
    e[tot].nxt=head[x];
    head[x]=tot;
}
 
void dfs_1(int x,int f){ 
	dep[x]=dep[f]+1; 
	fa[x]=f; 
	siz[x]=1;
	int maxson=-1;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==f) continue;
		dfs_1(y,x);
		siz[x]+=siz[y];
		if(siz[y]>maxson){
			son[x]=y;
			maxson=siz[y];
		}
	}
}
 
void dfs_2(int x,int topf){
	dfn[x]=++cnt;
	top[x]=topf;
	if(!son[x]) return;
	dfs_2(son[x],topf);
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==fa[x]||y==son[x]) continue;
		dfs_2(y,y);
	}
}
 
int get_lca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]swap(x,y);
        x=fa[top[x]];
    } 
    if(dep[x]return x;
    else return y;
}
 
int get_dis(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]swap(x,y);
        ans+=dep[x]-dep[top[x]]+1;
        x=fa[top[x]];
    }
    if(dep[x]1;
    else ans+=dep[x]-dep[y]+1;
    return ans;
}
 
int main(){
    cin>>n>>m;
    int x,y,z;
    int lca;
    for(int i=2;i<=n;i++){
        cin>>x;
        add(x,i);
        add(i,x);
    }
    dfs_1(1,0);
    dfs_2(1,1);
    while(m--){
        cin>>x>>y>>z;
        int lca_1=get_lca(x,y);
        int lca_2=get_lca(x,z);
        int lca_3=get_lca(y,z);
        if(dep[lca_2]>dep[lca_1]) lca_1=lca_2;
        if(dep[lca_3]>dep[lca_1]) lca_1=lca_3;
        cout<<max(get_dis(lca_1,x),max(get_dis(lca_1,y),get_dis(lca_1,z)))<
    }
    return 0;
}