[文章目录]
Description
在这个问题中，给定一个值S和一棵树。在树的每个节点有一个正整数，问有多少条路径的节点总和达到S。路径中节点的深度必须是升序的。假设节点1是根节点，根的深度是0，它的儿子节点的深度为1。路径不必一定从根节点开始。对于100%数据，N≤100000，所有权值以及S都不超过1000。
一开始看错题了，以为没有固定的根节点。看懂之后就好想多了，1A也是爽了。
就是找树上不弯曲的链上的点权和为s的方案数。考虑前缀和思想，吧每个节点到根节点路径上所有的节点的点权和为当前节点的前缀和，那么所求就是每个节点的前缀和与该节点子树中任意节点的前缀和相减为s的个数。所以我们在dfs过程中用set记录根到当前节点的所有前缀和，累加ans。然后当返回时清除当前的前缀和。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#define N 101000
using namespace std;
int n,sum,w[N],ans,root;
bool v[N];
int head[N],to[N<<1],nxt[N<<1],cnt;
void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
multiset<int>s;
multiset<int>::iterator it;
void dfs(int x,int pre,int data)
{
s.insert(data);
int tmp=data+w[x];
ans+=s.count(tmp-sum);
for(int i=head[x];i;i=nxt[i])
dfs(to[i],x,tmp);
s.erase(data);
}
int main()
{
scanf("%d%d",&n,&sum);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int x,y,i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);v[y]=1;
}
for(int i=1;i<=n;i++) if(!v[i]) root=i;
dfs(root,0,0);
printf("%d",ans);
return 0;
}