Description

小C得到了一棵树，这棵树每个点都有一个权值且1为根节点。无聊的小C又随机了一个权值s，现在他想知道这棵树上有多少条路径的节点权值总和恰好为s，且满足该路径中节点的深度必须是升序的。

Input

第一行是两个正整数n,s，接下来一行n个正整数，表示每个节点的权值。
接下来n-1行，每行包含两个正整数，表示树上的一条边。

Output

输出一个数，表示满足条件的路径数。

Hint

对于30%的数据，n<=1000.
对于100%的数据，n<=100000,s,节点权值<=1000.

Source

BY BPM

Solution

将任意叶节点到根的路径分离，那么就是求序列中是否存在连续的一段和为s。倍增、扫描都可以

~~事实就是此题暴力可过~~

Code

#include <stdio.h>
#include <math.h>
#include <queue>
#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)
#define drp(i, st, ed) for (int i = st; i >= ed; i -= 1)
#define erg(i, st) for (int i = ls[st]; i; i = e[i].next)
#define N 100001
#define E N * 2 + 1
struct edge{int x, y, next;}e[E];
int dep[N], ls[N], v[N];
int edgeCnt = 0;
inline void addEdge(int x, int y){
    e[++ edgeCnt] = (edge){x, y, ls[x]}; ls[x] = edgeCnt;
    e[++ edgeCnt] = (edge){y, x, ls[y]}; ls[y] = edgeCnt;
}
inline int read(){
int x = 0; char ch = getchar();
while (ch < '0' || ch > '9'){ch = getchar();}
while (ch <= '9' && ch >= '0'){x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();}
return x;
}
std:: queue<int> que;
inline void bfs(int st){
while (!que.empty()){que.pop();}
    que.push(st);
    dep[st] = 1;
while (!que.empty()){
int now = que.front(); que.pop();
        erg(i, now){
if (!dep[e[i].y]){
                que.push(e[i].y);
                dep[e[i].y] = dep[now] + 1;
            }
        }
    }
}
int ans = 0;
inline void dfs2(int now, int s, int tot){
if (s == tot){
        ans += 1;
return;
    }
    erg(i, now){
if (dep[e[i].y] > dep[now] && tot + v[e[i].y] <= s){
            dfs2(e[i].y, s, tot + v[e[i].y]);
        }
    }
}
int main(void){
int n = read(), s = read();
    rep(i, 1, n){v[i] = read();}
    rep(i, 2, n){
int x = read(), y = read();
        addEdge(x, y);
    }
    bfs(1);
    rep(i, 1, n){
        dfs2(i, s, v[i]);
    }
printf("%d\n", ans);
return 0;
}

秒客网

2017年8月9日提高组T3 难题