已经调了三天了……

题目描述

小明决定去餐厅来庆祝他的第一份高薪工作。

他住在一个特殊的公园里，公园可以看作是一棵有根树，由n个顶点组成，根结点编号为1。小明的家就在1结点中。公园里面也有很多猫，他知道哪些结点里面有猫。

公园的每个叶子结点中都有一家餐厅，小明想选择一个餐厅去庆祝，但他非常害怕猫，如果他从家出发到某家餐厅有超过m个连续的结点中有猫，他是不可能去这家餐厅的。

你的任务是帮助小明计算出他能够去的餐厅的数量。

思路：dfs（WA爆零）

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
#include<stdio.h>  
using namespace std;
int n,m,x,y,s,ans;
struct tree{
	vector<int> son;
	bool cat;
	int father;
}Tree[100005];
void dfs(int k){
	if(Tree[k].cat)
		s++;
	else
		s=0;
	if(s>m)
		return;
	if(!Tree[k].son.size()){
		ans++;
		return;
	}
	for(int i=0;i<Tree[k].son.size();i++){
		int t=s;
		dfs(Tree[k].son[i]);
		s=t;
	}
	return;
}
int main(){
	freopen("restaurant.in","r",stdin);
	freopen("restaurant.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>Tree[i].cat;
	for(int i=1;i<n;i++){
		cin>>x>>y; 
		if(x>y)
			swap(x,y);
		Tree[y].father=x;
		Tree[x].son.push_back(y);
	}
	dfs(1);
	cout<<ans<<endl;
	return 0;
} 

$2\leq n \leq 2\times 10^5$