首页 > 其他 > 详细

[codevs2370]小机房的树<LCA>

时间:2017-10-15 20:13:09      阅读:296      评论:0      收藏:0      [点我收藏+]

题目链接:http://codevs.cn/problem/2370/

这题我还是做了比较久了,因为有人告诉我这是用tarjan离线做技术分享

好吧算我是蒟蒻,真心不懂tarjan怎么做,最后还是用倍增做的

 

所以我也就借着这题复习了一下RMQ了。。

思想就是定义两个数组f[i][j],dis[i][j]分别表示从i上升2^j层到达的节点和需要的价值

然后就是让两个询问节点先在统一深度需要的价值加上到达同一节点需要的价值,没啥难度,看看难度就懂了

 

技术分享
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<queue>
 8 #define maxn 50005
 9 using namespace std;
10 //倍增
11 int n,m,dis[maxn][30],f[maxn][30],dep[maxn],head[maxn];
12 struct edge{
13     int u,v,w,nxt;
14 }e[maxn*10]; 
15 
16 int tot;
17 void adde(int u,int v,int w){
18     e[++tot].u=u;
19     e[tot].v=v;
20     e[tot].w=w;
21     e[tot].nxt=head[u];
22     head[u]=tot;
23 }
24 
25 void build(int u)
26 {
27     for(int i=head[u];i!=-1;i=e[i].nxt){
28         int v=e[i].v,w=e[i].w;
29         if(f[v][0]==0){
30             f[v][0]=u;
31             dep[v]=dep[u]+1;
32             dis[v][0]=w;
33             build(v);
34         }
35     }
36 }
37 
38 void first(){
39     for(int j=1;j<=20;j++){
40         for(int i=1;i<=n;i++){
41             f[i][j]=f[f[i][j-1]][j-1];
42             dis[i][j]=dis[i][j-1]+dis[f[i][j-1]][j-1];
43         }
44     }
45 }
46 
47 int sum=0;
48 int lca(int a,int b){
49     if(dep[a]<dep[b])swap(a,b);//保证a的深度要深一些
50     if(dep[a]!=dep[b]){//让不同深度到相同深度 
51         int d=dep[a]-dep[b];
52         for(int i=0;d;i++){
53             if(d&1){
54                 sum+=dis[a][i];
55                 a=f[a][i];
56             }
57             d=d>>1;//这里是经典的类似二进制的方法分解成2^i1+2^i2+…… 
58         }    
59     }
60     if(a==b)return sum;
61     for(int i=20;i>=0;i--){
62         if(f[a][i]!=f[b][i]){//两个人刚刚好达不到根节点
63         //这样的意义就是不断的缩小向上扩展的深度,可以到达终点
64         //因为是不等于才执行,所以循环完了肯定还是到不了
65             sum+=dis[a][i]+dis[b][i];
66             a=f[a][i];b=f[b][i]; 
67         }
68     }
69     sum+=dis[a][0]+dis[b][0];//2^i=2^i-1+2^i-2+2^1+2^0+2^0
70     return sum;
71      
72 }
73 
74 int main(){
75     memset(head,-1,sizeof(head));
76     scanf("%d",&n);
77     for(int i=1;i<n;i++)
78     {
79         int u,v,w;
80         scanf("%d%d%d",&u,&v,&w);
81         adde(u+1,v+1,w);adde(v+1,u+1,w);
82     }
83     f[1][0]=1;//倍增过界了就默认为到了根节点 
84     build(1);
85     first();
86     scanf("%d",&m);
87     for(int i=1;i<=m;i++)
88     {
89         int a,b;sum=0;
90         scanf("%d%d",&a,&b);
91         int ans=lca(a+1,b+1);
92         printf("%d\n",ans);
93     }
94 }
View Code

 

[codevs2370]小机房的树<LCA>

原文:http://www.cnblogs.com/Danzel-Aria233/p/7669971.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!