# CFR 14 D. Two Paths ( Ad hoc, Tree, DP )

Problem - 14D - Codeforces

O( N ^ 2 ) / O( N )

```int N;
vp edge;
vvi G;

void init(){
cin >> N;
G = vvi( N );
for( int i = 0; i < N - 1; ++i ){
int u, v; cin >> u >> v;
edge.emplace_back( u - 1, v - 1 );
G[ u - 1 ].emplace_back( v - 1 );
G[ v - 1 ].emplace_back( u - 1 );
}
}

int get_max_path_length( int u, vi &vis, int ban1, int ban2, int &ans ){
int max1 = 0, max2 = 0;
for( int v : G[ u ] ){
if( vis[ v ] ) continue;
if( ban1 == u and ban2 == v ) continue;
if( ban1 == v and ban2 == u ) continue;
vis[ v ] = 1;
int vres = get_max_path_length( v, vis, ban1, ban2, ans );
++vres;
if( vres > max1 ){
max2 = max1;
max1 = vres;
} else if( vres > max2 ){
max2 = vres;
}
}
upmax( ans, max1 + max2 );
return max1;
}

void preprocess(){
int ans = 0;
for( int i = 0; i < N - 1; ++i ){
int ban1, ban2; tie( ban1, ban2 ) = edge[ i ];
vi vis( N );
int max1 = 0;
vis[ 0 ] = 1;
get_max_path_length( 0, vis, ban1, ban2, max1 );
int max2 = 0;
for( int j = 0; j < N; ++j ){
if( not vis[ j ] ){
vis[ j ] = 1;
get_max_path_length( j, vis, ban1, ban2, max2 );
break;
}
}
upmax( ans, max1 * max2 );
}
cout << ans << endl;
}
```