首页 > 代码库 > 树讲解——牧场行走（ lca ）
树讲解——牧场行走（ lca ）
大视野 1602: [Usaco2008 Oct]牧场行走
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1947 Solved: 1021
[Submit][Status][Discuss]
Description
N头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。 这n块土地被n-1条边连接。 奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。 这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。
Input
*第一行：两个被空格隔开的整数：N和Q
*第二行到第n行：第i+1行有两个被空格隔开的整数：AI，BI，LI
*第n+1行到n+Q行：每一行有两个空格隔开的整数：P1，P2，表示两头奶牛的编号。
Output
*第1行到第Q行：每行输出一个数，表示那两头奶牛之间的距离。
Sample Input
4 2
2 1 2
4 3 2
1 4 3
1 2
3 2
2 1 2
4 3 2
1 4 3
1 2
3 2
Sample Output
2
7
7
思路：
对于这道题，我们可以发现，两各节点之间的距离就等于这两点的深度之和减去这两点的lca的深度的两倍
so，这道题我们就转化成求lca的问题了
好废话少说，我们来看看代码吧！
代码：
#include<vector>#include<cstdlib>#include<stdio.h>#include<cstring>#include<iostream>#include<algorithm>#define N 10001using namespace std;vector<pair<int,int> >vec[N];int n,m,x,y,z,fa[N],deep[N],top[N],size[N],dis[N];int lca(int x,int y){ for(;top[x]!=top[y];) { if(deep[top[x]]<deep[top[y]]) swap(x,y); x=fa[top[x]]; } if(deep[x]>deep[y]) swap(x,y); return x;}void dfs(int x){ size[x]=1; deep[x]=deep[fa[x]]+1; for(int i=0;i<vec[x].size();i++) { if(fa[x]!=vec[x][i].first) { fa[vec[x][i].first]=x; dis[vec[x][i].first]=dis[x]+vec[x][i].second; dfs(vec[x][i].first); size[x]+=size[vec[x][i].first]; } } }void dfs1(int x){ int t=0; if(!top[x]) top[x]=x; for(int i=0;i<vec[x].size();i++) if(vec[x][i].first!=fa[x]&&size[vec[x][i].first]>size[t]) t=vec[x][i].first; if(t) { top[t]=top[x]; dfs1(t); } for(int i=0;i<vec[x].size();i++) if(vec[x][i].first!=fa[x]&&vec[x][i].first!=t) dfs1(vec[x][i].first);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<n;i++) { scanf("%d%d%d",&x,&y,&z); vec[x].push_back(make_pair(y,z)); vec[y].push_back(make_pair(x,z)); } dfs(1); dfs1(1); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); printf("%d\n",dis[x]+dis[y]-2*dis[lca(x,y)]); }}
树讲解——牧场行走（ lca ）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。