题目链接：

题意：

给出n，q，表示n个点，q次询问，给出2~n这些点的父亲，询问是三个点，问任意两个点走到第三个点的最长公共路径的长度

思路：

lca

方法一： from：q神

1. 要么一个点在另外两个点的链上，这个前面判掉了 

2. 要么构成一个星形，求出这个星形的中心点

　　这里又有两种小情况

　　(1), 一个是有一条链要往上走，两条链往下走

　　(2), 排除掉这个情况之后就是三条链往下走 

方法二：

分别考虑到三个点的最长公共路径长度，取最长

lca(a,b) 与 lca(c,b) 哪一个更深，计算深的那个点与b的距离

如果深度相同，就是说a，c在一颗子树上，那么找到lca(a,c) 计算这个点与b的距离。

就是a，b，c 两两lca中最深的那个到达要到达的点的最大值，因为只有最深的点，才是公共的部分开始的地方。

代码：

代码一：

#include 
     
      using namespace std;typedef long long ll;#define MS(a) memset(a,0,sizeof(a))#define MP make_pair#define PB push_backconst int INF = 0x3f3f3f3f;const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){    ll x=0,f=1;char ch=getchar();    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;}//const int maxn = 1e5+10;const int DEG = 17;vector
      
        e[maxn];int time_tag,in[maxn],out[maxn],dep[maxn];int fa[maxn][DEG];void dfs(int u){    in[u] = ++time_tag;    for(int i=1; i
       
        >=1){        if(d&1) u = fa[u][i];    }    if(u==v) return u;    for(int i=DEG-1; i>=0; i--)        if(fa[u][i] != fa[v][i])            u=fa[u][i],v=fa[v][i];    return fa[u][0];}int dis(int u,int v){    return dep[u]+dep[v]-2*dep[lca(u,v)];}int main(){    int n,q;    scanf("%d%d",&n,&q);    for(int i=2; i<=n; i++){        int p = read();        e[p].push_back(i);    }    dfs(1);    while(q--)    {        int k[3];        for(int i=0;i<3;i++)            scanf("%d",&k[i]);        bool flag=0;        for(int i=0;i<3;i++)        {            int u=k[i],v=k[(i+1)%3],w=k[(i+2)%3],f=lca(u,v);            if((lca(u,w)==w || lca(v,w)==w) && in[w]>=in[f] && in[w]<=out[f])            {                printf("%d\n",max(dis(u,w),dis(v,w))+1);                flag=1;                break;            }        }        if(!flag)        {            flag=0;            for(int i=0;i<3;i++)            {                int u=k[i],v=k[(i+1)%3],w=k[(i+2)%3],f=lca(u,v);                if(in[w]
        
         out[f])                {                    printf("%d\n",max({dis(u,f),dis(v,f),dis(w,f)})+1);                    flag=1;                    break;                }            }        }        if(!flag)        {            int u=k[0],v=k[1],w=k[2],f=lca(u,v);            printf("%d\n",max({dis(u,f),dis(v,f),dis(w,f)})+1);        }    }    return 0;}
        
       
      
     

 代码二：

#include 
     
      using namespace std;typedef long long ll;#define MS(a) memset(a,0,sizeof(a))#define MP make_pair#define PB push_backconst int INF = 0x3f3f3f3f;const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){    ll x=0,f=1;char ch=getchar();    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;}//const int maxn = 1e5+10;const int DEG = 17;vector
      
        e[maxn];int time_tag,in[maxn],out[maxn],dep[maxn];int fa[maxn][DEG];void dfs(int u){    in[u] = ++time_tag;    for(int i=1; i
       
        >=1){        if(d&1) u = fa[u][i];    }    if(u==v) return u;    for(int i=DEG-1; i>=0; i--)        if(fa[u][i] != fa[v][i])            u=fa[u][i],v=fa[v][i];    return fa[u][0];}int dis(int u,int v){    return dep[u]+dep[v]-2*dep[lca(u,v)];}int getans(int a,int b,int c){    int x=lca(a,b);    int y=lca(b,c);    if(dep[x]
        
         dep[y]){        return dis(b,x)+1;    }    else {        int z=lca(a,c);        return dis(z,b)+1;    }}int main(){    int n,q;    scanf("%d%d",&n,&q);    for(int i=2; i<=n; i++){        int p = read();        e[p].push_back(i);    }    dfs(1);    while(q--){        int a,b,c;        cin >> a >> b >> c;        int ans = 0;        ans=max(ans,getans(a,c,b));        ans=max(ans,getans(b,a,c));        ans=max(ans,getans(a,b,c));        cout << ans << endl;    }    return 0;}