记忆化搜索非常好写,
尤其是从一个朴素的搜索开始改造。
sum是要记录的,但是没必要存在状态里
直接统计一下当前节点是第几步之后的方案数
虽然说时间复杂度没有朴素的优美
但是不会MLE啊
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
int n,s;
int Aimee[100001];
int x,y;
int head[100001];
int dp[101][100001];
struct b{
int to;
int ne;
}b[100001];
int p;
int ans;
void add(int f,int to){
p++;
b[p].ne=head[f];
b[p].to=to;
head[f]=p;
return ;
}
int dfs(int now,int de,int sum){
if(dp[de][now]) return dp[de][now];
sum+=Aimee[now];
if(sum>s)
return 0;
if(sum==s)
return dp[de][now]=1;
int res=0;
for(int i=head[now];i;i=b[i].ne){
res+=dfs(b[i].to,de+1,sum);
}
return dp[de][now]=res;
}
signed main(){
scanf("%lld%lld",&n,&s);
for(int i=1;i<=n;++i){
scanf("%d",&Aimee[i]);
}
for(int i=1;i<n;++i){
scanf("%lld%lld",&x,&y);
add(x,y);
}
for(int i=1;i<=n;++i){
ans+=dfs(i,0,0);
}
cout<<ans;
return 0;
}