2783: [JLOI2012]树
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 588 Solved: 347
Description
数列
提交文件：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≤263。
这个是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。
题解
邻接表存图，dfs查找路径，set记录可能的路径s' 值
代码
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <typeinfo>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//************************************************************************************** set<int > s;
int t;
int n,sum;
struct ss
{
int to,next;
}e[];
int sss;
int k,ans;
int head[];
int a[];
void init()
{
t=;
memset(head,,sizeof(head));
}
void add(int u,int v)
{
e[t].to=v;
e[t].next=head[u];
head[u]=t++;
}
void dfs(int x,int sum)
{
sum+=a[x];
if(s.count(sum-sss))ans++;
s.insert(sum);
for(int i=head[x];i;i=e[i].next)
{
dfs(e[i].to,sum);
}
s.erase(sum);
}
int hash[];
int main()
{
scanf("%d%d",&n,&sss);
init();
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
int x,y;
for(int i=;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
hash[y]=;
}
for(int i=;i<=n;i++)
if(!hash[i]){k=i;break;}
s.clear();
s.insert();
ans=;
sum=;
dfs(k,); cout<<ans<<endl;
return ;
}