原题大意

给一棵树，在给给出3个点s，f，t问s到f与t到f经过相同的点有几个？输出最多的那种sft组合。

算法分析

分情况讨论：

f是s的祖先，t在f到s的外面
f是s的祖先，t在f到s的路径上
s->lca(f,s)->f，lca(s,t)在s->lca(f,s)上
s->lca(f,s)->f，lca(f,t)在lca(f,s)->f上

另一种取巧的做法是(lca(a,b) + lca(c,b) - lca(a,c))/2

程序代码

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
#define pb push_back
const int maxn=100005;
int n, q;
int fir[maxn],no[2*maxn],se[2*maxn],st[2*maxn][20],lo[200005],dep[maxn];
bool used[maxn];
struct nod
{
    int to,cost;
};
vector<nod> g[maxn];
int cnt,sum;



void mkST()
{
    for(int i=1;i<=cnt;i++)st[i][0]=se[i];
    for(int j=1;(1<<j)<=cnt;j++)
        for(int i=1;i<=cnt-(1<<j)+1;i++)
            st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}

void DFS(int u,int f,int di)
{
    dep[u]=di;
    no[++sum]=u;
    int t=sum;
    se[++cnt]=t;
    fir[u]=cnt;
    for(auto p : g[u])
    {
        if(p.to==f)continue;
        DFS(p.to,u,di+p.cost);
        se[++cnt]=t;
    }
}

int find(int p,int q)
{
    if(p>q)swap(p,q);
    int j=lo[q-p+1];
    return min(st[p][j],st[q-(1<<j)+1][j]);
}

int cal(int x,int y)
{
    int now=no[find(fir[x],fir[y])];
    return dep[x]+dep[y]-2*dep[now];
}
int main(){
    lo[1]=0;
    for(int i=2;i<=200000;i++)lo[i]=lo[i>>1]+1;
    scanf("%d%d", &n, &q);
    for(int i = 2; i <= n; i++){
        int t;
        scanf("%d", &t);
        g[i].pb({t,1});
        g[t].pb({i,1});
    }
    DFS(1,0,0);mkST();
    for(int i = 1; i <= q; i++){
        int a,b,c;
        scanf("%d%d%d",&a, &b, &c);
        int l1 = (cal(a,b) + cal(a,c) - cal(b,c))/2;
        int l2 = (cal(b,a) + cal(b,c) - cal(a,c))/2;
        int l3 = (cal(c,a) + cal(c,b) - cal(b,a))/2;
        printf("%d\n",1+ max(l1,max(l2,l3)));
    }
    return 0;
}