Codeforces #321 Div2 C. Kefa and Park

CF321は不参加でした。
http://codeforces.com/contest/580/problem/C

問題

N頂点の根付き木が与えられる。
幾つかの頂点には猫がいる。

根から葉に対して最短距離で移動するとき、M頂点を超えて連続で猫に遭遇する、ということがなく移動可能な葉の数を求めよ。

解法

BFSなりDFSで、ここまで何匹連続猫に遭遇したかを伝搬させて計算していくだけ。
(M+1)匹連続遭遇したらそのサブツリーの処理は打ち切る。
(M+1)匹連続遭遇しないで葉に到達したら、その分答えにカウントする。

int N,M;
int C[101010];
vector<int> E[101010];

int dfs(int cur,int pre,int con) {
	if(C[cur]) con++;
	else con=0;
	if(con>M) return 0;

	int isleaf=1;
	int ret=0;
	FORR(r,E[cur]) if(r!=pre) isleaf=0, ret +=dfs(r,cur,con);
	return ret+isleaf;

}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N>>M;
	FOR(i,N) cin>>C[i+1];
	
	FOR(i,N-1) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	cout<<dfs(1,0,0)<<endl;
}

まとめ

一見ややこしそうだけど実は単純な問題。
実際正答者Bと同程度だしねぇ。