NC13813. Borrow Classroom
描述
输入描述
第一行是一个正整数T(≤ 5)，表示测试数据的组数， 对于每组测试数据， 第一行是两个整数n,q(1≤ n,q ≤ 100000)，分别表示节点数和询问数， 接下来n-1行，每行包含两个整数x,y(1≤ x,y ≤ n)，表示x和y之间有一条边相连，保证这些边能构成一棵树， 接下来q行，每行包含三个整数A,B,C(1 ≤ A,B,C ≤ n)，表示一个询问，其中A是何老师所在位置，B是SK同学所在位置，C是小Q同学所在位置，保证小Q同学初始不在教务处。
输出描述
对于每个询问，输出一行，如果何老师能成功拦截则输出"YES"（不含引号），否则输出"NO"（不含引号）。
示例1
输入:
1 7 2 1 2 2 3 3 4 4 7 1 5 1 6 3 5 6 7 5 6
输出:
YES NO
C++(clang++ 11.0.1) 解法, 执行用时: 1535ms, 内存消耗: 23488K, 提交时间: 2022-08-26 21:17:45
#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){
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){
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;
}