CodeVS 1503 愚蠢的宠物
2024-10-21 09:09:26
题目描述 Description
大家都知道,sheep有两只可爱的宠物(一只叫神牛,一只叫神菜)。有一天,sheep带着两只宠物到狗狗家时,这两只可爱的宠物竟然迷路了……
狗狗的家因为常常遭到猫猫的攻击,所以不得不把家里前院的路修得非常复杂。狗狗家前院有N个连通的分叉结点,且只有N-1条路连接这N个节点,节点的编号是1-N(1为根节点)。sheep的宠物非常笨,他们只会向前走,不会退后(只向双亲节点走),sheep想知道他们最早什么时候会相遇(即步数最少)。
输入描述 Input Description
第1行:一个正整数N,表示节点个数。
第2~N行:两个非负整数A和B,表示A是B的双亲。(保证A,B<=n)
第N+1行:两个非负整数A和B,表示两只宠物所在节点的位置。(保证A,B<=n)
输出描述 Output Description
输出他们最早相遇的节点号。
样例输入 Sample Input
10
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
4 10
3 6
样例输出 Sample Output
1
数据范围及提示 Data Size & Hint
对于10%的数据,n<10^6
对于100%的数据,n<=10^6
一个裸LCA,倍增解决。
(其实这题用不着倍增,普通dfs足够了)
/*by SilverN*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int mxn=;
struct node{
int v,next;
}e[mxn];
int hd[mxn],cnt;
int fa[mxn][];
int dep[mxn];
int n,m;
int a,b;
void add_edge(int u,int v){
e[++cnt].v=v;e[cnt].next=hd[u];hd[u]=cnt;return;
}
void dfs(int u){
int i,j;
for(i=hd[u];i;i=e[i].next){
int v=e[i].v;
dep[v]=dep[u]+;
for(j=;(<<j)<=dep[v];j++)
fa[v][j]=fa[fa[v][j-]][j-];
dfs(v);
}
}
void solve(){
int i,j;
int x=a,y=b;
if(dep[x]<dep[y])swap(x,y);
for(i=;i>=;i--){
if(dep[x]>=dep[y]+(<<i)) x=fa[x][i];//
}
if(x==y){printf("%d\n",x);return;}
for(i=;i>=;i--){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];y=fa[y][i];
}
}
printf("%d\n",fa[x][]);
return;
}
int main(){
scanf("%d",&n);
int i,j;
for(i=;i<n;i++){
scanf("%d%d",&a,&b);
add_edge(a,b);
fa[b][]=a;
}
scanf("%d%d",&a,&b);
dep[]=;
fa[][]=-;
dfs();
solve();
return ;
}
最新文章
- Ubuntu 14.04开发环境初始化
- [.net 面向对象程序设计进阶] (3) 正则表达式 (二) 高级应用
- IO - 同步,异步,阻塞,非阻塞 (亡羊补牢篇)
- Python之调用函数
- 移动端调试工具推荐 小苹果和debugap
- Mysql常出现的问题
- codeforces 483B Friends and Presents 解题报告
- [RQNOJ313]波浪数
- TCP_DEFER_ACCEPT的坑
- IE下判断IE版本的语句
- Java中有关日期的一些常见运算与应用(Date,DateFormat,SimpleDateFormat)
- HDU 5812 Distance
- KVO 进阶
- javascript如何处理多级的实时监听
- jsp页面选择文件上传,获取不到绝对路径问题
- 浅谈canvas中的拖尾效果
- ubuntu 下使用 jsoncpp库
- 怎么搜索sci论文。
- iOS一段文字设置多种颜色格式
- E. The Supersonic Rocket Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2)
热门文章
- jrtplib移植
- 6- vue django restful framework 打造生鲜超市 -完成商品列表页(下)
- php微信分享demo
- 21.VUE学习之-操作data里的数组变异方法push&;unshit&;pop&;shift的实例应用讲解
- 第37课 thinkphp5添加商品基本信息及通过前置钩子上传商品主图 模型事件(勾子函数)
- Django--源码安装
- 3 View - 状态保持 session
- Service IntentService区别 (面试)
- Hive将SQL转化为MapReduce的过程
- Hyper-V动态迁移中?小心性能损失