kmjp's blog

競技プログラミング参加記です

TopCoder SRM 703 Div2 Hard TreeDiameters

ここ3か月で2回しかSRM出てない…。
https://community.topcoder.com/stat?c=problem_statement&pm=14462

問題

木を成す無向グラフSにおけるA(S)とは、Sの直径とおなじ距離を持つ2点の対の数を意味する。
ここで木を成す無向グラフTが与えられる。Tの部分グラフT'のうち、A(T')の最大値を求めよ。

解法

まず直径が偶数の部分グラフを作る場合を考える。
グラフの中心点vを定め、そこから距離dにある頂点数を数え上げたとき、中心点から見てC個の各子頂点のsubtreeの方向にN[0],N[1],N[2],...,N[C-1]個ずつあったとする。
その時、vを中心として距離dまでの頂点からなる部分グラフT'を考えると、 \displaystyle A(T') = \sum_{0\le i \lt j \lt C} (N_i * N_j)となる。
よって、vを総当たりし、そこから各距離までの頂点数を各子頂点のSubtreeに対してDFSで数え上げれば、A(T')の最大値を求めることができる。

次に直径が奇数の場合を考える。
これは中心点vの代わりに2頂点u-vを結ぶ中心辺(?)を考え、同様にそこから距離dの頂点数を数え上げていけば同様にA(T')を列挙できる。

class TreeDiameters {
	public:
	int N;
	vector<int> E[1010];
	int ma,md;
	int num[1010];
	int sum[1010];
	int count[1010];
	
	void dfs(int cur,int pre,int d) {
		md=max(md,d);
		count[d]++;
		FORR(r,E[cur]) if(r!=pre) dfs(r,cur,d+1);
	}
	
	int getMax(vector <int> p) {
		int N=p.size()+1;
		int i,j;
		FOR(i,N) E[i].clear();
		FOR(i,p.size()) E[i+1].push_back(p[i]),E[p[i]].push_back(i+1);
		
		ma=0;
		FOR(i,N) {
			ZERO(num);
			ZERO(sum);
			FORR(r,E[i]) {
				md=0;
				dfs(r,i,1);
				for(j=0;j<=md;j++) {
					sum[j] += num[j]*count[j];
					ma=max(ma,sum[j]);
					num[j] += count[j];
					count[j]=0;
				}
			}
		}
		FOR(i,N) FORR(r,E[i]) if(r>i) {
			ZERO(num);
			ZERO(sum);
			md=0;
			dfs(i,r,0);
			for(j=0;j<=md;j++) num[j]=count[j], count[j]=0;
			md=0;
			dfs(r,i,0);
			for(j=0;j<=md;j++) ma=max(ma,num[j]*count[j]),count[j]=0;
		}
		return ma;
	}
}

まとめ

直径が奇数の場合は、中心を点でなく辺でとるというテクは覚えておいたほうがいいね。