CodeforcesRound#277(Div.2)D（树形DP计数类）_html/css_WEB-ITnose
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#277(Div.2)D（树形DP计数类）_html/css_WEB-ITnose，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2245字，纯文字阅读大概需要4分钟。
内容图文
D. Valid Sets
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
As you know, an undirected connected graph with n nodes and n?-?1 edges is called a tree. You are given an integer d and a tree consisting of n nodes. Each node i has a value ai associated with it.
We call a set S of tree nodes valid if following conditions are satisfied:
- S is non-empty.
- S is connected. In other words, if nodes u and v are in S, then all nodes lying on the simple path between u and v should also be presented in S.
- .
Your task is to count the number of valid sets. Since the result can be very large, you must print its remainder modulo 1000000007(109?+?7).
Input
The first line contains two space-separated integers d (0?≤?d?≤?2000) and n (1?≤?n?≤?2000).
The second line contains n space-separated positive integers a1,?a2,?...,?an(1?≤?ai?≤?2000).
Then the next n?-?1 line each contain pair of integers u and v (1?≤?u,?v?≤?n) denoting that there is an edge between u and v. It is guaranteed that these edges form a tree.
Output
Print the number of valid sets modulo 1000000007.
Sample test(s)
input
1 42 1 3 21 21 33 4
output
input
0 31 2 31 22 3
output
input
4 87 8 7 5 4 6 4 101 61 25 81 33 56 73 4
output
41
Note
In the first sample, there are exactly 8 valid sets: {1},?{2},?{3},?{4},?{1,?2},?{1,?3},?{3,?4} and {1,?3,?4}. Set {1,?2,?3,?4} is not valid, because the third condition isn't satisfied. Set {1,?4} satisfies the third condition, but conflicts with the second condition.
题意：RT
思路：树形DP，dp[u]表示以u为根，且它的所有子树的点v的权值都不超过它，且满足 w[u]-w[v]<=d 的方案数
对于每个点为根这样算一遍就好了，注意减去算重的情况，即相邻多个点的权值相等，可以用点的代号去重（即规定只能从代号大的往小的DP）
内容总结
以上是互联网集市为您收集整理的CodeforcesRound#277(Div.2)D（树形DP计数类）_html/css_WEB-ITnose全部内容，希望文章能够帮你解决CodeforcesRound#277(Div.2)D（树形DP计数类）_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。