搜尋
首頁web前端html教學Codeforces Round #277 (Div. 2)D(树形DP计数类)_html/css_WEB-ITnose

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:

  1. S is non-empty.
  2. 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.
  3. .

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]


            对于每个点为根这样算一遍就好了,注意减去算重的情况,即相邻多个点的权值相等,可以用点的代号去重(即规定只能从代号大的往小的DP)


陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
HTML與CSS和JavaScript:比較Web技術HTML與CSS和JavaScript:比較Web技術Apr 23, 2025 am 12:05 AM

HTML、CSS和JavaScript是構建現代網頁的核心技術:1.HTML定義網頁結構,2.CSS負責網頁外觀,3.JavaScript提供網頁動態和交互性,它們共同作用,打造出用戶體驗良好的網站。

HTML作為標記語言:其功能和目的HTML作為標記語言:其功能和目的Apr 22, 2025 am 12:02 AM

HTML的功能是定義網頁的結構和內容,其目的在於提供一種標準化的方式來展示信息。 1)HTML通過標籤和屬性組織網頁的各個部分,如標題和段落。 2)它支持內容與表現分離,提升維護效率。 3)HTML具有可擴展性,允許自定義標籤增強SEO。

HTML,CSS和JavaScript的未來:網絡開發趨勢HTML,CSS和JavaScript的未來:網絡開發趨勢Apr 19, 2025 am 12:02 AM

HTML的未來趨勢是語義化和Web組件,CSS的未來趨勢是CSS-in-JS和CSSHoudini,JavaScript的未來趨勢是WebAssembly和Serverless。 1.HTML的語義化提高可訪問性和SEO效果,Web組件提升開發效率但需注意瀏覽器兼容性。 2.CSS-in-JS增強樣式管理靈活性但可能增大文件體積,CSSHoudini允許直接操作CSS渲染。 3.WebAssembly優化瀏覽器應用性能但學習曲線陡,Serverless簡化開發但需優化冷啟動問題。

HTML:結構,CSS:樣式,JavaScript:行為HTML:結構,CSS:樣式,JavaScript:行為Apr 18, 2025 am 12:09 AM

HTML、CSS和JavaScript在Web開發中的作用分別是:1.HTML定義網頁結構,2.CSS控製網頁樣式,3.JavaScript添加動態行為。它們共同構建了現代網站的框架、美觀和交互性。

HTML的未來:網絡設計的發展和趨勢HTML的未來:網絡設計的發展和趨勢Apr 17, 2025 am 12:12 AM

HTML的未來充滿了無限可能。 1)新功能和標準將包括更多的語義化標籤和WebComponents的普及。 2)網頁設計趨勢將繼續向響應式和無障礙設計發展。 3)性能優化將通過響應式圖片加載和延遲加載技術提升用戶體驗。

HTML與CSS vs. JavaScript:比較概述HTML與CSS vs. JavaScript:比較概述Apr 16, 2025 am 12:04 AM

HTML、CSS和JavaScript在網頁開發中的角色分別是:HTML負責內容結構,CSS負責樣式,JavaScript負責動態行為。 1.HTML通過標籤定義網頁結構和內容,確保語義化。 2.CSS通過選擇器和屬性控製網頁樣式,使其美觀易讀。 3.JavaScript通過腳本控製網頁行為,實現動態和交互功能。

HTML:是編程語言還是其他?HTML:是編程語言還是其他?Apr 15, 2025 am 12:13 AM

HTMLISNOTAPROGRAMMENGUAGE; ITISAMARKUMARKUPLAGUAGE.1)htmlStructures andFormatSwebContentusingtags.2)itworkswithcsssforstylingandjavascript for Interactivity,增強WebevebDevelopment。

HTML:建立網頁的結構HTML:建立網頁的結構Apr 14, 2025 am 12:14 AM

HTML是構建網頁結構的基石。 1.HTML定義內容結構和語義,使用、、等標籤。 2.提供語義化標記,如、、等,提升SEO效果。 3.通過標籤實現用戶交互,需注意表單驗證。 4.使用、等高級元素結合JavaScript實現動態效果。 5.常見錯誤包括標籤未閉合和屬性值未加引號,需使用驗證工具。 6.優化策略包括減少HTTP請求、壓縮HTML、使用語義化標籤等。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

Atom編輯器mac版下載

Atom編輯器mac版下載

最受歡迎的的開源編輯器

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3 英文版

SublimeText3 英文版

推薦:為Win版本,支援程式碼提示!