数列
提交文件：sequence.pas/c/cpp
输入文件： sequence.in
输出文件： sequence.out
问题描述：
把一个正整数分成一列连续的正整数之和。这个数列必须包含至少两个正整数。你需要求出这个数列的最小长度。如果这个数列不存在则输出 -1 。
输入格式：
每行包含一个正整数 n 。
每个文件包含多行，读入直到文件结束。
输出格式：
对于每个 n ，输出一行，为这个数列的最小长度。
第一行是两个整数N和S，其中N是树的节点数。
第二行是N个正整数，第i个整数表示节点i的正整数。
接下来的N-1行每行是2个整数x和y，表示y是x的儿子。
输出格式：
输出路径节点总和为S的路径数量。
输入样例： | 输出样例： |
3 3 1 2 3 1 2 1 3 | 2 |
数据范围：
对于30%数据，N≤100；
对于60%数据，N≤1000；
对于100%数据，N≤100000，所有权值以及S都不超过1000。
数据范围：
对于所有数据，n≤2 。
这个是JLOI2012的T1，发出来仅为了试题完整
=============================================================================================
在这个问题中，给定一个值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。
题解：
这个题目看上去是不是要点分，稍微看一下数据范围,S不超过1000，而且所有点权都为正整数，这意味着我们每次枚举一个起点，dfs，层数不会超过1000层，而且因为要保证深度关系，很多节点都远远达不到。这题还是很暴力吧。
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define MAXN 101000
using namespace std;
int ans=;
int val[MAXN],b[MAXN],dep[MAXN],roof;
struct edge{
int first;
int next;
int to;
}a[MAXN*];
int n,m,num=; void addedge(int from,int to){
a[++num].to=to;
a[num].next=a[from].first;
a[from].first=num;
} void dfs(int now,int fa,int tot){
if(tot==m) ans++;
if(tot>=m) return;
for(int i=a[now].first;i;i=a[i].next){
int to=a[i].to;
if(to==fa) continue;
if(dep[to]<=dep[now]) continue;
dfs(to,now,val[to]+tot);
}
} void pre(int now,int fa){
dep[now]=dep[fa]+;
for(int i=a[now].first;i;i=a[i].next){
int to=a[i].to;if(to==fa) continue;
pre(to,now);
}
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&val[i]);
for(int i=;i<=n-;i++){
int x,y;scanf("%d%d",&x,&y);
addedge(x,y),addedge(y,x);b[y]=;
}
for(int i=;i<=n;i++) if(!b[i]) roof=i;
pre(roof,);
for(int i=;i<=n;i++) dfs(i,,val[i]);
printf("%d",ans);
return ;
}