Codeforces #333 Div1 D. Acyclic Organic Compounds

これは本番チャレンジするべきだった…。
http://codeforces.com/contest/601/problem/D

問題

各頂点にアルファベット1文字が振られた根付き木が与えられる。
各頂点vについて、dif(v)は以下のように定義される。

• vから、vのsubtree内にある各頂点に到達する最短経路上の頂点のアルファベットを順に並べて単語を作ったとき、Uniqueな単語の数

また、各頂点についてパラメータC[v]が与えられる。

C[v]+dif(v)の最大値、及び最大値となる頂点の数を求めよ。

解法

実質dif(v)を高速に求める問題となる。
vから始めてvのsubtree中の各頂点に至る経路で構成される単語のうちユニークなものを数え上げるということは、vから始めるのではなく根からvを経由して同様にvのsubtree上の頂点に至る経路で構成される単語のユニークな数と等しい。

RollingHashを使い、各頂点に対して根から各頂点に至るまでの文字を連結して構成される文字列のハッシュ値を求めよう。
あとはsubtree内のユニークなハッシュ値を数え上げる問題になる。
これはいわゆる一般的なマージテクを用いて、ユニークなハッシュ値のsetを葉から根にマージしていけば良い。

const ll mo0=1000000007,mo1=1000000009;
const ll add0=1000010007, add1=1003333331;
ll mul0,mul1;

pair<ll,ll> add(pair<ll,ll> v,int c) {
	return {(v.first*mul0+c+add0)%mo0,(v.second*mul1+c+add1)%mo1};
}

int N;
int C[301010];
string S;
vector<int> E[303030];
set<pair<ll,ll> > SS[303030];
map<int,int> MP;

void dfs(int cur,int pre,pair<ll,ll> v) {
	int mal=0,ind=0,i;
	v=add(v,S[cur]);
	FOR(i,E[cur].size()) if(E[cur][i]!=pre) {
		dfs(E[cur][i],cur,v);
		if(SS[E[cur][i]].size()>mal) mal=SS[E[cur][i]].size(), ind=E[cur][i];
	}
	
	if(mal) swap(SS[cur],SS[ind]);
	FOR(i,E[cur].size()) if(E[cur][i]!=pre && E[cur][i] != ind) {
		FORR(r,SS[E[cur][i]]) SS[cur].insert(r);
	}
	SS[cur].insert(v);
	MP[SS[cur].size()+C[cur]]++;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	mul0=10009+(((ll)&mul0)>>5)%259;
	mul1=10007+(((ll)&mul1)>>5)%257;
	
	cin>>N;
	FOR(i,N) cin>>C[i];
	cin>>S;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,-1,{1,1});
	cout<<MP.rbegin()->first<<endl;
	cout<<MP.rbegin()->second<<endl;
}

まとめ

問題すら見なかったのが悔やまれる。