首页 > 代码库 > [luoguP3252] [JLOI2012]树（DP）
[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 {13 int x = 0, f = 1;14 char ch = getchar();15 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;16 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;17 return x * f;18 }19 20 inline void add(int x, int y)21 {22 to[cnt] = y;23 next[cnt] = head[x];24 head[x] = cnt++;25 }26 27 inline void dfs(int u)28 {29 sum[u] = sum[f[u]] + a[u];30 S.insert(sum[u]);31 if(S.count(sum[u] - s)) ans++;32 for(int i = head[u]; i ^ -1; i = next[i]) dfs(to[i]); 33 S.erase(sum[u]);34 }35 36 int main()37 {38 int i, x, y;39 n = read();40 s = read();41 memset(head, -1, sizeof(head));42 for(i = 1; i <= n; i++) a[i] = read();43 for(i = 1; i < n; i++)44 {45 x = read();46 y = read();47 f[y] = x;48 add(x, y);49 }50 S.insert(0);51 dfs(1);52 printf("%d\n", ans);53 return 0;54 }
[luoguP3252] [JLOI2012]树（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。