樹

jzoj 2753

題目大意：

給你一棵樹，每一個點都一個值，現在問你有多少條路徑可以滿足以下條件：
1、方向都是向下
2、路徑上的點的值總和為S

輸入樣例

3 3 1 2 3 1 2 1 3

輸出樣例

2

數據范圍

對于30%數據，$N?100$；
對于60%數據，$N?1000$；
對于100%數據，$N?100000$，所有權值以及S都不超過1000。

解題思路：

從根節點開始搜索，用一個值num來記錄根節點到當前點的值總和
如果以某一個點為路徑開始，拿如果下面有某一個點的num為當前點的num加S那這就是一條合法路徑

代碼：

#include<map> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; int n, s, x, y, ans, tot, b[105000], head[105000]; map< int , int >p; struct rec {int to, next; }a[105000]; void add(int x, int y) {a[++tot].to = y;a[tot].next = head[x];head[x] = tot; } void dfs(int x, int num) {int k = p[num + s];//記錄num為這個值的點有多少個p[num + b[x]]++;//多了一個for (int i = head[x]; i; i = a[i].next)dfs(a[i].to, num + b[x]);//搜索ans += p[num + s] - k;//看多了多少 } int main() {scanf("%d%d", &n, &s);for (int i = 1; i <= n; ++i)scanf("%d", &b[i]);for (int i = 1; i < n; ++i){scanf("%d%d", &x, &y);add(x, y);//連邊}dfs(1, 0);printf("%d", ans);return 0; }

總結

以上是生活随笔為你收集整理的【dfs】树（jzoj 2753）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。