Code[VS] 2370 小机房的树 题解
RMQ
树链剖分
题目描述 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问题。这里使用线段树查询解决。
代码&注释：
/*
LCA
author:SHHHS
2016-09-26 02:25:19
*/ #include "bits/stdc++.h" using namespace std ;
typedef long long QAQ ;
struct Edge { int to , val , next ;};
struct Tree { int l , r , mintr ,pos ;};
int gmin ( int x , int y ) { return x > y ? y : x ;}
int gmax ( int x , int y ) { return x < y ? y : x ;}
const int maxN = ;
const int INF = ; Tree tr[ maxN<< ] ;
Edge e[ maxN ] ;
int cnt , dfs_num= , min_val ,min_pos ;
int head[maxN],fst[maxN],dep[maxN],ver[maxN],Dis[maxN];
bool vis[maxN]; inline void Add_Edge ( int x , int y , int _val ){
e[ ++cnt ].to = y ;
e[ cnt ].val = _val ;
e[ cnt ].next = head[ x ] ;
head[ x ] = cnt ;
} void Build_Tree ( int x , int y , int i ) {
tr[ i ].l = x ; tr[ i ].r = y ;
if ( x==y ) tr[ i ].mintr = dep[ x ] , tr[ i ].pos = x ;
else {
QAQ mid = ( tr[ i ].l + tr[ i ].r ) >> ;
Build_Tree ( x , mid , i<<);
Build_Tree ( mid+ , y , i<<|);
if (tr[i<<].mintr > tr[i<<|].mintr )
tr[ i ].pos = tr[i<<|].pos,tr[ i ].mintr = tr[i<<|].mintr;
else
tr[ i ].pos = tr[ i<< ].pos,tr[ i ].mintr = tr[ i<< ].mintr;
} } void DFS ( int x , int depth ) {
vis[ x ] = true ;
ver[ ++dfs_num ] = x ;
fst[ x ] = dfs_num ;
dep[ dfs_num ] = depth ;
for ( int i=head[ x ] ; i ; i=e[i].next ) {
int temp = e[ i ].to ;
if ( !vis[ temp ] ){
Dis[ temp ] = Dis[ x ] + e[ i ].val ;
DFS ( temp , depth + ) ;
ver[ ++dfs_num ] = x ;
dep[ dfs_num ] = depth ;
}
}
} void Query_Min ( int q , int w , int i ) {
if(q <= tr[i].l && w >= tr[i].r ){
if (tr[ i ].mintr < min_val ){
min_val = tr[i].mintr ;
min_pos = tr[i].pos ;
}
}
else {
QAQ mid = (tr[i].l + tr[i].r ) >> ;
if(q > mid) {
Query_Min ( q , w , i << | );
}
else if(w <= mid) {
Query_Min ( q , w , i << );
}
else {
Query_Min ( q , w , i << ) ;
Query_Min ( q , w , i << | );
}
}
} int LCA ( int x , int y ) {
int px = fst[ x ] , py = fst[ y ] , tmp ;
min_val = INF ;
if ( py < px ) swap ( px , py ) ;
Query_Min ( px , py , ) ;
return ver[ min_pos ] ;
}
int main ( ) {
int N ,M ;
scanf ("%d",&N);
for ( int i= ; i<=N- ; ++i ) {
int _x , _y , __ ;
scanf("%d %d %d" , &_x , &_y ,&__ ) ;
++_x;++_y;
Add_Edge ( _x , _y , __ ) ;
Add_Edge ( _y , _x , __ ) ;
}
DFS ( , ) ;
Build_Tree ( , dfs_num , ) ;
scanf ("%d",&M);
for ( int i= ; i<=M ; ++i ) {
int u , v ;
scanf ( "%d%d" , &u , &v ) ;
++u,++v;
printf ("%d",Dis[u]+Dis[v]-*Dis[LCA ( u , v )] ) ;
putchar('\n');
}
return ;
}
/*
树链剖分
author : SHHHS
2016-9-28 14:41:17
*/
#include "bits/stdc++.h" using namespace std ;
struct Edge { int to , next , val ;};
const int maxN = ;
const int INF = ; Edge e[ maxN ] ;
int head[ maxN ], ind[ maxN ] ,start [ maxN ],pre[ maxN ],hv[maxN],DFN[maxN],Dis[maxN]; int cnt , dfs_num ; void Add_Edge ( const int _x , const int _y , const int _val ) {
e[ ++cnt ].to = _y ;
e[ cnt ].val = _val ;
e[ cnt ].next = head[ _x ] ;
head[ _x ] = cnt ;
} int Init_DFS ( const int x , const int father ) {
int cnt_ , max_ = ;
for ( int i=head[ x ] ; i ; i=e[ i ].next ) {
int temp = e[ i ].to ;
if ( temp==father ) continue ;
Dis[ temp ] = Dis[ x ] + e[ i ] .val ;
int _ = Init_DFS ( temp , x ) ;
if ( _ > max_ ) {max_ = _ ; hv[ x ] = temp ;}
cnt_ +=_;
}
return cnt_ ;
} void DFS ( const int x , const int father ) {
if ( !start[ x ] ) start[ x ] = start[ father ] ;
DFN[ x ] = ++dfs_num ;
if ( hv[ x ] ) DFS ( hv[ x ] , x ) ;
for ( int i=head[ x ] ; i ; i =e[ i ].next ) {
if ( e[ i ].to != hv[ x ] && e[i].to != father ) {
int temp = e[ i ].to ;
start[ temp ] = temp ;
pre [ temp ] = x ;
DFS ( temp , x ) ;
}
}
} int LCA ( const int x , const int y ) {
int px = x , py = y ;
while ( start[px]!=start[py] ) {
if ( DFN[start[px]]>DFN[start[py] ] ) {
px = pre[ start[px] ] ;
}
else {
py = pre[ start[py] ] ;
}
}
return DFN[px]>DFN[py]?py:px ;
}
void DEBUG_ ( int n ) {
for ( int i= ; i<=n ; ++i ) {
printf ("%d:%d\n",i,DFN[ i ] ) ;
}
}
int main ( ) {
int N , M ;
scanf ( "%d" , &N ) ;
for ( int i= ; i<=N- ; ++i ) {
int _x , _y ,_val ;
scanf ( "%d%d%d" ,&_x , &_y ,&_val ) ;
++_x;++_y;
Add_Edge ( _x , _y , _val ) ;
Add_Edge ( _y , _x , _val ) ;
} Init_DFS ( , ) ;
start[ ] = ;
DFS ( , ) ; //DEBUG_ ( N ) ; scanf ( "%d" , &M ) ;
for ( int i= ; i<=M ; ++i ) {
int u , v ;
scanf ( "%d%d" , &u , &v ) ;
++u,++v;
printf ("%d\n",Dis[ u ] + Dis[ v ] - *Dis[ LCA ( u , v ) ] ) ;
}
return ;
}
/*
Tarjan LCA
author : SHHHS
2016-10-09 13:10:32
*/ #include "cstdio"
#include "cstring"
#include "iostream" using namespace std ;
struct Edge {int to , next , val ; } ;
struct Query { int u , v , next ; } ;
const int INF = ;
const int maxN = ; Edge e[ maxN ] ;
Query q[ maxN ] ;
int head[ maxN ] , qead[ maxN ] , father[ maxN ] , Dis[ maxN ] , lca[ maxN ] ;
bool vis[ maxN ] ; void Set_Init ( const int n ) {for ( int i= ; i<=n ; ++i ) father[ i ] = i ;} void Add_Edge ( int i , const int x , const int y , const int _val ) {
e[ i ].to = y ;
e[ i ].val = _val ;
e[ i ].next = head[ x ] ;
head[ x ] = i ;
} void Add_Query ( int i , const int x , const int y ) {
q[ i ].u = x ;
q[ i ].v = y ;
q[ i ].next = qead[ x ] ;
qead[ x ] = i ;
} int getfa ( int x ) {
return x==father[ x ] ? x : father[ x ] = getfa ( father[ x ] ) ;
} void Tarjan ( int x ) {
vis[ x ] = true ;
for ( int i=head[ x ] ; i ; i = e[ i ].next ) {
int temp = e[ i ].to ;
if ( !vis[ temp ] ) {
Dis[ temp ] = Dis[ x ] + e[ i ].val ;
Tarjan ( temp ) ;
father[ temp ] = x ;
}
} for ( int i=qead[ x ] ; i ; i = q[ i ].next ) {
int temp = q[ i ].u == x ? q[ i ].v : q[ i ].u ;
if ( vis[ temp ] )lca[ i >> ] = getfa ( father[ temp ] ) ;
}
} int getDis(int i)
{
return Dis[ q [ i << ].u ] + Dis[ q [ i << ].v ] - * Dis [ lca [ i ] ] ;
}
void DEBUG_( int n , int q ) {
for ( int i= ; i<=n ; ++i ) printf ( "%d " , Dis[ i ] ) ;
printf ( "\n" ) ;
for ( int i= ; i<=q ; ++i ) printf ( "%d " , lca[ i ] ) ;
printf ( "\n" ) ;
} int main ( ) {
int N , Q ;
scanf ( "%d" , &N ) ;
for ( int i= ; i<=N- ; ++i ) {
int _x , _y , _val ;
scanf ( "%d%d%d" , &_x , &_y , &_val ) ;
Add_Edge ( i << , _x + , _y + , _val ) ;
Add_Edge ( i << | , _y + , _x + , _val ) ;
}
scanf ( "%d" , &Q ) ;
for ( int i= ; i<=Q ; ++i ){
int _u , _v ;
scanf ( "%d%d" , &_u , &_v ) ;
Add_Query ( i << , _u + , _v + ) ;
Add_Query ( i << | , _v + , _u + ) ;
}
Set_Init ( N ) ;
Tarjan ( ) ;
//DEBUG_ ( N , Q ) ;
for ( int i= ; i<=Q ; ++i ) {
printf ( "%d\n" , getDis ( i ) ) ;
}
return ;
}
02:23:34 2016-09-26
(完)