Marathon Race :
Difficulty Level : Medium
Submissions : 227
Asked In :
Marks :30
: 3 | : 0
$$$N$$$ cities are there connected using $$$(n-1)$$$ bidirectional roads. Each city has a score given by $$$A[i]$$$.
Two Marathons were to be organized. But the path of the marathon to contain cities with only an even score or an odd score. You have to tell the max number of cities in the marathon path if the cities were with an even score or with an odd score.
Here path refers to simple path.
The first line contains $$$n$$$, the number of cities. The second line contains an array of $$$n$$$ integers denoting the score of cities from 1 to $$$n$$$. The next $$$n-1$$$ lines contain two integers each, which are connected by an edge.$$$(1 \le n \le 10^5)$$$$$$(1 \le A[i] \le 10^5).$$$
The output contains a single line containing two integers $$$x$$$ and $$$y$$$ where $$$x$$$ = max number of cities in the marathon path if the cities were with an even score, $$$y$$$ = max number of cities in the marathon path if the cities were with an odd score respectively.
5 4 3 2 3 5 1 2 1 3 2 4 2 5
2 3
1 9429
0 1
3 1035 28296 99007 1 3 1 2
1 2
