Codeforces Round #14 D.Two Paths

Round #16との難易度差が酷いｗ

問題概要

n個の都市がn-1本の双方向に通行可能な道路により結ばれている。
これらの道路を通りどの二つの都市も行き来することができる。

交わりのない2本の道路（すなわち、二つの道路の通る都市が共通のものを持たない）の長さをa,bとするときa*bの最大値を求めよ。
n≦200である。

解法

まず、都市と道路のグラフは木であることを簡単に示す。
（グラフの木がわからない人はwikipedia等参照）

連結であることは条件にあるので、閉路（ループ）がないことを言えばよい。
道路の数はn-1本であり、任意の都市間が行き来できる。ゆえに道路k本と都市k個からなる閉路があったとすると、「その閉路に含まれない都市n-k個」と閉路の都市k個を結ぶ道路が少なくともk本必要である。
したがって道路の数はn本以上であることになり道路の本数がn-1本であることに矛盾する。■

更に、「二本の道」のどちらにも含まれないような道路が存在する。
（全ての道路がどちらかの道に属すると交わりができる）

たぶん道Aに含まれる都市から道Bに含まれる都市へ移動することを考えればよい。
どこかで道Aから道Bへ移動しなければならないが、その際に通る道路の両側の都市は異なる道が通っていることになり矛盾。■

したがって、「どちらにも含まれないような道路」でグラフを二つに分け、
それぞれの部分で最長になる道路を探せばよいことがわかる。

グラフが木であることから導かれる、任意の二点を行き来する単純パスが一意に決まる性質を用いれば、ワーシャルフロイド法などであらかじめ任意の都市間の距離を求めておけば計算量が減る。

ソースコード

O(n^3). 50msで通った。

int n;
int d[200][200];
int v[200];

void dfs(int c,int val)
{
	v[c]=val;
	rep(i,n)if(d[c][i]==1&&v[i]==0)
		dfs(i,val);
}

void run()
{
	cin>>n;
	rep(i,n)fill_n(d[i],n,inf);
	rep(i,n-1)
	{
		int a,b; cin>>a>>b; a--,b--;
		d[a][b]=d[b][a]=1;
	}
	rep(k,n)rep(i,n)rep(j,n)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	
	int ans=0;
	rep(i,n)rep(j,i)if(d[i][j]==1)
	{
		int t=d[i][j];
		
		d[i][j]=0;
		fill_n(v,n,0);
		dfs(i,1); dfs(j,-1);
		
		int m1=0,m2=0;
		rep(a,n)rep(b,a)if(v[a]==v[b])
		{
			if(v[a]>0)m1=max(m1,d[a][b]);
			else m2=max(m2,d[a][b]);
		}
		ans=max(ans,m1*m2);
		
		d[i][j]=t;
	}
	cout<<ans<<endl;
}