做这个网站多少钱,江西锐安建设工程有限公司网站,医疗器械有哪些产品,微信公众号粉丝下单Description
小J是一只猴子#xff0c;住在树上#xff0c;树上每个点都有一些果子
小J每天要固定吃掉S个果子
小J还要多在树上运动一下#xff0c;于是他想知道这个树上有多少路径#xff0c;路径上点的果子的总和正好为S
并且路径上的点的深度是连续增加的
Format
…Description
小J是一只猴子住在树上树上每个点都有一些果子
小J每天要固定吃掉S个果子
小J还要多在树上运动一下于是他想知道这个树上有多少路径路径上点的果子的总和正好为S
并且路径上的点的深度是连续增加的
Format
Input
第一行给出NS
接下来N个数字代表每个点上的果子数
接下来N-1行每行两个数字a,b代表a是b的父亲点
N100000
每个点的果子数及S均不超过int
Output
如题
Samples
输入数据 1
4 7
1 2 4 5
1 2
2 3
2 4Copy
输出数据 1
2 代码
#includebits/stdc.h
using namespace std;
int a[10000001],num,ans,n,x,y;
vectorintvec[10000001];
mapint,intmp;
void dfs(int k,int ss)
{ss a[k];mp[ss];if(mp.count(ss - num)) ans mp[ss - num];for(int i 0;i vec[k].size();i) dfs(vec[k][i],ss);mp[ss]--;if(mp[ss] 0) mp.erase(ss);return ;
}
signed main()
{cinnnum;for(int i 1;i n;i) cina[i];for(int i 1;i n;i){cinxy;vec[x].push_back(y);}mp[0] 1;dfs(1,0);coutansendl;return 0;
}
