「BZOJ1602」[Usaco2008 Oct] 牧场行走
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
题解
dis[x]表示根到x的距离
则x,y距离为dis[x]+dis[y]-2*dis[lca(x,y)]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,q,cnt; int deep[1001],head[1001],dis[1001],fa[1001][11]; bool vis[1001]; struct data{int to,next,v;}e[2001]; void ins(int u,int v,int w) {e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;} void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,w);} void dfs(int x) { vis[x]=1; for(int i=1;i<=9;i++) { if(deep[x]<(1<<i))break; fa[x][i]=fa[fa[x][i-1]][i-1]; } for(int i=head[x];i;i=e[i].next) { if(vis[e[i].to])continue; deep[e[i].to]=deep[x]+1; dis[e[i].to]=dis[x]+e[i].v; fa[e[i].to][0]=x; dfs(e[i].to); } } int lca(int x,int y) { if(deep[x]<deep[y])swap(x,y); int d=deep[x]-deep[y]; for(int i=0;i<=9;i++) if((1<<i)&d)x=fa[x][i]; for(int i=9;i>=0;i--) if(fa[x][i]!=fa[y][i]) {x=fa[x][i];y=fa[y][i];} if(x==y)return x; else return fa[x][0]; } int main() { scanf("%d%d",&n,&q); for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); insert(u,v,w); } dfs(1); for(int i=1;i<=q;i++) { int x,y; scanf("%d%d",&x,&y); printf("%d\n",dis[x]+dis[y]-2*dis[lca(x,y)]); } return 0; } |
Subscribe
计数器 9855188
OI 课件=>
OI 课件=>