Codeforces #316 Div2 D. Tree Requests

またcoutでやらかした…。
http://codeforces.com/contest/570/problem/D

問題

N頂点の根付き木が与えられる。
各頂点には１文字のアルファベットが与えられる。

この木に対し、M個のクエリに答えよ。
各クエリの入力は頂点V[i]と深さH[i]からなる。
各クエリに対し、深さH[i]の頂点群のうち頂点V[i]のサブツリーとなるものを集めたとき、それらの頂点が持つ文字を並べて回文を作れるかどうか判定せよ。

解法

まずDFSで木をEuler Tourしよう。

その際、各頂点の深さ毎に到達順のvectorを作り、a-zの各アルファベットの登場回数を記録する。
さらにそのvectorの累積和を求めておく。
こうすると、「深さH[i]の頂点群のうち頂点V[i]のサブツリーとなるもの」に含まれる各文字の登場回数がO(logN*σ)(σは文字種数)で求められる。
回文を作れる条件は、奇数回登場する文字種が１個以下であることなので、それを判定すればよい。

さらにここで２つの高速化を行う。
まず、回文を作れる条件は、奇数回登場する文字種が１個以下であることなので、各文字の登場回数を厳密に数える必要はなく、偶奇だけ覚えればよい。
よって26個分のアルファベットの登場回数の偶奇を1個のint値にまとめこむことができる。
また、一度vectorの累積和を取って後から各文字の登場回数をカウントするのではなく、クエリを先読みして頂点V[i]の探索前後で深さH[i]の頂点における各文字の登場回数を数えることで、vectorを作る必要がなくなる。

こちらもMが大きいので、coutを避けた方が良い。

int N,M;
vector<int> E[505050];
string S;
int sumx[505050];

vector<int> Q[505050];
int V[505050],H[505050],ret[505050];

void dfs(int cur,int dep) {
	
	FORR(r,Q[cur]) ret[r] ^= sumx[H[r]];
	sumx[dep] ^= (1<<(S[cur]-'a'));
	FORR(r,E[cur]) dfs(r,dep+1);
	FORR(r,Q[cur]) ret[r] ^= sumx[H[r]];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N-1) cin>>x, E[x-1].push_back(i+1);
	cin>>S;
	
	FOR(i,M) {
		cin>>V[i]>>H[i];
		V[i]--;
		Q[V[i]].push_back(i);
	}
	
	dfs(0,1);
	
	FOR(i,M) {
		if(__builtin_popcount(ret[i])>1) _P("No\n");
		else _P("Yes\n");
	}
}

まとめ

CFでは10^5より出力が多いときはcoutは避けること。なぜまたやらかしてしまったのか。