思路：lca,求两个最短路的公共长度。公共长度公式为(d(a,b)+d(b,c)-d(a,c))/2。

代码：

#include
     
      using namespace std;#define ll long long #define ls rt<<1,l,m#define rs rt<<1|1,m+1,rconst int INF=0x3f3f3f3f;const int N=1e5+5;const int logn=20;vector
      
       g[N];int anc[logn][N];int deep[N];void dfs(int o,int u){    deep[u]=deep[o]+1;    for(int j=0;j
       
        =0;i--)if(deep[anc[i][u]]>=deep[v])u=anc[i][u];    if(u==v)return u;    for(int i=logn-1;i>=0;i--)if(anc[i][u]!=anc[i][v])u=anc[i][u],v=anc[i][v];    return anc[0][u];}int dis(int u,int v){    int l=lca(u,v);    return deep[u]+deep[v]-2*deep[l];}int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int n,q;    cin>>n>>q;    for(int i=2;i<=n;i++)    {        int a;        cin>>a;        g[a].push_back(i);        g[i].push_back(a);    }     for(int i=0;i
        
         >a>>b>>c;        int d1=(dis(a,b)+dis(b,c)-dis(a,c))/2+1;        int d2=(dis(a,c)+dis(b,c)-dis(a,b))/2+1;        int d3=(dis(a,b)+dis(a,c)-dis(b,c))/2+1;        int ans=max(d1,max(d2,d3));        cout<
         
          <