Codeforces #357 Div2 D. Gifts by the List

問題文長い…。
http://codeforces.com/contest/681/problem/D

問題

ラベル付きの根付き木が与えられる。(ただし根は１つとは限らない)
各頂点iに対し、その頂点または祖先中の頂点A[i]が1つ対応付けられる。

以下の条件を満たす数列が存在するなら、一例を示せ。

• 各頂点iに対し、数列中を先頭から見ていき、iまたはその祖先にあたる最初の数値は、A[i]に一致する。

解法

親から順に1-2-3-4と頂点が並んでいるとき、A[4]=2ならばA[3]=1というようにx～A[x]中の頂点yにおいてA[y]がA[x]より親以上の頂点を差すことはできない。
この条件を判定するには、いくつかの方法がある。

• x!=A[x]ならば、xの親頂点yに対しA[x]=A[y]でなければならないのでこれをチェックする。
• 子からDFSし、xを抜けるときに現在の値を1加算、A[x]を抜けるときに1減算という処理を行う。減算が生じる頂点yがあれば、それはDFSの帰り順で解に含める。
  • ただし、1でも減算するケースでは、値が0になるまで減算しなければならない。減算しても0になりきらないケースは、上記1-2-3-4のようにA[y]がA[x]の親より上の頂点を示すケースに相当する。

以下のコードは後者。でも前者の方が頭いいな。

int N,M;
int P[101010];
vector<int> C[101010];
vector<int> R;
int A[101010];
int T[101010];

int dfs(int cur) {
	int pt=0;
	FORR(r,C[cur]) pt += dfs(r);
	if(cur==0) return 0;
	A[T[cur]]++;
	pt++;
	if(A[cur]>0) {
		if(pt!=A[cur]) {
			_P("-1\n");
			exit(0);
		}
		R.push_back(cur);
		pt=0;
	}
	return pt;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		P[y]=x;
		C[x].push_back(y);
	}
	for(i=1;i<=N;i++) if(P[i]==0) C[0].push_back(i);
	for(i=1;i<=N;i++) cin>>T[i];
	dfs(0);
	
	_P("%d\n",R.size());
	FORR(r,R) _P("%d\n",r);
	
}

まとめ

祖先の説明こんな丁寧にやる必要あったのかな。