[JLOI2012]树

Time Limit: 1 Sec Memory Limit: 128 MB

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。

倍增感觉应该是可以过的。。。只是这道题的时限有点迷。。。。

但是这里有个其他方法。。。

就是你一共只dfs一次，然后每次dfs到一个点的时候算一下以这个点结尾的答案。

所以你要手写一个类似队列的东西，一个头指针一个尾指针。

然后让队列里的东西和是最靠近 s 的。

这个维护要注意一下细节就好了。

复杂度应该很快。。。只是我不会算而已QAQ

#include
    
     using namespace std;const int maxn = 1e5 + 5;int ans, op = 1, ed, all, n, s, data[maxn];int ini[maxn];vector
     
       point[maxn];inline void read(int &x){    x = 0; static char c = getchar();    while(!isdigit(c)) c = getchar();    while(isdigit(c)){x = x * 10 + c - '0'; c = getchar();}}void dfs(int t, int step){    ini[step] = data[t]; ed = step; int lin = op, la = all;    all += data[t];     while(all > s && op < ed){all -= ini[op]; op++;}    while(op > 1 && all + ini[op] < s){op--; all += ini[op];}    if(all == s) ans++;    for(int i = point[t].size() - 1; i >= 0; --i)        dfs(point[t][i], step + 1);    all -= ini[step]; ed = step - 1; op = lin; all = la;}int main(){//  freopen("lpl.in", "r", stdin);    read(n); read(s);    for(int i = 1; i <= n; ++i) read(data[i]);    for(int a, b, i = 1; i < n; ++i){        read(a); read(b);        point[a].push_back(b);    }    dfs(1, 1);    cout << ans;    return 0;}