传送门
树上前缀和。
在树上找一条权值和为 s 的链，其中这个链上的点按深度递增（递减）（不同）
dfs
每搜到一个点求它的前缀和 sum[x]，放入 set 中。
在 set 中找 sum[x] s 的点，如果有，ans++
退出 dfs 的时候再把 sum[x] 从 set 中删除
因为每个点权都是正整数，所以 set 中没有重复元素。
同时也是单调递增，所以简单些不用 set，开个数组再 lower_bound 也行。
——代码
1 #include <set> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 6 const int MAXN = 100001; 7 int n, s, cnt, ans; 8 int a[MAXN], head[MAXN], to[MAXN << 1], next[MAXN << 1], f[MAXN], sum[MAXN]; 9 std::set <int> S; 10 11 inline int read() 12 19 20 inline void add(int x, int y) 21 26 27 inline void dfs(int u) 28 35 36 int main() 37 50 S.insert(0); 51 dfs(1); 52 printf("%d\n", ans); 53 return 0; 54 }View Code
上一篇：[luoguP2915] [USACO08NOV]奶牛混合起来Mixed Up Cows（DP）
下一篇：[luoguP2031] 脑力达人之分割字串（DP）
DP
