Submit: 1997 Solved: 1048
[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
HINT
Source
资格赛
Solution
我用了Tarjan离线LCA来做。
要注意位运算中>>1是除以2，<<1是乘以2。
|
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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include<iostream> #include<cstdio> using namespace std; const int N=1005; int n,q,tot,tot1,Next[N<<1],head[N],tree[N<<1],val[N<<1],Next1[N<<1],head1[N]; int tree1[N<<1],id[N<<1],sum[N],f[N],Ans[N],ans[N]; bool visit[N]; int get(int x) { if (f[x]==x) return x;else f[x]=get(f[x]); return f[x]; } void add(int x,int y,int z) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; } void Add(int x,int y,int z) { tot1++; Next1[tot1]=head1[x]; head1[x]=tot1; tree1[tot1]=y; id[tot1]=z; } void dfs(int now,int s) { sum[now]=s; for (int i=head[now];i;i=Next[i]) if (sum[tree[i]]==0&&tree[i]!=1) dfs(tree[i],s+val[i]); } void Tarjan_LCA(int u) { visit[u]=true; for (int i=head[u];i;i=Next[i]) { int v=tree[i]; if (!visit[v]) { Tarjan_LCA(v); f[get(v)]=u; } } for (int i=head1[u];i;i=Next1[i]) if (Ans[id[i]]==0&&visit[tree1[i]]) { Ans[id[i]]=get(tree1[i]); ans[id[i]]=sum[u]+sum[tree1[i]]-2*sum[Ans[id[i]]]; } } int main() { scanf("%d%d",&n,&q); tot=tot1=0; for (int i=1;i<n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } for (int i=1;i<=q;i++) { int x,y; scanf("%d%d",&x,&y); Add(x,y,i);Add(y,x,i); } dfs(1,0); for (int i=1;i<=n;i++) f[i]=i,visit[i]=false; Tarjan_LCA(1); for (int i=1;i<=q;i++) printf("%d\n",ans[i]); return 0; } |
