HourRank16 : D. Jenny's Subtrees

計算量の見積もりがえらく適当だが通ってしまった。一応O(|V|^2)のはず…。
https://www.hackerrank.com/contests/hourrank-16/challenges/jenny-subtrees

問題

木を成すN頂点の無向グラフSが与えられる。

S'(x)を各頂点xから距離R以内の頂点で構成されるSの部分グラフとする。
各S'(x)のうち、同型グラフは複数あっても1つとカウントする場合、S'(x)は何通り考えられるか。

解法

各xについて距離R内の頂点を列挙すればO(N^2)でS'(x)を列挙できる。
あとは同型判定である。

自分は根付き木の同型判定用ハッシュ関数を持っていたので、大雑把にS'(x)内の各頂点を根とする場合のハッシュを求め、そのハッシュ値の配列をソートしたものをもって木のハッシュ値とし、同型判定をした。
メモ化再帰をしても微妙にTLEしたので、S'(x)=S'(y)となる場合S'(y)の同型判定は省略したところTLEを回避できた。

int N,R;
vector<int> E[5050];

bitset<5000> now;
unordered_set<bitset<5000>> SS;
set<vector<ll>> S;

int ctim;
int tim[3030][3030];
ll memo[3030][3030];


void dfs(int cur,int pre,int l) {
	now[cur]=1;
	if(l) FORR(r,E[cur]) if(r!=pre) dfs(r,cur,l-1);
}

ll tree_normalize(vector<ll> T) {
	ll momo[2]={1000000007,1000000009};
	vector<ll> prim = {100291,100297,100313,100333,100343,100357,100361,100363,100379,100391};
	
	sort(ALL(T));
	int id=0,id2=1;
	ll a=1,b=1;
	FORR(r,T) {
		ll h=r>>32, l=r-(h<<32);
		(a+=h*prim[(id++)%prim.size()])%=momo[0];
		(b+=l*prim[(id2++)%prim.size()])%=momo[1];
	}
	return (a<<32)+b;
}

ll dfs2(int cur,int pre) {
	
	if(tim[cur][pre]==ctim) return memo[cur][pre];
	
	vector<ll> V;
	V.push_back((1LL)+(1LL<<32));
	
	FORR(r,E[cur]) if(r!=pre && now[r]) V.push_back(dfs2(r,cur));
	
	memo[cur][pre]=tree_normalize(V);
	tim[cur][pre]=ctim;
	return memo[cur][pre];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>R;
	
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	MINUS(tim);
	
	FOR(i,N) {
		FOR(j,N) now[j]=0;
		ctim=i;
		dfs(i,-1,R);
		
		if(SS.count(now)) continue;
		SS.insert(now);
		
		vector<ll> V;
		FOR(j,N) if(now[j]) V.push_back(dfs2(j,3002));
		sort(ALL(V));
		S.insert(V);
		
	}
	
	cout<<S.size()<<endl;
}

まとめ

ペナルティが気にならないからって無理やりすぎる解き方な気はする。
本当はちゃんと計算量見積もるなり最大ケース試すなりするほうがいいのだけども。