Codeforces #566 Div2 D. Complete Mirror

候補に気付くまでが大変。
https://codeforces.com/contest/1182/problem/D

問題

木を成す無向グラフが与えられる。
以下の条件を満たす根となる頂点があればそれを1つ答えよ。

• 根からの距離が等しい頂点は、次数が皆等しい。

解法

根を決めたとき、条件を満たすか考えよう。
これは各頂点において、各子頂点のSubTreeの形状が同じであれば良く、これはSubTreeのハッシュ値を求めれば容易に確認できる。

あとは根の候補を探そう。
まず一つ考えられるのは、次数２以上の点が根となりうるのは、テストケースにもある木の中心である。
（中心じゃないと、子頂点毎の深さが異なるので条件を成しえない）。
これは容易に求められる。

それ以外の場合、どこかの次数１の点である。
この場合も、先の中心を求めた結果が役に立つ。
中心を求め、そこを根とした場合に各子頂点のSubTreeのうち、ハッシュ値が異なるものが1つだけあればそのSubTreeの葉が候補となる。
その時、中心から対象の葉まで分岐があってはならない。
仮に分岐がある場合、葉同士の距離の間に直径より短い組があることになるので、そもそも条件を満たさない。

int N;
vector<vector<int>> E;

set<int> D[101010];

void dfs(int cur,int pre,int d) {
	D[d].insert(E[cur].size());
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,d+1);
}

int isok(int v) {
	int i;
	FOR(i,101010) D[i].clear();
	dfs(v,v,0);
	
	FOR(i,101010) if(D[i].size()>1) break;
	if(i==101010) {
		cout<<v+1<<endl;
		exit(0);
	}
	
}


pair<int,int> farthest(vector<vector<int>>& E, int cur,int pre,int d,vector<int>& D) {
	D[cur]=d;
	pair<int,int> r={d,cur};
	FORR(e,E[cur]) if(e!=pre) r=max(r, farthest(E,e,cur,d+1,D));
	return r;
}

pair<int,vector<int>> diameter(vector<vector<int>>& E) { // diameter,center
	vector<int> D[2];
	D[0].resize(E.size());
	D[1].resize(E.size());
	auto v1=farthest(E,0,0,0,D[0]);
	auto v2=farthest(E,v1.second,v1.second,0,D[0]);
	farthest(E,v2.second,v2.second,0,D[1]);
	pair<int,vector<int>> R;
	R.first = v2.first;
	//重心を取る場合
	for(int i=E.size()-1;i>=0;i--) if(D[0][i]+D[1][i]==R.first && abs(D[0][i]-D[1][i])<=1) R.second.push_back(i);

	return R;
}

ll tree_normalize(vector<ll> T) {
	static ll momo[2]={1000000007,1000000009};
	static vector<ll> prim = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79};
	
	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;
}

vector<ll> dfs2(int cur,int pre) {
	vector<ll> R={0,cur,0};
	vector<ll> V={1};
	FORR(e,E[cur]) if(e!=pre) {
		auto v=dfs2(e,cur);
		R[0]+=v[0];
		R[1]=v[1];
		V.push_back(v[2]);
	}
	if(V.size()==1) {
		R[0]=1;
		R[2]=1;
	}
	else {
		R[2]=tree_normalize(V);
	}
	return R;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	E.resize(N);
	FOR(i,N-1) {
		cin>>x>>y;
		x--;
		y--;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	
	auto C=diameter(E);
	FORR(c,C.second) {
		isok(c);
		
		vector<vector<ll>> cand;
		FORR(e,E[c]) cand.push_back(dfs2(e,c));
		map<ll,int> V;
		FORR(cc,cand) {
			V[cc[2]]++;
		}
		if(V.size()>=3) continue;
		FORR(cc,cand) if(V[cc[2]]==1 && cc[0]==1) isok(cc[1]);
	}
	
	cout<<-1<<endl;
		
}

まとめ

これEより難しかったっぽいな。