题意:在一棵生成树上，给出了三个点，求三个点之间最大的相交点数，CF难度1900。
题解：求出三个lca，并取深度最大的那个，就是我们要的三岔路口K，然后分别求出K到a，b，c三点的路径长度，取最大值+1就是答案。为什么是取深度最大的呢？因为只有当深度是最大的时候设该点为K，这个K为三岔路口，每一个a，b，c到K的距离都不会用重复，否则如果取的不是最深的，可能造成重复的情况，这个需要避免。然后找到这个K之后，ans就是a，b，c三点分别到K的距离+1即可（+1是因为本身也算）。
一开始没做出来的原因：不知道如何找这个岔口....以为需要把岔口当做root来弄，然后就需要一次又一次的重复更新建立LCA表，就很麻烦。其实求岔口只需要以1作为root，然后a，b，c三个点两两求LCA然后取深度最大的LCA就行了....树上每2个点的距离dis(u,v)=depth[u]+depth[v]-2*depth(LCA(u,v)],好吧是我菜了
#include<bits/stdc++.h> #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e5+5; int tot,head[maxn]; struct E{ int to,next; }edge[maxn<<1]; void add(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } int n,m,a[maxn],fa[maxn][40],depth[maxn],vis[maxn]; void dfs(int s,int step){ depth[s]=step;vis[s]=1; for(int i=head[s];i!=-1;i=edge[i].next){ int v=edge[i].to; if(!vis[v]) fa[v][0]=s,dfs(v,step+1); } } void bz(){ for(ll j=1;j<=30;j++){ for(ll i=1;i<=n;i++){ fa[i][j]=fa[fa[i][j-1]][j-1]; } } } ll LCA(ll u,ll v){ if(depth[u]<depth[v]) swap(u,v); ll dc=depth[u]-depth[v]; for(ll i=0;i<30;i++){ if((1<<i)&dc){ u=fa[u][i]; } } if(u==v) return u; for(ll i=29;i>=0;i--){ if(fa[u][i]!=fa[v][i]){ u=fa[u][i]; v=fa[v][i]; } } u=fa[u][0]; return u; } int dis(int u,int v){ return depth[u]+depth[v]-2*depth[LCA(u,v)]; } int main(){ scanf("%d%d",&n,&m);mem(head,-1); for(int i=2;i<=n;i++){ int x;scanf("%d",&x); add(i,x);add(x,i); } dfs(1,1); bz(); while(m--){ int a,b,c;scanf("%d%d%d",&a,&b,&c); int l1=LCA(a,b); int l2=LCA(a,c); int l3=LCA(b,c); if(depth[l2]>depth[l1]) l1=l2; if(depth[l3]>depth[l1]) l1=l3; cout<<max(dis(l1,a),max(dis(l1,b),dis(l1,c)))+1<<endl; } }