Codeforces #856 : Div2 E. Labeling the Tree with Distances

不参加だったけどだいぶ簡単だったらしい？
https://codeforces.com/contest/1794/problem/E

問題

N要素の木を成すグラフが与えられる。
また、N-1要素の整数列Aが与えられる。

以下を満たす頂点vを列挙せよ。

• vを根とした根付き木を考える。1点を除いた各点においてvからの距離を任意の順で並べた数列を考えると、Aと等しくできる。

解法

ハッシュを使う。
適当な正整数Bと素数Pを使い、vからの距離がdである点に対応するハッシュ値を(B^v)%Pと取ろう。
全方位木DPの要領で、各点を根とした場合のハッシュ値の総和を求めよう。
これが、元のAに対応するハッシュ値に、距離0～(N-1)のいずれかに対応するハッシュ値を追加したものと等しければ、その点は条件を満たす可能性が高い。

B,Pを複数通り行えば安全。

int N;
int C[202020];
vector<int> E[202020];

ll mo;
ll dp[202020];
int ok[202020];
map<ll,vector<int>> cand;
ll p2[202020];
int B=135;

ll dfs1(int cur,int pre) {
	dp[cur]=1;
	FORR(e,E[cur]) if(e!=pre) {
		(dp[cur]+=B*dfs1(e,cur))%=mo;
	}
	return dp[cur];
}
void dfs2(int cur,int pre,ll p) {
	(dp[cur]+=p)%=mo;
	cand[dp[cur]].push_back(cur);
	FORR(e,E[cur]) if(e!=pre) {
		ll h=(dp[cur]+mo-B*dp[e]%mo)%mo;
		dfs2(e,cur,B*h%mo);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	srand(time(NULL));
	cin>>N;
	FOR(i,N-1) {
		cin>>x;
		C[x]++;
	}
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,4) {
		ZERO(dp);
		ll moc[4]={998244353,1000000007,1000000009,1000000021};
		mo=moc[i];
		p2[0]=1;
		B=rand()%10000+1;
		FOR(j,N+1) p2[j+1]=p2[j]*B%mo;
		
		cand.clear();
		
		dfs1(0,0);
		dfs2(0,0,0);
		
		ll hash=0;
		FOR(j,N) {
			(hash+=C[j]*p2[j])%=mo;
		}
		FOR(j,N) {
			ll hash2=(hash+p2[j])%mo;
			FORR(v,cand[hash2]) ok[v]++;
		}
	}
	int num=0;
	FOR(i,N) if(ok[i]==4) num++;
	cout<<num<<endl;
	FOR(i,N) if(ok[i]==4) cout<<i+1<<" ";
	cout<<endl;
	
}

まとめ

upsolveしてる人異様に多いけど何なんだろ。