843 . 貨運區域劃分

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

33.3% (2/6)

Tags

apcsc apcsc-exam3

Description

粄條市是一個道路錯綜複雜的城市，因此運送各種東西都是一個難題。粄條市由 N 個區域以及 N−1 條雙向道路組成，每一條道路都連接兩個區域，並且任兩個區域都由若干條道路直接或間接相連。

最近粄條市新開了 M 家貨運公司，其中的第 i 家貨運公司設置在第 ri 個區域裡，為了避免不同家貨運公司整天打架，每一家貨運公司都設置在不同區域，而且他們喜歡把公司設在偏遠的地方，所以每一家公司設置的區域，都只有連接一條道路而已。

既然是新開的公司，那他們當然要先劃出各自的勢力範圍，具體來說，每個區域都會是恰好一家公司的勢力範圍，而一家公司的勢力範圍可能包含一個或多個區域，而這家公司只會送他的勢力範圍裡的貨物，而不會侵犯到其他公司的勢力範圍。

理所當然地，一家公司設置的地點自然會屬於自己的勢力範圍，而且為了防止塞車，對於兩個屬於同一家公司的勢力範圍的區域，必須要能夠在只經過這家公司的勢力範圍的情況下，來往這兩個區域。

第 i 個區域住了 pi 個人，勢力範圍裡住的人越多，公司就越賺錢。為了防止貧富差距擴大，粄條市的市長王ㄅ希望所有公司的勢力範圍裡，人口數都不超過 K 人，請你告訴他有沒有可能。

Input Format

第一行有兩個整數 N,M,K，表示區域的數量、貨運公司的數量與同一家公司勢力範圍裡的人口上限。

第二行有 M 個整數 r1,r2,…,rM，表示每一家貨運公司所在的區域。

第三行有 N 個整數 p1,p2,…,pN，表示每個區域裡住的人數。

接下來有 N−1 行，其中第 i 行包含兩個整數 ui,vi，表示第 i 條道路連接的兩個區域編號。

  • 3≤N≤3×105
  • 1≤M≤N
  • 1≤K≤1015
  • 1≤ri≤N
  • ∀i≠j, ri≠rj
  • 1≤pi≤109
  • 1≤ui,vi≤N
  • 對於所有 i，第 ri 個區域連接恰一條道路
  • 任兩個區域之間可以透過道路互相來往

Output Format

如果王ㄅ的想法有可能達成，輸出 Yes，否則輸出 No。

Sample Input 1

5 2 3
1 5
1 1 1 1 1
1 2
2 3
3 4
4 5

Sample Output 1

Yes

Sample Input 2

6 3 17
5 4 1
7 2 4 8 8 9
1 3
2 4
6 2
3 6
5 6

Sample Output 2

Yes

Sample Input 3

10 3 35
10 6 8
8 6 1 6 6 6 4 7 9 4
1 7
2 3
1 5
2 1
10 5
1 9
3 6
7 8
4 9

Sample Output 3

Yes

Sample Input 4

5 1 4999999999
2
1000000000 1000000000 1000000000 1000000000 1000000000
1 4
1 3
3 2
3 5

Sample Output 4

No

Sample Input 5

3 2 3
1 2
4 2 1
3 1
3 2

Sample Output 5

