已悟:路径中如果不选某个节点,那么路径到此结束,它之后的所有节点都没有递归的权利了。```cpp
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
struct node{
int value;
vector<int> a;
}t[maxn];
int n , s , ans = 0 , Ans = 0;
void dfs(int x){
if(ans == s){
Ans++;
return;
}
for(int i = 0; i < t[x].a.size(); i++){
if(ans + t[t[x].a[i]].value <= s){
ans += t[t[x].a[i]].value;
dfs(t[x].a[i]);
ans -= t[t[x].a[i]].value;
}
}
}
int main(int argc, char const *argv[])
{
cin >> n >> s;
for(int i = 1; i <= n; i++)
cin >> t[i].value;
t[0].a.push_back(1);
for(int i = 1; i <= n - 1; i++){
int x , y;
cin >> x >> y;
t[x].a.push_back(y);
}
for(int i = 0; i <= n - 1; i++)
dfs(i);
cout << Ans;
return 0;
}
```
by qianggong @ 2024-02-22 21:42:07