「BZOJ2783」[JLOI2012] 树

2014年9月3日4,3830

Description

第一行是两个整数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。

=============================================================================================

在这个问题中,给定一个值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。记录元素前缀和。

比如搜到x,在set里面查询有没有s[x]-k,有的话ans++,然后继续往下dfs时插入s[x]

最开始要插入0

 

avatar
  Subscribe  
提醒