#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std ;
#define MAXN 200007
int n ;
vector < int > v[ MAXN ] ;
int used[ MAXN ] ;
bool fl[ MAXN ] ;
vector < int > cycle ;
int h ;
int term ;
int rdist[ MAXN ] ;
int rways[ MAXN ] ;
int diam[ MAXN ] ;
long long dways[ MAXN ] ;
void find_cycle ( int vertex , int prv ) {
used[ vertex ] = 1 ;
int i ;
int sz = v[ vertex ].size ( ) ;
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ] == prv ) { continue ; }
if ( used[ v[ vertex ][ i ] ] == 0 ) {
find_cycle ( v[ vertex ][ i ] , vertex ) ;
}
else if ( used[ v[ vertex ][ i ] ] == 1 ) {
h = 1 ;
term = used[ v[ vertex ][ i ] ] ;
}
if ( h != 0 ) { break ; }
}
if ( h != 0 ) {
if ( h == 1 ) {
fl[ vertex ] = true ;
cycle.push_back ( vertex ) ;
}
if ( vertex == term ) { h = 2 ; }
}
used[ vertex ] = 2 ;
}
void dfs ( int vertex , int prv ) {
int i ;
int sz = v[ vertex ].size ( ) ;
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ] == prv ) { continue ; }
if ( fl[ v[ vertex ][ i ] ] == true ) { continue ; }
dfs ( v[ vertex ][ i ] , vertex ) ;
}
rdist[ vertex ] = -1 ;
rways[ vertex ] = 1 ;
dways[ vertex ] = 1 ;
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ] == prv ) { continue ; }
if ( fl[ v[ vertex ][ i ] ] == true ) { continue ; }
if ( rdist[ v[ vertex ][ i ] ] + rdist[ vertex ] + 1 > diam[ vertex ] ) {
diam[ vertex ] = rdist[ v[ vertex ][ i ] ] + rdist[ vertex ] + 1 ;
dways[ vertex ] = 0 ;
}
if ( rdist[ v[ vertex ][ i ] ] + rdist[ vertex ] + 1 == diam[ vertex ] ) {
dways[ vertex ] += 1LL * rways[ vertex ] * rways[ v[ vertex ][ i ] ] ;
}
if ( rdist[ vertex ] < rdist[ v[ vertex ][ i ] ] + 1 ) {
rdist[ vertex ] = rdist[ v[ vertex ][ i ] ] + 1 ;
rways[ vertex ] = 0 ;
}
if ( rdist[ vertex ] == rdist[ v[ vertex ][ i ] ] + 1 ) {
rways[ vertex ] ++ ;
}
}
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ] == prv ) { continue ; }
if ( fl[ v[ vertex ][ i ] ] == true ) { continue ; }
if ( diam[ v[ vertex ][ i ] ] > diam[ vertex ] ) {
diam[ vertex ] = diam[ v[ vertex ][ i ] ] ;
dways[ vertex ] = 0 ;
}
if ( diam[ v[ vertex ][ i ] ] == diam[ vertex ] ) {
dways[ vertex ] += dways[ v[ vertex ][ i ] ] ;
}
}
if ( rdist[ vertex ] < 0 ) { rdist[ vertex ] = 0 ; }
}
class Tree {
public :
int lazy[ 5 * MAXN ] ;
int tr[ 5 * MAXN ] ;
int ways[ 5 * MAXN ] ;
void merge ( int where ) {
if ( tr[ 2 * where ] > tr[ 2 * where + 1 ] ) {
tr[ where ] = tr[ 2 * where ] ;
ways[ where ] = ways[ 2 * where ] ;
}
else if ( tr[ 2 * where ] < tr[ 2 * where + 1 ] ) {
tr[ where ] = tr[ 2 * where + 1 ] ;
ways[ where ] = ways[ 2 * where + 1 ] ;
}
else {
tr[ where ] = tr[ 2 * where ] ;
ways[ where ] = ( ways[ 2 * where ] + ways[ 2 * where + 1 ] ) ;
}
}
void push_lazy ( int where , int IL , int IR ) {
if ( lazy[ where ] == 0 ) { return ; }
tr[ where ] += lazy[ where ] ;
if ( IL != IR ) {
lazy[ 2 * where ] += lazy[ where ] ;
lazy[ 2 * where + 1 ] += lazy[ where ] ;
}
lazy[ where ] = 0 ;
}
void init ( int where , int IL , int IR ) {
lazy[ where ] = 0 ;
if ( IL == IR ) {
tr[ where ] = rdist[ cycle[ IL - 1 ] ] ;
ways[ where ] = rways[ cycle[ IL - 1 ] ] ;
tr[ where ] += min ( IL - 1 , (int)cycle.size ( ) - IL + 1 ) ;
return ;
}
int mid = ( IL + IR ) / 2 ;
init ( 2 * where , IL , mid ) ;
init ( 2 * where + 1 , mid + 1 , IR ) ;
merge ( where ) ;
}
void update ( int where , int IL , int IR , int CURL , int CURR , int val ) {
push_lazy ( where , IL , IR ) ;
if ( IR < CURL || CURR < IL ) { return ; }
if ( CURL <= IL && IR <= CURR ) {
lazy[ where ] += val ;
push_lazy ( where , IL , IR ) ;
return ;
}
int mid = ( IL + IR ) / 2 ;
update ( 2 * where , IL , mid , CURL , CURR , val ) ;
update ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , val ) ;
merge ( where ) ;
}
pair < int , int > query ( int where , int IL , int IR , int CURL , int CURR ) {
if ( IR < IL ) { return make_pair ( 0 , 0 ) ; }
push_lazy ( where , IL , IR ) ;
if ( IR < CURL || CURR < IL ) { return make_pair ( 0 , 0 ) ; }
if ( CURL <= IL && IR <= CURR ) {
return make_pair ( tr[ where ] , ways[ where ] ) ;
}
int mid = ( IL + IR ) / 2 ;
pair < int , int > ret1 , ret2 ;
ret1 = query ( 2 * where , IL , mid , CURL , CURR ) ;
ret2 = query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ;
if ( ret1.first < ret2.first ) { swap ( ret1 , ret2 ) ; }
if ( ret1.first == ret2.first ) { ret1.second += ret2.second ; }
return ret1 ;
}
};
Tree w ;
void input ( ) {
scanf ( "%d" , &n ) ;
int i ;
for ( i = 1 ; i <= n ; i ++ ) {
int x , y ;
scanf ( "%d%d" , &x , &y ) ;
v[ x ].push_back ( y ) ;
v[ y ].push_back ( x ) ;
}
}
void solve ( ) {
find_cycle ( 1 , -1 ) ;
int sz = cycle.size ( ) ;
int i ;
for ( i = 0 ; i < sz ; i ++ ) {
dfs ( cycle[ i ] , -1 ) ;
}
int ans = 0 ;
int tm = 1 ;
/**
for ( i = 0 ; i < sz ; i ++ ) {
printf ( "--- %d\n" , cycle[ i ] ) ;
printf ( "%d %d\n" , rdist[ cycle[ i ] ] , rways[ cycle[ i ] ] ) ;
printf ( "%d %d\n" , diam[ cycle[ i ] ] , dways[ cycle[ i ] ] ) ;
}
**/
for ( i = 0 ; i < sz ; i ++ ) {
if ( ans < diam[ cycle[ i ] ] ) {
ans = diam[ cycle[ i ] ] ;
tm = 0 ;
}
if ( ans == diam[ cycle[ i ] ] ) {
tm += dways[ cycle[ i ] ] ;
}
}
w.init ( 1 , 1 , sz ) ;
int rem1 = tm ;
if ( ans != ( sz / 2 ) ) { rem1 = 0 ; }
for ( i = 1 ; i <= sz ; i ++ ) {
pair < int , int > ret1 , ret2 ;
ret1 = w.query ( 1 , 1 , sz , i + 1 , sz ) ;
ret2 = w.query ( 1 , 1 , sz , 1 , i - 1 ) ;
if ( ret1.first < ret2.first ) { swap ( ret1 , ret2 ) ; }
if ( ret1.first == ret2.first ) { ret1.second += ret2.second ; }
ret1.first += rdist[ cycle[ i - 1 ] ] ;
int opp = i + ( n + 1 ) / 2 ;
if ( opp > n ) { opp -= n ; }
if ( ( n % 2 ) == 0 ) {
pair < int , int > ret3 = w.query ( 1 , 1 , sz , opp , opp ) ;
ret3.first += rdist[ cycle[ i - 1 ] ] ;
if ( ret1.first == ret3.first ) {
ret1.second += ret3.second ;
}
}
if ( ans < ret1.first ) {
ans = ret1.first ;
tm = 0 ;
}
if ( ans == ret1.first ) {
tm += ret1.second ;
}
if ( (sz % 2) == 1 ) {
if ( i <= opp ) {
w.update ( 1 , 1 , sz , i + 1 , opp - 1 , -1 ) ;
w.update ( 1 , 1 , sz , opp + 1 , sz , 1 ) ;
w.update ( 1 , 1 , sz , 1 , i , 1 ) ;
}
else {
w.update ( 1 , 1 , sz , i + 1 , sz , -1 ) ;
w.update ( 1 , 1 , sz , 1 , opp - 1 , -1 ) ;
w.update ( 1 , 1 , sz , opp + 1 , i , 1 ) ;
}
}
else {
if ( i <= opp ) {
w.update ( 1 , 1 , sz , i + 1 , opp , -1 ) ;
w.update ( 1 , 1 , sz , opp + 1 , sz , 1 ) ;
w.update ( 1 , 1 , sz , 1 , i , 1 ) ;
}
else {
w.update ( 1 , 1 , sz , i + 1 , sz , -1 ) ;
w.update ( 1 , 1 , sz , 1 , opp , -1 ) ;
w.update ( 1 , 1 , sz , opp + 1 , i , 1 ) ;
}
}
}
if ( ans == ( sz / 2 ) ) {
tm -= ( tm - rem1 ) / 2 ;
}
printf ( "%d\n" , tm ) ;
}
int main ( ) {
input ( ) ;
solve ( ) ;
return 0 ;
}
Compilation message
shymbulak.cpp: In function 'void input()':
shymbulak.cpp:169:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ( "%d" , &n ) ;
^
shymbulak.cpp:173:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ( "%d%d" , &x , &y ) ;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
23332 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
23332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
23332 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
23332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
103 ms |
26368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
