D. Misha, Grisha and Underground(LCA+求解重叠路径)

$考虑给定a,b,c,其中c为终点,如何求ac和bc的重叠路径呢?$

$令dis(q,w)表示q和w的距离$

$那么重叠路径是(\ dis(a,c)+dis(b,c)-dis(a,b)\ )/2$

$假如a和b分别在c的两侧,显然dis(a,c)+dis(b,c)=dis(a,b),满足$

$若在同一侧,dis(a,b)表示的是到公共点前的路径$

$减去除以2即可$

$求dis用lca来实现$

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
struct p{int to,nxt;
}d[maxn]; int head[maxn],cnt=1,n,q;
void add(int u,int v){d[cnt]=(p){ v,head[u] },head[u]=cnt++;
}
int fa[maxn][22],deep[maxn],lg[maxn];
void dfs(int u,int father)
{deep[u]=deep[father]+1,fa[u][0]=father;for(int i=1;i<=lg[ deep[u] ];i++)fa[u][i]=fa[ fa[u][i-1] ][i-1];for(int i=head[u];i;i=d[i].nxt){int v=d[i].to;if( v==father )	continue;dfs(v,u);}
}int lca(int x,int y)
{if( deep[x]<deep[y] )	swap(x,y);while( deep[x]>deep[y] )x=fa[x][ lg[deep[x]-deep[y]]-1 ];if( x==y )	return x;for(int i=lg[ deep[x] ]-1;i>=0;i--)if( fa[x][i]!=fa[y][i] )x=fa[x][i],y=fa[y][i];return fa[x][0];
}
void init(){for(int i=1;i<=200000;i++)	lg[i]=lg[i-1]+(i==(1<<lg[i-1]) );
}
int get_dis(int x,int y){int u=lca(x,y);
//	cout << x << "和" << y << "的lca是" << u << endl;return deep[x]+deep[y]-2*deep[u];
} 
int main()
{cin >> n >> q;init();for(int i=2,l;i<=n;i++){scanf("%d",&l);add(i,l); add(l,i);}dfs(1,0);while( q-- ){int a,b,c,ans;scanf("%d%d%d",&a,&b,&c);int ab=get_dis(a,b);int bc=get_dis(b,c);int ac=get_dis(a,c);//	cout << ab << " " << bc << " " << ac << endl;int na=( ac+ab-bc )/2;int nb=( ab+bc-ac )/2;int nc=( bc+ac-ab )/2;ans=max(na,max(nb,nc) )+1;printf("%d\n",ans);}
}