一棵树，q次询问，每次给你三个点a b c，让你把它们选做s f t，问你把s到f +1后，询问f到t的和，然后可能的最大值是多少。
最无脑的想法是链剖线段树……但是会TLE。
LCT一样无脑，但是少一个log，可以过。
正解是分类讨论，
如果t不在lca(s,f)的子树内，答案是dis(lca(s,f),f)。
如果t在lca(s,f)的子树内，并且dep(lca(s,t))>dep(lca(f,t))，答案是dis(lca(s,t),f)；
否则答案是dis(lca(f,t),f)。
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100010
int n,m,ans;
int v[N<<1],next[N<<1],first[N],en;
void AddEdge(int U,int V)
{
v[++en]=V;
next[en]=first[U];
first[U]=en;
}
int fa[N],dep[N],top[N],son[N],siz[N];
int Ls[N],Rs[N],tot;
void dfs(int U)
{
siz[U]=1;
for(int i=first[U];i;i=next[i])
if(v[i]!=fa[U])
{
fa[v[i]]=U;
dep[v[i]]=dep[U]+1;
dfs(v[i]);
siz[U]+=siz[v[i]];
if(siz[v[i]]>siz[son[U]])
son[U]=v[i];
}
}
void df2(int U)
{
Ls[U]=++tot;
if(son[U])
{
top[son[U]]=top[U];
df2(son[U]);
}
for(int i=first[U];i;i=next[i])
if(v[i]!=fa[U]&&v[i]!=son[U])
{
top[v[i]]=v[i];
df2(v[i]);
}
Rs[U]=tot;
}
int lca(int U,int V)
{
while(top[U]!=top[V])
{
if(dep[top[U]]<dep[top[V]])
swap(U,V);
U=fa[top[U]];
}
if(dep[U]>dep[V])
swap(U,V);
return U;
}
const int c[7][4]={{0,0,0,0},{0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},{0,3,1,2},{0,3,2,1}};
int calc(int U,int V){
int tmp=dep[lca(U,V)];
return dep[U]+dep[V]-tmp-tmp+1;
}
int main()
{
int b[4],x;
scanf("%d%d",&n,&m);
for(int i=2;i<=n;++i)
{
scanf("%d",&x);
AddEdge(x,i);
AddEdge(i,x);
}
top[1]=dep[1]=1;
dfs(1);
df2(1);
for(int i=1;i<=m;++i){
int ans=0;
for(int j=1;j<=3;++j){
scanf("%d",&b[j]);
}
for(int j=1;j<=6;++j){
int lcasf=lca(b[c[j][1]],b[c[j][2]]);
if(Ls[b[c[j][3]]]<Ls[lcasf] || Ls[b[c[j][3]]]>Rs[lcasf]){
ans=max(ans,calc(lcasf,b[c[j][2]]));
}
else{
int lcast=lca(b[c[j][1]],b[c[j][3]]);
int lcaft=lca(b[c[j][2]],b[c[j][3]]);
if(dep[lcast]>dep[lcaft]){
ans=max(ans,calc(lcast,b[c[j][2]]));
}
else{
ans=max(ans,calc(lcaft,b[c[j][2]]));
}
}
}
printf("%d
",ans);
}
return 0;
}