【codevs2370】小机房的树 LCA 倍增

2370 小机房的树

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 钻石 Diamond

题目描述 Description

小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告诉他们最少需要花费多少精力

输入描述 Input Description

第一行一个n，接下来n-1行每一行有三个整数u，v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。
第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ，v 表示两只虫子所在的节点

输出描述 Output Description

一共有m行，每一行一个整数，表示对于该次询问所得出的最短距离。

样例输入 Sample Input

1 0 1

2 0 1

1 0

2 0

1 2

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1<=n<=50000， 1<=m<=75000， 0<=c<=1000

题解：

　　今天练习的LCA 倍增的第二题，也是一道模板题。相对于上一道商务旅行而言，只不过是加上了一个边的权值，可以用前缀和的方式：v[i]记录从 i 节点到根节点的距离，注意节点是从0开始的，找到LCA 后，通过计算公式：ans=v[x]+v[y]-2*v[lca(x,y)] 便可以计算出ans了。又把倍增递推写错了。。而且错的还是刚才没有错的。。。。好吧。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 50005
 6 using namespace std;
 7 int n,m;
 8 int tot,he[maxn],to[maxn*2],ne[maxn*2],w[maxn*2];
 9 int f[14][maxn],depth[maxn],v[maxn];
10 bool vis[maxn];
11 void add(int a,int b,int c)
12 {
13     tot++;to[tot]=b;w[tot]=c;ne[tot]=he[a];he[a]=tot;
14 }
15 void build (int x)
16 {
17     for (int i=he[x];i;i=ne[i])
18     if(!vis[to[i]]){
19         vis[to[i]]=true;
20         depth[to[i]]=depth[x]+1;
21         v[to[i]]=v[x]+w[i];
22         f[0][to[i]]=x;
23         build(to[i]);
24     }
25 }
26 void bz()
27 {
28     for (int i=1;i<=14;i++)//i=1!!!! or  WA掉100
29       for (int j=0;j<=n-1;j++)
30         f[i][j]=f[i-1][f[i-1][j]];
31 }
32 int lca(int a,int b)
33 {
34     if (depth[a]<depth[b]) swap(a,b);
35     int derta=depth[a]-depth[b];
36     for (int i=0;i<=14;i++)
37     {
38         if (1<<i & derta){
39             a=f[i][a];
40         }
41     }
42     if (a==b) return a;
43     for (int i=14;i>=0;i--)
44     {
45         if (f[i][a]!=f[i][b]){
46             a=f[i][a];
47             b=f[i][b];
48         }
49     }
50     return f[0][a];
51 }
52 int main()
53 {
54     freopen("codevs2370.in","r",stdin);
55     cin>>n;
56     for (int i=1;i<n;i++)
57     {
58         int x,y,z;
59         scanf("%d%d%d",&x,&y,&z);
60         add(x,y,z);
61         add(y,x,z);
62     }
63     vis[0]=true;
64     depth[0]=1;
65     build(0);
66     bz();
67     cin>>m;
68     for (int i=1;i<=m;i++)
69     {
70         int x,y;
71         scanf("%d%d",&x,&y);
72         printf("%d
",v[x]+v[y]-2*v[lca(x,y)]);
73     }
74     return 0;
75 }

View Code