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

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

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

分析：

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

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('
');
110          }
111          return 0 ;
112 }

 1 /*
 2     树链剖分 
 3     author : SHHHS
 4     2016-9-28 14:41:17  
 5 */
 6 #include "bits/stdc++.h"
 7 
 8 using namespace std ;
 9 struct Edge { int to , next , val ;};
10 const int maxN = 10010 ;
11 const int INF = 2147483647 ;
12 
13 Edge e[ maxN ] ;
14 int head[ maxN ], ind[ maxN ] ,start [ maxN ],pre[ maxN ],hv[maxN],DFN[maxN],Dis[maxN];
15 
16 int cnt , dfs_num ;
17 
18 void Add_Edge ( const int _x , const int _y , const int _val ) {
19          e[ ++cnt ].to = _y ;
20          e[ cnt ].val = _val ;
21          e[ cnt ].next = head[ _x ] ;
22          head[ _x ] = cnt ;
23 }
24 
25 int Init_DFS ( const int x , const int father ) {
26          int cnt_ , max_ = 0 ;
27          for ( int i=head[ x ] ; i ; i=e[ i ].next ) {
28                   int temp = e[ i ].to ;
29                   if ( temp==father ) continue ;
30                   Dis[ temp ] = Dis[ x ] + e[ i ] .val ;
31                   int _ = Init_DFS ( temp , x ) ;
32                  if ( _ > max_ ) {max_ = _ ; hv[ x ] = temp ;}
33                  cnt_ +=_;
34          }
35          return cnt_ ;
36 }
37 
38 void DFS ( const int x , const int father ) {
39          if ( !start[ x ] ) start[ x ] = start[ father ] ;
40          DFN[ x ] = ++dfs_num ;
41          if ( hv[ x ] ) DFS ( hv[ x ] , x ) ;
42          for ( int i=head[ x ] ; i ; i =e[ i ].next ) {
43                   if ( e[ i ].to != hv[ x ] && e[i].to != father ) {
44                            int temp = e[ i ].to ;
45                            start[ temp ] = temp ;
46                            pre [ temp ] = x ;
47                            DFS ( temp , x ) ;
48                   }
49          }
50 }
51 
52 int LCA ( const int x , const int y ) {
53          int px = x , py = y ;
54          while ( start[px]!=start[py] ) {
55                   if ( DFN[start[px]]>DFN[start[py] ] ) {
56                            px = pre[ start[px] ] ;
57                   }
58                   else {
59                            py = pre[ start[py] ] ;
60                   }
61          }
62          return DFN[px]>DFN[py]?py:px ;
63 }
64 void DEBUG_ ( int n ) {
65          for ( int i=1 ; i<=n ; ++i ) {
66                   printf ("%d:%d
",i,DFN[ i ] ) ;
67          }
68 }
69 int main ( ) {
70          int N , M ;
71          scanf ( "%d" , &N ) ;
72          for ( int i=1 ; i<=N-1 ; ++i ) {
73                   int _x , _y ,_val ;
74                   scanf ( "%d%d%d" ,&_x , &_y ,&_val ) ;
75                   ++_x;++_y;
76                   Add_Edge ( _x , _y , _val ) ;
77                   Add_Edge ( _y , _x , _val ) ;
78          }
79 
80          Init_DFS ( 1 , 1 ) ;
81          start[ 1 ] = 1 ;
82          DFS ( 1 , 1 ) ;
83          
84          //DEBUG_ ( N ) ;  
85          
86          scanf ( "%d" , &M ) ;
87          for ( int i=1 ; i<=M ; ++i ) {
88                   int u , v ;
89                   scanf ( "%d%d" , &u , &v ) ;
90                   ++u,++v;
91                   printf ("%d
",Dis[ u ] + Dis[ v ] - 2*Dis[ LCA ( u , v ) ] ) ;
92          }
93          return 0 ;
94 }

 1 /*
 2      Tarjan LCA 
 3      author : SHHHS
 4      2016-10-09 13:10:32 
 5 */
 6 
 7 #include "cstdio"
 8 #include "cstring"
 9 #include "iostream"
10 
11 using namespace std ; 
12 struct Edge {int to , next , val ; } ;
13 struct Query { int u , v , next ; } ; 
14 const int INF = 2147483647 ;
15 const int maxN = 501000 ;
16 
17 Edge e[ maxN ] ;
18 Query q[ maxN ] ;
19 int head[ maxN ] , qead[ maxN ] , father[ maxN ] , Dis[ maxN ] , lca[ maxN ] ;
20 bool vis[ maxN ] ;
21 
22 void Set_Init ( const int n ) {for ( int i=1 ; i<=n ; ++i ) father[ i ] = i ;}
23 
24 void Add_Edge ( int i , const int x , const int y , const int _val ) {
25         e[ i ].to = y ;
26         e[ i ].val = _val ;
27         e[ i ].next = head[ x ] ;
28         head[ x ] = i ;
29 } 
30 
31 void Add_Query ( int i , const int x , const int y ) {
32         q[ i ].u = x ;
33         q[ i ].v = y ;
34         q[ i ].next = qead[ x ] ;
35         qead[ x ] = i ;
36 }
37 
38 int getfa ( int x ) {
39         return x==father[ x ] ? x : father[ x ] = getfa ( father[ x ] ) ;
40 }
41 
42 void Tarjan ( int x ) {
43         vis[ x ] = true ;
44         for ( int i=head[ x ] ; i ; i = e[ i ].next ) {
45                 int temp = e[ i ].to ;
46                 if ( !vis[ temp ] ) {
47                         Dis[ temp ] = Dis[ x ] + e[ i ].val ;
48                         Tarjan ( temp ) ;
49                         father[ temp ] = x ;
50                 }
51         }
52         
53         for ( int i=qead[ x ] ; i ; i = q[ i ].next ) {
54                 int temp = q[ i ].u == x ? q[ i ].v : q[ i ].u ;
55                 if ( vis[ temp ] )lca[ i >> 1 ] = getfa ( father[ temp ] ) ;
56         }
57 }
58 
59 int getDis(int i)
60 {
61     return Dis[ q [ i << 1 ].u ] + Dis[ q [ i << 1 ].v ] - 2 * Dis [ lca [ i ] ] ; 
62 }
63 void DEBUG_( int n  , int q ) {
64         for ( int i=1 ; i<=n ; ++i ) printf ( "%d " , Dis[ i ] ) ;
65         printf ( "
" ) ;
66         for ( int i=0 ; i<=q ; ++i ) printf ( "%d " , lca[ i ] ) ;
67         printf ( "
" ) ;
68 }
69 
70 int main ( ) {
71         int N , Q ;
72         scanf ( "%d" , &N ) ;
73         for ( int i=1 ; i<=N-1 ; ++i ) {
74                 int _x , _y , _val ;
75                 scanf ( "%d%d%d" , &_x , &_y , &_val ) ;
76                 Add_Edge ( i << 1 , _x + 1 , _y + 1 , _val ) ;
77                 Add_Edge ( i << 1 | 1 , _y + 1 , _x + 1 , _val ) ;
78         }
79         scanf ( "%d" , &Q ) ;
80         for ( int i=1 ; i<=Q ; ++i ){
81                 int _u , _v ;
82                 scanf ( "%d%d" , &_u , &_v ) ;
83                 Add_Query ( i << 1 , _u + 1 , _v + 1 ) ;
84                 Add_Query ( i << 1 | 1 , _v + 1 , _u + 1 ) ;
85         }
86         Set_Init ( N ) ;
87         Tarjan ( 1 ) ;
88         //DEBUG_ ( N , Q ) ;
89         for ( int i=1 ; i<=Q ; ++i ) {
90                 printf ( "%d
" , getDis ( i ) ) ;
91         }
92         return 0 ;
93 }

02:23:34 2016-09-26

(完)

Code[VS] 2370 LCA 题解

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

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