The Valley Overflows

Time limit1sMemory limit512 MB

Summary

Given a tree of valleys with heights, decide whether water starting from any non-K valley can reach valley K under the splash-up movement rule.

Level: Hard8 of 10
Topics: Tree, DFS, Greedy, Implementation
Solved: No attempts yet

Problem

Deep in the mountains near Soongsil University, in a valley called Soongsilgol, lives Ukje, who sells baeksuk in the valley to get by after the gift-wrapping factory went bankrupt in the Fourth Industrial Revolution. Soongsilgol has N terraced valleys, connected in a tree shape by N-1 water channels. That is, there is always a unique path between any two valleys. The i-th valley sits at elevation Hi. Along a water channel, water from a higher valley overflows and falls to a lower valley. If two valleys at the same elevation are connected by a water channel, water flows in both directions.

Water that falls from height Ha to Hb splashes up from Hb by (Ha-Hb)/2. The water then rises to elevation Hb+(Ha-Hb)/2, and can move to any c satisfying Hc ≤ Hb+(Ha-Hb)/2. At c, the water splashes up by (the height it splashed to at b - the height of c)/2, that is, (Hb+(Ha-Hb)/2 - Hc)/2. Splashed water moves only along water channels. Water may fall from several valleys into one valley, or splash from one valley to several valleys; assume that this never changes the elevations of the valleys or causes interference between splashing streams.

(a→b means water moves from a to b, and a and b are the heights of the two valleys for convenience) For 8→2, the water splashes by (8-2)/2=3 and rises to elevation 5. The water can then move at most as far as 8→2→5. 8→2→6, 8→2→7, and so on are impossible. For 8→2→2, the water that splashed to elevation 5 via 8→2 then falls to the valley at elevation 2, splashes by (5-2)/2=1.5, and ends at elevation 3.5. In the example above, starting from 8 reaches every valley.

The kitchen aunt Hyobin wants to commute by riding the water channels like a water slide. Together with Hyobin, let us find out whether there exists a path by which water can move to valley K, where Ukje's baeksuk restaurant is!

Input

The first line gives the number of valleys N and the number of the valley K where Ukje is. (1 ≤ N ≤ 200,000, 1 ≤ K ≤ N)

The second line gives the elevations Hi of the N valleys in order. (1 ≤ Hi ≤ 1,000,000, Hi is a positive integer)

From the third line, N-1 lines give water channel information u, v. This means there is a water channel between valley u and valley v. (1 ≤ u,v ≤ N, u ≠ v)

Output

If the starting point is not K and there exists at least one path by which water can move to K under the conditions, print 1; otherwise print 0.

Examples3

Example 1
Input
```
4 4
8 2 2 3
1 2
2 3
3 4
```
Expected output
```
1
```
Example 2
Input
```
4 4
8 2 5 6
1 2
2 3
3 4
```
Expected output
```
0
```
Example 3
Input
```
6 6
8 2 1 6 1 2
1 2
2 3
3 4
3 5
5 6
```
Expected output
```
1
```