BZOJ-1063: [Noi2008]道路设计(树DP)
2019-03-15 本文已影响0人
AmadeusChan
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1063
首先想了好久才发现这是一棵树，每个点最多连一条边，最右的点不连，所以n-1条边，然后连通，所以是树。
接下来就很好做啦，dp(v,0),dp(v,1),dp(v,2)分别表示在v不在链上，在链一端，在链中间，v子树的最小不便利度，然后就可以直接dp掉了，然后考虑第二问，我们发现最小不便利度一定不是超过log n（轻重树链剖分都log n了嘛），所以f(i,j,0),f(i,j,1),f(i,j,2)分别表示三种情况下不便利值为j的情况，然后处理个前缀和dp一下，总复杂度O(n + n log n)。
代码（细节超多QAQ）：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )
#define Rep( i , x ) for ( int i = 0 ; i < x ; ++ i )
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )
#define travel( x ) for ( edge *p = head[ x ] ; p ; p = p -> next )
const int maxn = 101000 ;
const int maxm = 201000 ;
struct edge {
edge *next ;
int t ;
} E[ maxm ] ;
edge *pt = E , *head[ maxn ] ;
inline void add( int s , int t ) {
pt -> t = t , pt -> next = head[ s ] ; head[ s ] = pt ++ ;
}
inline void addedge( int s , int t ) {
add( s , t ) , add( t , s ) ;
}
bool used[ maxn ] ;
int n , m , q ;
void dfs( int now ) {
used[ now ] = true ;
travel( now ) if ( ! used[ p -> t ] ) dfs( p -> t ) ;
}
int dp[ maxn ][ 3 ] , ch[ maxn ] , f[ maxn ][ 3 ] , ans ;
const int inf = 0x7fffffff ;
void Dp0( int now , int fa ) {
travel( now ) if ( p -> t != fa ) Dp0( p -> t , now ) ;
int cnt = 0 ;
dp[ now ][ 0 ] = 0 ;
travel( now ) if ( p -> t != fa ) ch[ ++ cnt ] = p -> t ;
f[ 0 ][ 0 ] = 0 , f[ 0 ][ 1 ] = f[ 0 ][ 2 ] = inf ;
rep( i , cnt ) {
int v = ch[ i ] ;
f[ i ][ 0 ] = max( f[ i - 1 ][ 0 ] , min( min( dp[ v ][ 0 ] , dp[ v ][ 1 ] ) , dp[ v ][ 2 ] ) + 1 ) ;
f[ i ][ 1 ] = min( max( f[ i - 1 ][ 1 ] , min( min( dp[ v ][ 0 ] , dp[ v ][ 1 ] ) , dp[ v ][ 2 ] ) + 1 ) , max( f[ i - 1 ][ 0 ] , min( dp[ v ][ 0 ] , dp[ v ][ 1 ] ) ) ) ;
f[ i ][ 2 ] = min( max( f[ i - 1 ][ 2 ] , min( min( dp[ v ][ 0 ] , dp[ v ][ 1 ] ) , dp[ v ][ 2 ] ) + 1 ) , max( f[ i - 1 ][ 1 ] , min( dp[ v ][ 0 ] , dp[ v ][ 1 ] ) ) ) ;
}
dp[ now ][ 0 ] = f[ cnt ][ 0 ] , dp[ now ][ 1 ] = f[ cnt ][ 1 ] , dp[ now ][ 2 ] = f[ cnt ][ 2 ] ;
}
const int maxd = 20 ;
typedef long long ll ;
int Dp[ maxn ][ maxd ][ 3 ] , sum[ maxn ][ maxd ][ 3 ] , g[ maxn ][ 3 ][ 2 ] ;
void Dp1( int now , int fa ) {
int cnt = 0 , v , a , b , c , d ;
travel( now ) if ( p -> t != fa ) {
++ cnt ; Dp1( p -> t , now ) ;
}
if ( ! cnt ) {
REP( i , 0 , ans ) {
Dp[ now ][ i ][ 0 ] = Dp[ now ][ i ][ 1 ] = Dp[ now ][ i ][ 2 ] = 0 ;
}
Dp[ now ][ 0 ][ 0 ] = 1 ; return ;
}
cnt = 0 ;
travel( now ) if ( p -> t != fa ) ch[ ++ cnt ] = p -> t ;
Dp[ now ][ 0 ][ 0 ] = 0 ;
if ( cnt == 1 ) {
Dp[ now ][ 0 ][ 2 ] = 0 ;
Dp[ now ][ 0 ][ 1 ] = ( Dp[ ch[ 1 ] ][ 0 ][ 0 ] + Dp[ ch[ 1 ] ][ 0 ][ 1 ] ) % q ;
} else if ( cnt == 2 ) {
Dp[ now ][ 0 ][ 1 ] = 0 ;
Dp[ now ][ 0 ][ 2 ] = ( ll ) ( Dp[ ch[ 1 ] ][ 0 ][ 0 ] + Dp[ ch[ 1 ] ][ 0 ][ 1 ] ) * ( Dp[ ch[ 2 ] ][ 0 ][ 0 ] + Dp[ ch[ 2 ] ][ 0 ][ 1 ] ) % q ;
} else {
Dp[ now ][ 0 ][ 1 ] = Dp[ now ][ 0 ][ 2 ] = 0 ;
}
rep( i , cnt ) {
int v = ch[ i ] ;
sum[ i ][ 0 ][ 0 ] = Dp[ v ][ 0 ][ 0 ] , sum[ i ][ 0 ][ 1 ] = Dp[ v ][ 0 ][ 1 ] , sum[ i ][ 0 ][ 2 ] = Dp[ v ][ 0 ][ 2 ] ;
REP( j , 1 , ans ) {
sum[ i ][ j ][ 0 ] = ( sum[ i ][ j - 1 ][ 0 ] + Dp[ v ][ j ][ 0 ] ) % q ;
sum[ i ][ j ][ 1 ] = ( sum[ i ][ j - 1 ][ 1 ] + Dp[ v ][ j ][ 1 ] ) % q ;
sum[ i ][ j ][ 2 ] = ( sum[ i ][ j - 1 ][ 2 ] + Dp[ v ][ j ][ 2 ] ) % q ;
}
}
REP( j , 1 , ans ) {
g[ 0 ][ 0 ][ 0 ] = g[ 0 ][ 0 ][ 1 ] = g[ 0 ][ 1 ][ 0 ] = g[ 0 ][ 1 ][ 1 ] = g[ 0 ][ 2 ][ 0 ] = g[ 0 ][ 2 ][ 1 ] = 0 ;
g[ 0 ][ 0 ][ 0 ] = 1 ;
rep( i , cnt ) {
int v = ch[ i ] ;
g[ i ][ 0 ][ 0 ] = ( ll ) g[ i - 1 ][ 0 ][ 0 ] * ( j - 2 >= 0 ? ( sum[ i ][ j - 2 ][ 0 ] + sum[ i ][ j - 2 ][ 1 ] + sum[ i ][ j - 2 ][ 2 ] ) : 0 ) % q ;
a = ( ll ) g[ i - 1 ][ 0 ][ 0 ] * ( Dp[ v ][ j - 1 ][ 0 ] + Dp[ v ][ j - 1 ][ 1 ] + Dp[ v ][ j - 1 ][ 2 ] ) % q ;
b = ( ll ) g[ i - 1 ][ 0 ][ 1 ] * ( sum[ i ][ j - 1 ][ 0 ] + sum[ i ][ j - 1 ][ 1 ] + sum[ i ][ j - 1 ][ 2 ] ) % q ;
g[ i ][ 0 ][ 1 ] = ( a + b ) % q ;
a = ( ll ) g[ i - 1 ][ 0 ][ 0 ] * ( sum[ i ][ j - 1 ][ 0 ] + sum[ i ][ j - 1 ][ 1 ] ) % q ;
b = ( ll ) g[ i - 1 ][ 1 ][ 0 ] * ( j - 2 >= 0 ? ( sum[ i ][ j - 2 ][ 0 ] + sum[ i ][ j - 2 ][ 1 ] + sum[ i ][ j - 2 ][ 2 ] ) : 0 ) % q ;
g[ i ][ 1 ][ 0 ] = ( a + b ) % q ;
a = ( ll ) g[ i - 1 ][ 0 ][ 0 ] * ( Dp[ v ][ j ][ 0 ] + Dp[ v ][ j ][ 1 ] ) % q ;
b = ( ll ) g[ i - 1 ][ 0 ][ 1 ] * ( sum[ i ][ j ][ 0 ] + sum[ i ][ j ][ 1 ] ) % q ;
c = ( ll ) g[ i - 1 ][ 1 ][ 0 ] * ( Dp[ v ][ j - 1 ][ 0 ] + Dp[ v ][ j - 1 ][ 1 ] + Dp[ v ][ j - 1 ][ 2 ] ) % q ;
d = ( ll ) g[ i - 1 ][ 1 ][ 1 ] * ( sum[ i ][ j - 1 ][ 0 ] + sum[ i ][ j - 1 ][ 1 ] + sum[ i ][ j - 1 ][ 2 ] ) % q ;
g[ i ][ 1 ][ 1 ] = ( a + b + c + d ) % q ;
a = ( ll ) g[ i - 1 ][ 1 ][ 0 ] * ( sum[ i ][ j - 1 ][ 0 ] + sum[ i ][ j - 1 ][ 1 ] ) % q ;
b = ( ll ) g[ i - 1 ][ 2 ][ 0 ] * ( j - 2 >= 0 ? ( sum[ i ][ j - 2 ][ 0 ] + sum[ i ][ j - 2 ][ 1 ] + sum[ i ][ j - 2 ][ 2 ] ) : 0 ) % q ;
g[ i ][ 2 ][ 0 ] = ( a + b ) % q ;
a = ( ll ) g[ i - 1 ][ 1 ][ 0 ] * ( Dp[ v ][ j ][ 0 ] + Dp[ v ][ j ][ 1 ] ) % q ;
b = ( ll ) g[ i - 1 ][ 1 ][ 1 ] * ( sum[ i ][ j ][ 0 ] + sum[ i ][ j ][ 1 ] ) % q ;
c = ( ll ) g[ i - 1 ][ 2 ][ 0 ] * ( Dp[ v ][ j - 1 ][ 0 ] + Dp[ v ][ j - 1 ][ 1 ] + Dp[ v ][ j - 1 ][ 2 ] ) % q ;
d = ( ll ) g[ i - 1 ][ 2 ][ 1 ] * ( sum[ i ][ j - 1 ][ 0 ] + sum[ i ][ j - 1 ][ 1 ] + sum[ i ][ j - 1 ][ 2 ] ) % q ;
g[ i ][ 2 ][ 1 ] = ( a + b + c + d ) % q ;
}
Dp[ now ][ j ][ 0 ] = g[ cnt ][ 0 ][ 1 ] ;
Dp[ now ][ j ][ 1 ] = g[ cnt ][ 1 ][ 1 ] ;
Dp[ now ][ j ][ 2 ] = g[ cnt ][ 2 ][ 1 ] ;
}
}
int main( ) {
memset( head , 0 , sizeof( head ) ) ;
scanf( "%d%d%d" , &n , &m , &q ) ;
while ( m -- ) {
int s , t ; scanf( "%d%d" , &s , &t ) ; addedge( s , t ) ;
}
memset( used , false , sizeof( used ) ) ;
dfs( 1 ) ;
rep( i , n ) if ( ! used[ i ] ) {
printf( "-1\n-1\n" ) ; return 0 ;
}
Dp0( 1 , 0 ) ;
printf( "%d\n" , ans = min( dp[ 1 ][ 0 ] , min( dp[ 1 ][ 1 ] , dp[ 1 ][ 2 ] ) ) ) ;
Dp1( 1 , 0 ) ;
printf( "%d\n" , ( Dp[ 1 ][ ans ][ 0 ] + Dp[ 1 ][ ans ][ 1 ] + Dp[ 1 ][ ans ][ 2 ] ) % q ) ;
return 0 ;
}
