TopCoder SRM 695 Div2 Hard BearUniqueDiameter

これは自力で解けた。
https://community.topcoder.com/stat?c=problem_statement&pm=14367

問題

木を成す無向グラフが与えられる。
ここから１つの連結した部分グラフを取ることを考える。
この部分グラフの直径を成す頂点対が１つになるようなグラフは何通りあるか。

解法

まず１点しかない部分グラフは常に条件を満たす。
以後２点以上ある場合を考える。
D(u,v)を頂点u,v間の最短距離とする。

グラフの直径を成す２点(u,v)を総当たりしよう。
u',v'を以下のように定める。

• D(u,v)が偶数の場合、u'もv'もu,vの中点。
• D(u,v)が奇数の場合、D(u,u')=D(v,v')=(D(u,v)-1)/2となる点。すなわちu-vをつないだ頂点群のうち中央の2点

u',v'からDFSで各頂点xを探索し、条件を満たす頂点の残し方を列挙しよう。

• xがu-vの最短経路上にあるなら必ず残す。
• xを残すと直径がD(u,v)以上になりうる、すなわちmax(D(x,u'),D(x,v'))≧(D(u,v)-1)/2ならば、xは消す一択。
• それ以外の場合、xは消しても残しても良い。消す場合が1通り、残す場合は(u'やv'から見て遠い方の)各頂点の組み合わせの掛算の分だけ組み合わせがある。

vector<int> E[301];
int num[301][301];
int mat[301][301];
ll mo=1000000007;

class BearUniqueDiameter {
	public:
	int N;
	
	ll dfs(int cur,int pre,int left,int u,int v) {
		if(left<0) return 1;
		ll ret=1;
		
		int canerase = (mat[cur][u]+mat[cur][v]>mat[u][v]);
		FORR(e,E[cur]) if(e!=pre) (ret *= dfs(e,cur,left-1,u,v))%=mo;
		return ret+canerase;
	}
	
	int countSubtrees(vector <int> a, vector <int> b) {
		int x,y,z,i;
		N=a.size()+1;
		FOR(x,N) FOR(y,N) mat[x][y]=(x!=y)*999;
		FOR(i,N-1) mat[a[i]][b[i]]=mat[b[i]][a[i]]=1;
		FOR(z,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][z]+mat[z][y]);
		FOR(i,N) E[i].clear();
		FOR(i,N-1) E[a[i]].push_back(b[i]),E[b[i]].push_back(a[i]);
		
		ll ret=N;
		FOR(y,N) FOR(x,y) {
			int d=mat[x][y];
			int u=-2,v=-2,i;
			FOR(i,N) {
				if(d%2==0 && mat[x][i]==mat[y][i] && mat[x][i]==d/2) u=i,v=-1;
				if(d%2==1 && mat[x][i]==d/2 && mat[y][i]==d/2+1) u=i;
				if(d%2==1 && mat[x][i]==d/2+1 && mat[y][i]==d/2) v=i;
			}
			if(v==-1) ret += dfs(u,-1,d/2-1,x,y);
			else ret += dfs(u,v,d/2-1,x,y)*dfs(v,u,d/2-1,x,y)%mo;
		}
		
		return ret%mo;
		
	}
}

まとめ

ちょっと悩んだけど、コードはそんなに複雑ではないね。