[luoguP3252] [JLOI2012]树（DP）

传送门

树上前缀和。

在树上找一条权值和为 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

上一篇：[luoguP1005] 矩阵取数游戏（DP + 高精度）

下一篇：[luoguP2983] [USACO10FEB]购买巧克力Chocolate Buying（贪心）

---

DP