首页 > 代码库 > Code[VS] 2370 LCA 题解

Code[VS] 2370 LCA 题解

Code[VS] 2370 小机房的树 题解

题目描述 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

3

1 0 1

2 0 1

3

1 0

2 0

1 2

样例输出 Sample Output

1

1

2

数据范围及提示 Data Size & Hint

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

———————————————————————————分割线—————————————————————————————

分析:

这道题是一个比较明显的求树上路径的题,显然

Ans = dis[ u ] + dis[v] - 2*dis[ LCA( u , v ) ]   

所以本题核心是求LCA ,将LCA问题转化为RMQ问题。这里使用线段树查询解决。

代码&注释:

 

  1 /*  2     LCA   3     author:SHHHS  4     2016-09-26 02:25:19   5 */  6   7 #include "bits/stdc++.h"  8   9 using namespace std ; 10 typedef long long QAQ ; 11 struct Edge { int to , val , next ;}; 12 struct Tree { int l , r , mintr ,pos ;}; 13 int gmin ( int x , int y ) { return x > y ? y : x ;} 14 int gmax ( int x , int y ) { return x < y ? y : x ;} 15 const int maxN = 200010 ; 16 const int INF = 2147483647 ; 17  18 Tree tr[ maxN<<2 ] ; 19 Edge e[ maxN ] ; 20 int cnt , dfs_num=0 , min_val ,min_pos ; 21 int head[maxN],fst[maxN],dep[maxN],ver[maxN],Dis[maxN]; 22 bool vis[maxN]; 23  24 inline void Add_Edge ( int x , int y , int _val ){ 25          e[ ++cnt ].to = y ; 26          e[ cnt ].val = _val ; 27          e[ cnt ].next = head[ x ] ; 28          head[ x ] = cnt ; 29 } 30  31 void Build_Tree ( int x , int y , int i ) { 32          tr[ i ].l = x ; tr[ i ].r = y ; 33          if ( x==y ) tr[ i ].mintr = dep[ x ] , tr[ i ].pos = x ; 34          else { 35                   QAQ mid = ( tr[ i ].l + tr[ i ].r ) >>1 ; 36                  Build_Tree ( x , mid , i<<1); 37                  Build_Tree ( mid+1 , y , i<<1|1); 38                  if (tr[i<<1].mintr > tr[i<<1|1].mintr ) 39                           tr[ i ].pos = tr[i<<1|1].pos,tr[ i ].mintr = tr[i<<1|1].mintr; 40                  else  41                          tr[ i ].pos = tr[ i<<1 ].pos,tr[ i ].mintr = tr[ i<<1 ].mintr; 42          } 43           44 } 45  46 void DFS ( int x , int depth ) { 47          vis[ x ] = true ;  48          ver[ ++dfs_num ] = x ;  49          fst[ x ] = dfs_num ;  50          dep[ dfs_num ] = depth ; 51          for ( int i=head[ x ] ; i ; i=e[i].next ) { 52                   int temp = e[ i ].to ; 53                   if ( !vis[ temp ] ){ 54                            Dis[ temp ] = Dis[ x ] + e[ i ].val ; 55                            DFS ( temp , depth + 1 ) ; 56                            ver[ ++dfs_num ] = x ;  57                            dep[ dfs_num ] = depth ; 58                  } 59          } 60 } 61  62 void Query_Min ( int q , int w , int i ) { 63          if(q <= tr[i].l && w >= tr[i].r ){ 64                   if (tr[ i ].mintr < min_val ){ 65                            min_val = tr[i].mintr ; 66                            min_pos = tr[i].pos ; 67                   } 68          } 69          else { 70                   QAQ mid = (tr[i].l + tr[i].r ) >> 1; 71                   if(q > mid) { 72                           Query_Min ( q , w , i << 1 | 1); 73                   } 74                   else if(w <= mid) { 75                           Query_Min ( q , w , i << 1); 76                   } 77                   else { 78                           Query_Min ( q , w , i << 1) ; 79                           Query_Min ( q , w , i << 1 | 1); 80                   } 81          } 82 } 83  84 int LCA ( int x , int y ) { 85          int px = fst[ x ] , py = fst[ y ] , tmp ; 86          min_val = INF ; 87          if ( py < px ) swap ( px , py ) ; 88          Query_Min ( px , py , 1 ) ; 89          return ver[ min_pos ] ; 90 } 91 int main ( ) { 92          int N ,M ; 93          scanf ("%d",&N); 94          for ( int i=1 ; i<=N-1 ; ++i ) { 95                   int _x , _y , __ ; 96                   scanf("%d %d %d" , &_x , &_y ,&__ ) ; 97                   ++_x;++_y; 98                   Add_Edge ( _x , _y , __ ) ; 99                   Add_Edge ( _y , _x , __ ) ;100          }101          DFS ( 1 , 1 ) ;102          Build_Tree ( 1 , dfs_num , 1 ) ;103          scanf ("%d",&M);104          for ( int i=1 ; i<=M ; ++i ) {105                   int u , v ;106                   scanf ( "%d%d" , &u , &v ) ;107                   ++u,++v;108                   printf ("%d",Dis[u]+Dis[v]-2*Dis[LCA ( u , v )] ) ;109                   putchar(\n);110          }111          return 0 ;112 }

 

 

 

02:23:34 2016-09-26

(完)

Code[VS] 2370 LCA 题解