Borrow Classroom (LCA)

题目传送门

题意：给一棵树的三个结点A,B,C求dis(A,1)与dis(B,C)+dis(C,1)的关系。

思路：利用LCA求出dis(A,1)=dep[A],dis(C,1)=dep[C],dis（B,C）=dep[B]+dep[C]-dep[lca(B,C)]。然后还要特判一下当dis(A,1)=dis(B,C)+dis(C,1)时 lca(A,C)是否等于1，若等于1也是输出NO。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>e[N];
int dep[N],fa[N][20],mx,n,q,t;
void dfs(int u){ //DFS遍历整棵树 
	for(auto v:e[u])
		if(v!=fa[u][0]){
			fa[v][0]=u,dep[v]=dep[u]+1;
			for(int i=1;i<=mx;i++)
				fa[v][i]=fa[fa[v][i-1]][i-1];
			dfs(v);
		}
}
int lca(int u,int v){ //LCA
	if(dep[u]<dep[v]) swap(u,v);
	int dta=dep[u]-dep[v];
	for(int i=0;i<=mx;i++)
		if((1<<i)&dta) u=fa[u][i];
	if(u==v) return u;
	for(int i=mx;i>=0;i--)
		if(fa[u][i]!=fa[v][i])
			u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
int main(){
	cin>>t;
	while(t--){
		for(int i=1;i<=n;i++) e[i].clear();//初始化 
		cin>>n>>q;
		mx=log2(n),dep[1]=0;//初始化 
		for(int i=1,u,v;i<n;i++){
			cin>>u>>v;
			e[u].push_back(v);
			e[v].push_back(u); 
		}
		dfs(1);
		while(q--){
			int a,b,c,d1,d2;
			cin>>a>>b>>c;
			d1=dep[a],d2=dep[b]+dep[c]*2-2*dep[lca(b,c)];
			if(d1<d2) puts("YES");
			else if(d1>d2) puts("NO");
			else puts(lca(a,c)==1?"NO":"YES");//特判 
		}
	}
	return 0;
}