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

Problem - 14D - Codeforces

題意：
給一棵樹，求兩個不相交的路徑，長度乘積最長可以是多少。

資料規模：
節點數： 2 ≤ N ≤ 200
時間限制：1000 ms
空間限制：64 MB

解法：
因為樹原本是連通的，而不能相交其實就是有一條路徑可以把他們連起來卻不准連起來，所以考慮一一枚舉橋，並禁掉該橋。這時候會有兩個連通分量，分別求最長路徑，更新答案即可。

時間 / 空間複雜度：
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;
}