提交时间:2023-12-22 13:54:59

运行 ID: 117177

#include<bits/stdc++.h> using namespace std; int d[100005],f[100005][20],lg[100005]; void dfs(int pos,int fa,vector<int>e[]){ d[pos]=d[fa]+1,f[pos][0]=fa; for(int i=1;i<=lg[d[pos]];i++) f[pos][i]=f[f[pos][i-1]][i-1]; for(int i=0;i<e[pos].size();i++) if(e[pos][i]!=fa)dfs(e[pos][i],pos,e); } void init(int n,int s,vector<int>e[]){ for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1; dfs(s,0,e); } int lca(int u,int v){ if(d[u]<d[v])swap(u,v); while(d[u]>d[v]) u=f[u][lg[d[u]-d[v]]]; if(u==v)return u; for(int i=lg[d[u]];i>=0;i--) if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i]; return f[u][0]; } int dis(int u,int v){ return d[u]+d[v]-2*d[lca(u,v)]+1; } int query(int a,int b,int c){ if((lca(a,b)==a&&lca(a,c)!=a)||(lca(a,b)!=a&&lca(a,c)==a))return 1; if(lca(a,b)==a&&lca(a,c)==a)return dis(a,lca(b,c)); if(lca(a,lca(b,c))==lca(b,c))return min(dis(lca(a,b),a),dis(lca(a,c),a)); return dis(a,lca(b,c)); } int n,q; vector<int>e[100005]; int main(){ cin>>n>>q; for(int i=2,t;i<=n;i++) cin>>t,e[t].push_back(i),e[i].push_back(t); init(n,1,e); for(int i=1,a,b,c;i<=q;i++) cin>>a>>b>>c,cout<<max(max(query(a,b,c),query(b,a,c)),query(c,a,b))<<'\n'; return 0; }