最近公共祖先。
如果$A$到$1$的时间小于$B$到$C$再到$1$的时间，那么一定可以拦截。
如果上述时间相等，需要在到达$1$之前，两者相遇才可以拦截。
#include<bits/stdc++.h> using namespace std; int T,n,Q,sz; int dep[100010],f[100010]; int dp[100010][35]; int h[200010],to[200010],nx[200010]; void add(int x,int y) { to[sz] = y; nx[sz] = h[x]; h[x] = sz++; } int LCA(int x,int y) { if(dep[x]<dep[y]) swap(x,y); while(1) { if(dep[x]==dep[y]) break; for(int j=20;j>=0;j--) { int p = dp[x][j]; if(p==-1) continue; if(dep[p]<dep[y]) continue; x=p; break; } } if(x==y) return x; while(1) { if(dp[x][0]==dp[y][0]) return dp[x][0]; for(int j=20;j>=0;j--) { int p = dp[x][j]; int q = dp[y][j]; if(p==q) continue; x = p; y = q; break; } } } int dis(int x,int y) { int t = LCA(x,y); return dep[x]-dep[t] + dep[y]-dep[t]; } void dfs(int x,int y,int d) { f[x]=1; dp[x][0] = y; dep[x] = d; for(int i = h[x];i!=-1;i=nx[i]) { int p = to[i]; if(f[p]) continue; dfs(p,x,d+1); } } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&Q); for(int i=1;i<=n;i++) { f[i]=0; h[i]=-1; } sz=0; for(int i=1;i<=n-1;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } dfs(1,-1,1); for(int j=1;j<=20;j++) for(int i=1;i<=n;i++) { if(dp[i][j-1]==-1) dp[i][j]=-1; else dp[i][j] = dp[dp[i][j-1]][j-1]; } for(int i=1;i<=Q;i++) { int A,B,C; scanf("%d%d%d",&A,&B,&C); int ans=0; int disAC = dis(A,C); int disBC = dis(B,C); int disA1 = dep[A]-dep[1]; int disC1 = dep[C]-dep[1]; if(disAC<=disBC) ans=1; if(disA1<disBC+disC1) ans=1; if(disA1==disBC+disC1&&LCA(A,C)!=1) ans=1; if(ans==1) printf("YES "); else printf("NO "); } } return 0; }