#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std ;
#define MAXN 500007
int n ;
vector < int > v[ MAXN ] ;
struct tuhla {
int val ;
int tm ;
tuhla ( ) { val = tm = 0 ; }
tuhla ( int _val , int _tm ) {
val = _val ;
tm = _tm ;
}
};
tuhla dp[ MAXN ] ;
tuhla up[ MAXN ] ;
tuhla ret[ MAXN ][ 7 ] ;
long long ans ;
long long tot ;
vector < int > pos ;
tuhla update ( tuhla cur , int x , int y ) {
if ( cur.val < x ) { cur.val = x ; cur.tm = 0 ; }
if ( cur.val == x ) { cur.tm += y ; }
return cur ;
}
void dfs_down ( int vertex , int prv ) {
int i ;
int sz = v[ vertex ].size ( ) ;
dp[ vertex ] = tuhla ( 0 , 1 ) ;
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ] == prv ) { continue ; }
dfs_down ( v[ vertex ][ i ] , vertex ) ;
dp[ vertex ] = update ( dp[ vertex ] , dp[ v[ vertex ][ i ] ].val + 1 , dp[ v[ vertex ][ i ] ].tm ) ;
}
}
void dfs_up ( int vertex , int prv ) {
int i ;
int sz = v[ vertex ].size ( ) ;
tuhla p1 , p2 ;
int id1 , id2 ;
id1 = 0 ;
id2 = 0 ;
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ] == prv ) { continue ; }
up[ v[ vertex ][ i ] ] = tuhla ( 0 , 1 ) ;
up[ v[ vertex ][ i ] ] = update ( up[ v[ vertex ][ i ] ] , up[ vertex ].val + 1 , up[ vertex ].tm ) ;
}
tuhla cur = tuhla ( -50 , 1 ) ;
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ] == prv ) { continue ; }
up[ v[ vertex ][ i ] ] = update ( up[ v[ vertex ][ i ] ] , cur.val , cur.tm ) ;
cur = update ( cur , dp[ v[ vertex ][ i ] ].val + 2 , dp[ v[ vertex ][ i ] ].tm ) ;
}
cur = tuhla ( -50 , 1 ) ;
for ( i = sz - 1 ; i >= 0 ; i -- ) {
if ( v[ vertex ][ i ] == prv ) { continue ; }
up[ v[ vertex ][ i ] ] = update ( up[ v[ vertex ][ i ] ] , cur.val , cur.tm ) ;
cur = update ( cur , dp[ v[ vertex ][ i ] ].val + 2 , dp[ v[ vertex ][ i ] ].tm ) ;
}
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ] == prv ) { continue ; }
dfs_up ( v[ vertex ][ i ] , vertex ) ;
}
}
void recalc ( tuhla &best1 , tuhla &best2 , tuhla &best3 , int x , int y ) {
if ( best1.val < x ) {
best3 = best2 ;
best2 = best1 ;
best1 = tuhla ( x , y ) ;
}
else if ( best2.val < x ) {
best3 = best2 ;
best2 = tuhla ( x , y ) ;
}
else {
best3 = tuhla ( x , y ) ;
}
}
void get_mx ( int vertex , int prv ) {
tuhla best1 , best2 , best3 ;
best1 = tuhla ( -50 , 1 ) ;
best2 = tuhla ( -50 , 1 ) ;
best3 = tuhla ( -50 , 1 ) ;
int i ;
int sz = v[ vertex ].size ( ) ;
if ( prv != -1 ) {
recalc ( best1 , best2 , best3 , up[ vertex ].val , up[ vertex ].tm ) ;
}
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ] == prv ) { continue ; }
recalc ( best1 , best2 , best3 , dp[ v[ vertex ][ i ] ].val + 1 , dp[ v[ vertex ][ i ] ].tm ) ;
}
if ( best3.val != -50 ) {
long long aux = 1LL * best1.val * ( best2.val + best3.val ) ;
if ( ans < aux ) {
pos.clear ( ) ;
ans = aux ;
}
if ( ans == aux ) {
pos.push_back ( vertex ) ;
}
}
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ] == prv ) { continue ; }
get_mx ( v[ vertex ][ i ] , vertex ) ;
}
}
long long calc_fixed_len ( int vertex , int len ) {
int i ;
long long ret = 0 ;
int sz = v[ vertex ].size ( ) ;
for ( i = 0 ; i < sz ; i ++ ) {
if ( dp[ v[ vertex ][ i ] ].val + 1 == len ) { ret += dp[ v[ vertex ][ i ] ].tm ; }
}
return ret ;
}
long long calc_double ( int vertex , int len ) {
int i ;
long long ret = 0 ;
long long sm = 0 ;
int sz = v[ vertex ].size ( ) ;
for ( i = 0 ; i < sz ; i ++ ) {
if ( dp[ v[ vertex ][ i ] ].val + 1 == len ) {
ret += sm * dp[ v[ vertex ][ i ] ].tm ;
sm += dp[ v[ vertex ][ i ] ].tm ;
}
}
return ret ;
}
void get_combinations ( int vertex ) {
dfs_down ( vertex , -1 ) ;
tuhla best1 , best2 , best3 ;
best1 = tuhla ( -50 , 1 ) ;
best2 = tuhla ( -50 , 1 ) ;
best3 = tuhla ( -50 , 1 ) ;
int i ;
int sz = v[ vertex ].size ( ) ;
for ( i = 0 ; i < sz ; i ++ ) {
recalc ( best1 , best2 , best3 , dp[ v[ vertex ][ i ] ].val + 1 , dp[ v[ vertex ][ i ] ].tm ) ;
}
if ( best1.val != best2.val && best2.val != best3.val ) {
long long aux1 , aux2 ;
aux1 = best2.tm ;
aux2 = calc_fixed_len ( vertex , best3.val ) ;
tot += aux1 * aux2 ;
}
else if ( best1.val == best2.val && best2.val != best3.val ) {
long long aux1 , aux2 ;
aux1 = best1.tm + best2.tm ;
aux2 = calc_fixed_len ( vertex , best3.val ) ;
tot += aux1 * aux2 ;
}
else {
tot += calc_double( vertex , best2.val ) ;
}
}
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 ( ) {
int i ;
int leaves = 0 ;
for ( i = 1 ; i <= n ; i ++ ) {
leaves += ( v[ i ].size ( ) == 1 ) ;
}
if ( leaves == 2 ) { printf ( "0 1\n" ) ; return ; }
dfs_down ( 1 , -1 ) ;
up[ 1 ] = tuhla ( 0 , 1 ) ;
dfs_up ( 1 , -1 ) ;
get_mx ( 1 , -1 ) ;
int sz = pos.size ( ) ;
for ( i = 0 ; i < sz ; i ++ ) {
get_combinations ( pos[ i ] ) ;
}
printf ( "%lld %lld\n" , ans , tot ) ;
}
int main ( ) {
input ( ) ;
solve ( ) ;
return 0 ;
}
Compilation message
road.cpp: In function 'void dfs_up(int, int)':
road.cpp:49:9: warning: variable 'id1' set but not used [-Wunused-but-set-variable]
int id1 , id2 ;
^
road.cpp:49:15: warning: variable 'id2' set but not used [-Wunused-but-set-variable]
int id1 , id2 ;
^
road.cpp: In function 'void input()':
road.cpp:173:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ( "%d" , &n ) ;
^
road.cpp:177: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 |
6 ms |
48896 KB |
Output is correct |
| 2 |
Correct |
13 ms |
48896 KB |
Output is correct |
| 3 |
Correct |
13 ms |
48896 KB |
Output is correct |
| 4 |
Correct |
13 ms |
48896 KB |
Output is correct |
| 5 |
Correct |
16 ms |
48896 KB |
Output is correct |
| 6 |
Correct |
9 ms |
48896 KB |
Output is correct |
| 7 |
Correct |
13 ms |
48896 KB |
Output is correct |
| 8 |
Incorrect |
6 ms |
48896 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
48896 KB |
Output is correct |
| 2 |
Correct |
13 ms |
48896 KB |
Output is correct |
| 3 |
Correct |
13 ms |
48896 KB |
Output is correct |
| 4 |
Correct |
13 ms |
48896 KB |
Output is correct |
| 5 |
Correct |
16 ms |
48896 KB |
Output is correct |
| 6 |
Correct |
9 ms |
48896 KB |
Output is correct |
| 7 |
Correct |
13 ms |
48896 KB |
Output is correct |
| 8 |
Incorrect |
6 ms |
48896 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
48896 KB |
Output is correct |
| 2 |
Correct |
13 ms |
48896 KB |
Output is correct |
| 3 |
Correct |
13 ms |
48896 KB |
Output is correct |
| 4 |
Correct |
13 ms |
48896 KB |
Output is correct |
| 5 |
Correct |
16 ms |
48896 KB |
Output is correct |
| 6 |
Correct |
9 ms |
48896 KB |
Output is correct |
| 7 |
Correct |
13 ms |
48896 KB |
Output is correct |
| 8 |
Incorrect |
6 ms |
48896 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
