How far away ?(LCA)dfs和倍增模版
2024-08-29 04:50:57
How far away ?
Tarjan
http://www.cnblogs.com/caiyishuai/p/8572859.html
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 20491 Accepted Submission(s):
8010
Problem Description
There are n houses in the village and some
bidirectional roads connecting them. Every day peole always like to ask like
this "How far is it if I want to go from house A to house B"? Usually it hard to
answer. But luckily int this village the answer is always unique, since the
roads are built in the way that there is a unique simple path("simple" means you
can't visit a place twice) between every two houses. Yout task is to answer all
these curious people.
bidirectional roads connecting them. Every day peole always like to ask like
this "How far is it if I want to go from house A to house B"? Usually it hard to
answer. But luckily int this village the answer is always unique, since the
roads are built in the way that there is a unique simple path("simple" means you
can't visit a place twice) between every two houses. Yout task is to answer all
these curious people.
Input
First line is a single integer T(T<=10), indicating
the number of test cases.
For each test case,in the first line there are
two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses
and the number of queries. The following n-1 lines each consisting three numbers
i,j,k, separated bu a single space, meaning that there is a road connecting
house i and house j,with length k(0<k<=40000).The houses are labeled from
1 to n.
Next m lines each has distinct integers i and j, you areato answer
the distance between house i and house j.
the number of test cases.
For each test case,in the first line there are
two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses
and the number of queries. The following n-1 lines each consisting three numbers
i,j,k, separated bu a single space, meaning that there is a road connecting
house i and house j,with length k(0<k<=40000).The houses are labeled from
1 to n.
Next m lines each has distinct integers i and j, you areato answer
the distance between house i and house j.
Output
For each test case,output m lines. Each line represents
the answer of the query. Output a bland line after each test case.
the answer of the query. Output a bland line after each test case.
Sample Input
2
3 2
1 2 10
3 1 15
1 2
2 3
3 2
1 2 10
3 1 15
1 2
2 3
2 2
1 2 100
1 2
2 1
Sample Output
10
25
100
100
25
100
100
Source
Recommend
这一道题目意思是说,村庄之间有路可达,给你N个节点,N-1条路,然后M组查询,查询两个节点之间的距离。
N个节点N-1条边,那么就符合树的定义。所以题目给的就是一个树,就是求树上两个节点的距离。
这一道题目可以和LCA联系起来,求两个节点(a和b)的距离。两个节点必然由一个公共点连接起来,这个点就是LCA(最近公共祖先c)
那么求距离就可以转换为a到根节点的距离+b到根节点的距离—c到根节点的距离—c到根节点的距离。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#define N 100000+10
using namespace std;
int n,m;
struct node
{
int to,next,cost;
}e[N];
int cnt;
int fa[][N];
int head[N],depth[N],dis[N];
void init()
{
memset(head,-,sizeof head);
memset(depth,,sizeof depth);
memset(dis,,sizeof dis);
cnt=;
}
void addedge(int u,int v,int w)//建图过程,建双向边
{
e[cnt].to=v;
e[cnt].cost=w;
e[cnt].next=head[u];
head[u]=cnt++;
} void DFS(int u,int f)//遍历树
{
fa[][u]=f;
for(int i=head[u];~i;i=e[i].next)//遍历所有相连的边
{
int To=e[i].to;
if(To!=f)//去掉以后MLE,可能是递归求的过程中太多临时变量
{//建树过程建双向边,会出现to=f的情况,去掉以后会陷入无限递归中
dis[To]=dis[u]+e[i].cost;//更新距离
depth[To]=depth[u]+;//更新深度
DFS(To,u);
}
} } void solve()
{
depth[]=;//题目给的是一个树
dis[]=;//无论怎么样的树,都可以把1视为根节点
DFS(,-);
for(int i=;i<;i++)//树上倍增
for(int j=;j<=n;j++)
fa[i][j]=fa[i-][fa[i-][j] ];
} int LCA(int u,int v)//求最近公共祖先
{
if(depth[u]>depth[v])//保证V的深度比较大
swap(u,v);
for(int i=;i<;i++)//倍增到深度相同
if((depth[v]-depth[u])>>i&)//二进制特性,一定能跳到深度相同
v=fa[i][v];
if(u==v)
return u;
for(int i=;i>=;i--)//两者同时倍增
{
if(fa[i][u]!=fa[i][v])
{
u=fa[i][u];
v=fa[i][v];
}
}
return fa[][v];
}
int main()
{
int i,t;
int a,b,c;
while(scanf("%d",&t)!=EOF)
{ while(t--)
{
init();
scanf("%d%d",&n,&m);
for(i=;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
}
solve();
for(i=;i<=m;i++)
{
scanf("%d%d",&a,&b);
int ans=dis[a]+dis[b]-*dis[LCA(a,b)];
printf("%d\n",ans);
}
}
return ;
}
}
最新文章
- 【转载】mysql慢查询
- GitHub安装配置
- poj1006-Biorhythms(中国剩余定理)
- DevExpress GridView对表格的部分说明
- PHP isset()与empty()的区别
- cocos2d-x之CCMotionStreak类&mdash;&mdash;2013-08-25 16
- 浅述Oracle分布式事务概念
- Android文件下载(实现断点续传)
- Struts2之初识
- 安装WebLogic失败,出现”[VALIDATION] [ERROR]:INST-07004: Oracle 主目录(O) 位置包含一个或多个无效字符“解决方案
- LayaAir引擎开发HTML5最简单教程(面向JS开发者)
- 关于nginx安装的收藏
- 【iCore1S 双核心板_ARM】例程二十:UART_IAP_ARM实验——更新升级STM32
- R包的小技巧
- mysql导入导出表
- computational biology | Bioinformatician | 开发者指南
- Python 自然语言处理笔记(一)
- window.location.replace()与window.location.href()区别
- 新电脑装不了win7?来试试我的方法!
- VIM字符编码基础知识