No

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~4 範例測資 0
2 5~43 除了第 1 個區域以外，所有區域連接最多兩條道路、第 1 個區域不會有公司設置、N≤1000 20
3 5~68 除了第 1 個區域以外，所有區域連接最多兩條道路、第 1 個區域不會有公司設置 30
4 0~119 無額外限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 4
1 2000 524288 65536 1 4
2 2000 524288 65536 1 4
3 2000 524288 65536 1 4
4 2000 524288 65536 1 4
5 2000 524288 65536 2 3 4
6 2000 524288 65536 2 3 4
7 2000 524288 65536 2 3 4
8 2000 524288 65536 2 3 4
9 2000 524288 65536 2 3 4
10 2000 524288 65536 2 3 4
11 2000 524288 65536 2 3 4
12 2000 524288 65536 2 3 4
13 2000 524288 65536 2 3 4
14 2000 524288 65536 2 3 4
15 2000 524288 65536 2 3 4
16 2000 524288 65536 2 3 4
17 2000 524288 65536 2 3 4
18 2000 524288 65536 2 3 4
19 2000 524288 65536 2 3 4
20 2000 524288 65536 2 3 4
21 2000 524288 65536 2 3 4
22 2000 524288 65536 2 3 4
23 2000 524288 65536 2 3 4
24 2000 524288 65536 2 3 4
25 2000 524288 65536 2 3 4
26 2000 524288 65536 2 3 4
27 2000 524288 65536 2 3 4
28 2000 524288 65536 2 3 4
29 2000 524288 65536 2 3 4
30 2000 524288 65536 2 3 4
31 2000 524288 65536 2 3 4
32 2000 524288 65536 2 3 4
33 2000 524288 65536 2 3 4
34 2000 524288 65536 2 3 4
35 2000 524288 65536 2 3 4
36 2000 524288 65536 2 3 4
37 2000 524288 65536 2 3 4
38 2000 524288 65536 2 3 4
39 2000 524288 65536 2 3 4
40 2000 524288 65536 2 3 4
41 2000 524288 65536 2 3 4
42 2000 524288 65536 2 3 4
43 2000 524288 65536 2 3 4
44 2000 524288 65536 3 4
45 2000 524288 65536 3 4
46 2000 524288 65536 3 4
47 2000 524288 65536 3 4
48 2000 524288 65536 3 4
49 2000 524288 65536 3 4
50 2000 524288 65536 3 4
51 2000 524288 65536 3 4
52 2000 524288 65536 3 4
53 2000 524288 65536 3 4
54 2000 524288 65536 3 4
55 2000 524288 65536 3 4
56 2000 524288 65536 3 4
57 2000 524288 65536 3 4
58 2000 524288 65536 3 4
59 2000 524288 65536 3 4
60 2000 524288 65536 3 4
61 2000 524288 65536 3 4
62 2000 524288 65536 3 4
63 2000 524288 65536 3 4
64 2000 524288 65536 3 4
65 2000 524288 65536 3 4
66 2000 524288 65536 3 4
67 2000 524288 65536 3 4
68 2000 524288 65536 3 4
69 2000 524288 65536 4
70 2000 524288 65536 4
71 2000 524288 65536 4
72 2000 524288 65536 4
73 2000 524288 65536 4
74 2000 524288 65536 4
75 2000 524288 65536 4
76 2000 524288 65536 4
77 2000 524288 65536 4
78 2000 524288 65536 4
79 2000 524288 65536 4
80 2000 524288 65536 4
81 2000 524288 65536 4
82 2000 524288 65536 4
83 2000 524288 65536 4
84 2000 524288 65536 4
85 2000 524288 65536 4
86 2000 524288 65536 4
87 2000 524288 65536 4
88 2000 524288 65536 4
89 2000 524288 65536 4
90 2000 524288 65536 4
91 2000 524288 65536 4
92 2000 524288 65536 4
93 2000 524288 65536 4
94 2000 524288 65536 4
95 2000 524288 65536 4
96 2000 524288 65536 4
97 2000 524288 65536 4
98 2000 524288 65536 4
99 2000 524288 65536 4
100 2000 524288 65536 4
101 2000 524288 65536 4
102 2000 524288 65536 4
103 2000 524288 65536 4
104 2000 524288 65536 4
105 2000 524288 65536 4
106 2000 524288 65536 4
107 2000 524288 65536 4
108 2000 524288 65536 4
109 2000 524288 65536 4
110 2000 524288 65536 4
111 2000 524288 65536 4
112 2000 524288 65536 4
113 2000 524288 65536 4
114 2000 524288 65536 4
115 2000 524288 65536 4
116 2000 524288 65536 4
117 2000 524288 65536 4
118 2000 524288 65536 4
119 2000 524288 65536 4
Submit
Back to Top