Aimee

记忆化搜索非常好写,

尤其是从一个朴素的搜索开始改造。

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;
}