Description

? ? ???在這個問題中，給定一個值S和一棵樹。在樹的每個節點有一個正整數，問有多少條路徑的節點總和達到S。路徑中節點的深度必須是升序的。假設節點1是根節點，根的深度是0，它的兒子節點的深度為1。路徑不必一定從根節點開始。

Input

???????第一行是兩個整數N和S，其中N是樹的節點數。

???????第二行是N個正整數，第i個整數表示節點i的正整數。

???????接下來的N-1行每行是2個整數x和y，表示y是x的兒子。

Output

???????輸出路徑節點總和為S的路徑數量。

Sample Input

3 3
1 2 3
1 2
1 3

Sample Output

2

HINT

對于100%數據，N≤100000，所有權值以及S都不超過1000。

題解

遍歷一遍，將根到當前節點路徑上的所有的點的樹上前綴和壓入棧中。

查找時二分棧即可。

1 //It is made by Awson on 2017.9.29 2 #include <set> 3 #include <map> 4 #include <cmath> 5 #include <ctime> 6 #include <queue> 7 #include <stack> 8 #include <vector> 9 #include <cstdio> 10 #include <string> 11 #include <cstring> 12 #include <cstdlib> 13 #include <iostream> 14 #include <algorithm> 15 #define LL long long 16 #define Max(a, b) ((a) > (b) ? (a) : (b)) 17 #define Min(a, b) ((a) < (b) ? (a) : (b)) 18 #define sqr(x) ((x)*(x)) 19 #define lowbit(x) ((x)&(-(x))) 20 using namespace std; 21 const int N = 100000; 22 void read(int &x) { 23 char ch; bool flag = 0; 24 for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar()); 25 for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar()); 26 x *= 1-2*flag; 27 } 28 29 int n, s, u, v; 30 int val[N+5]; 31 int sum[N+5], top; 32 struct tt { 33 int to, next; 34 }edge[N+5]; 35 int path[N+5], tot; 36 int ans; 37 38 void add(int u, int v) { 39 edge[++tot].to = v; 40 edge[tot].next = path[u]; 41 path[u] = tot; 42 } 43 bool erge(int l, int r) { 44 while (l <= r) { 45 int mid = (l+r)>>1; 46 if (sum[top]-sum[mid] == s) return true; 47 if (sum[top]-sum[mid] > s) l = mid+1; 48 else r = mid-1; 49 } 50 return false; 51 } 52 void dfs(int u) { 53 sum[++top] = sum[top-1]+val[u]; 54 ans += erge(0, top); 55 for (int i = path[u]; i; i = edge[i].next) 56 dfs(edge[i].to); 57 top--; 58 } 59 void work() { 60 read(n), read(s); 61 for (int i = 1; i <= n; i++) read(val[i]); 62 for (int i = 1; i < n; i++) 63 read(u), read(v), add(u, v); 64 dfs(1); 65 printf("%d\n", ans); 66 } 67 int main() { 68 work(); 69 return 0; 70 }

?

轉載于:https://www.cnblogs.com/NaVi-Awson/p/7609498.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的[JLOI 2012]树的全部內容，希望文章能夠幫你解決所遇到的問題。

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