BNUOJ ->Borrow Classroom(LCA)
2024-08-31 04:13:21
B. Borrow Classroom
Time Limit: 5000ms
Memory Limit: 262144KB
每年的BNU校赛都会有两次赛前培训,为此就需要去借教室,由于SK同学忙于出题,这个事情就由小Q同学来跑腿。SK同学准备从宿舍出发,把借教室的单子交给小Q同学让他拿去教务处盖章,但是何老师突然发现SK同学好像借错教室了,想抢在借教室的单子被送到教务处之前拦截下来。
现在把校园抽象成一棵个节点的树,每条边的长度都是一个单位长度,从到编号,其中教务处位于号节点,接下来有个询问,每次询问中SK同学会从号节点出发,到号节点找到小Q同学并将借教室的单子交给他,然后小Q同学再从号节点出发前往教务处,何老师会从号节点出发开始拦截。
所有人在一个单位时间内最多走一个单位距离,只要何老师在单子还没被送到教务处之前遇到拿着单子的同学都算拦截成功,如果小Q同学已经到了教务处,那么由于小Q同学手速极快,单子会被立即交上去,即使何老师到了教务处也无济于事,你需要判断何老师是否能够拦截成功。
Input
第一行是一个正整数,表示测试数据的组数,
对于每组测试数据,
第一行是两个整数,分别表示节点数和询问数,
接下来行,每行包含两个整数,表示和之间有一条边相连,保证这些边能构成一棵树,
接下来行,每行包含三个整数,表示一个询问,其中是何老师所在位置,是SK同学所在位置,是小Q同学所在位置,保证小Q同学初始不在教务处。
Output
对于每个询问,输出一行,如果何老师能成功拦截则输出"YES"(不含引号),否则输出"NO"(不含引号)。
Sample Input
1
7 2
1 2
2 3
3 4
4 7
1 5
1 6
3 5 6
7 5 6
Sample Output
YES
NO
这就是lca的裸题呀 因为自己一个地方导致无限wa
就是 求出b->c->1的距离 t1 和b->1的距离 t2
if(t1<t2)no
if(t1>t2)yes
if(t1==t2){lca(c,a)==1->no else->yes}
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<cstdlib>
#include<string>
typedef long long ll;
typedef unsigned long long LL;
using namespace std;
const double pi=acos(-1.0);
const int N=+;
const double eps=0.000000001;
int head[N];
int cnt;
struct node{
int to,next,w;
}edge[*N];
int d[N*];
int dp[*N][];
int t1;
int dep[N*],pos[N*],f[N*];
void init(){
memset(head,-,sizeof(head));
memset(pos,-,sizeof(pos));
memset(d,,sizeof(d));
cnt=;
t1=;
}
void add(int u,int v,int w){
edge[cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].w=w;
head[u]=cnt++;
}
void init_RMQ(int n){
for(int i=;i<=n;i++)dp[i][]=i;
for(int j=;(<<j)<=n;j++)
for(int i=;i+(<<j)-<=n;i++)
if(dep[dp[i][j-]]<dep[dp[i+(<<j-)][j-]])dp[i][j]=dp[i][j-];
else
dp[i][j]=dp[i+(<<j-)][j-];
}
int RMQ(int l,int r){
int k=;
while((<<k+)<=r-l+)k++;
if(dep[dp[l][k]]<dep[dp[r-(<<k)+][k]])return dp[l][k];
else
return dp[r-(<<k)+][k];
}
int lca(int u,int v){
if(pos[u]>pos[v])return f[RMQ(pos[v],pos[u])];
else
return f[RMQ(pos[u],pos[v])];
}
void DFS(int x,int deep){
f[t1]=x;
dep[t1]=deep;
pos[x]=t1++;
for(int i=head[x];i!=-;i=edge[i].next){
int v=edge[i].to;
if(pos[v]==-){
d[v]=d[x]+;
DFS(v,deep+);
f[t1]=x;
dep[t1++]=deep;
} }
}
int main(){
int t;
scanf("%d",&t);
int n,q;
while(t--){
init();
scanf("%d%d",&n,&q);
for(int i=;i<=n-;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v,);add(v,u,);
}
DFS(,);
init_RMQ(*n-);
while(q--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(b==&&c==){cout<<"NO"<<endl;continue;}
int ans1=d[b]+*d[c]-*d[lca(c,b)];
int ans2=d[a];
if(ans2<ans1)printf("YES\n");
else if(ans2==ans1){
if(lca(a,c)==)cout<<"NO"<<endl;
else{
cout<<"YES"<<endl;
}
}
else{
cout<<"NO"<<endl;
}
}
}
return ;
}
最新文章
- WCF学习之旅—TCP双工模式(二十一)
- WPF入门:数据绑定
- NetBeans建立跳过测试构建的快捷方式
- Linux tricks
- struts2 javaweb 过滤器、监听器 拦截器 原理
- HU 参考错误修正:/SCWM/RCORR_HUREF
- 4.3.3版本之引擎bug
- Web项目后台测试流程
- URAL 1934 Black Spot(最短路)
- ###学习《C++ Primer》- 5
- asp.net mvc 删除栏目、栏目下又有子栏目的处理方式
- LeetCode 108. Convert Sorted Array to Binary Search Tree (有序数组转化为二叉搜索树)
- poj_2503(map映射)
- Raft算法
- java虚拟机的学习书籍推荐
- typecho只能打开主页,文章详细内容打不开
- JAVA编程思想第一章——对象导论
- Influxdb时序数据库阅读笔记
- UItextfield各个通知和回调的顺序
- labview
热门文章
- [Android]异常7-Error:Configuration with name &#39;default&#39; not found.
- Angular——基本使用
- html——特殊字符
- JQuery文档加载完成执行js的几种方法
- c#中动态创建textbox并且从数据库中获取表中数据添加到textbox中
- Oracle 数据库连接的一些坑
- node版本管理工具nvm安装使用教程
- Luogu P2298 Mzc和男家丁的游戏
- swap() 函数实现的方法
- uva 10048 Audiophobia UVA - 10048