[JLOI 2012]树

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

HINT

对于100%数据，N≤100000，所有权值以及S都不超过1000。

题解

遍历一遍，将根到当前节点路径上的所有的点的树上前缀和压入栈中。

查找时二分栈即可。

 //It is made by Awson on 2017.9.29

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <cstdio>

 #include <string>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define sqr(x) ((x)*(x))

 #define lowbit(x) ((x)&(-(x)))

 using namespace std;

 const int N = ;

 void read(int &x) {

     char ch; bool flag = ;

     for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());

     for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());

     x *= -*flag;

 }

 int n, s, u, v;

 int val[N+];

 int sum[N+], top;

 struct tt {

     int to, next;

 }edge[N+];

 int path[N+], tot;

 int ans;

 void add(int u, int v) {

     edge[++tot].to = v;

     edge[tot].next = path[u];

     path[u] = tot;

 }

 bool erge(int l, int r) {

     while (l <= r) {

         int mid = (l+r)>>;

         if (sum[top]-sum[mid] == s) return true;

         if (sum[top]-sum[mid] > s) l = mid+;

         else r = mid-;

     }

     return false;

 }

 void dfs(int u) {

     sum[++top] = sum[top-]+val[u];

     ans += erge(, top);

     for (int i = path[u]; i; i = edge[i].next)

         dfs(edge[i].to);

     top--;

 }

 void work() {

     read(n), read(s);

     for (int i = ; i <= n; i++) read(val[i]);

     for (int i = ; i < n; i++)

         read(u), read(v), add(u, v);

     dfs();

     printf("%d\n", ans);

 }

 int main() {

     work();

     return ;

 }

巴特西