给一个图，给图上三个点，各自从这三个点出发，到达同一个点，问最少走的花费是多少？（每条边的花费都是1）
思路：两两求 LCA，得到三个 LCA，必定其中两个是重叠的，选择不重叠的那个点作为目的地（可以脑补一下，假如选重叠的那个，一段路是会被两个人走的），然后再用差分。
LCA 可以用倍增来求。
#include<iostream> #include<cstdio> #include<cstring> #define MAXN 500010 #define MAXM 1000010 using namespace std; typedef long long ll; int n,m,u,v,lg[MAXN],a,b,c,t,dep[MAXN],fa[MAXN][25],head[MAXN],cnt; ll res; struct Edge{ int to,nxt; }edge[MAXM]; void addedge(int u,int v){ edge[cnt].to=v;edge[cnt].nxt=head[u];head[u]=cnt++; } void dfs(int u,int f){ dep[u]=dep[f]+1;fa[u][0]=f; for(int i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(v!=f)dfs(v,u); } } int lca(int u,int v){ if(dep[u]<dep[v])swap(u,v); // 保证 dep[u]>dep[v] 即 u 在更深处 while(dep[u]>dep[v])u=fa[u][lg[dep[u]-dep[v]]-1]; if(u==v)return u; for(int k=lg[dep[u]];k>=0;k--) if(fa[u][k]!=fa[v][k])u=fa[u][k],v=fa[v][k]; return fa[u][0]; } int main(){ #ifdef WINE freopen("data.in","r",stdin); #endif memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=1;i<=n-1;i++){ scanf("%d%d",&u,&v); addedge(u,v);addedge(v,u); } dfs(1,0); for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i); for(int i=1;i<=m;i++){ scanf("%d%d%d",&a,&b,&c); int t1=lca(a,b),t2=lca(a,c),t3=lca(b,c); if(t1==t2)t=t3; if(t1==t3)t=t2; if(t2==t3)t=t1; res=dep[a]+dep[b]+dep[c]-dep[t1]-dep[t2]-dep[t3]; printf("%d %lld\n",t,res); } return 0; }