洛谷 P3252 [JLOI2012]树

题目传送门

解题思路:

暴力深搜,统计答案.

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 
 5 using namespace std;
 6 
 7 int n,s,v[100001],ans;
 8 vector<int> a[100001];
 9 
10 inline void dfs(int id,int len) {
11     if(len > s) return ;
12     if(len == s) {
13         ans++;
14         return;
15     }
16     for(int i = 0;i < a[id].size(); i++) {
17         int u = a[id][i];
18         dfs(u,len + v[u]);
19     }
20 }
21 
22 int main() {
23     scanf("%d%d",&n,&s);
24     for(int i = 1;i <= n; i++)
25         scanf("%d",&v[i]);
26     for(int i = 1;i < n; i++) {
27         int x,y;
28         scanf("%d%d",&x,&y);
29         a[x].push_back(y);
30     }
31     for(int i = 1;i <= n; i++) 
32         dfs(i,v[i]);
33     printf("%d",ans);
34     return 0;
35 }