408205: GYM103053 D Max and Mex

hezlik has a tree with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$, and each vertex has a value $$$a_i$$$. All $$$a_i$$$'s are distinct.

There are two non-negative integers $$$c$$$ and $$$d$$$. For a simple path $$$P$$$, let $$$V$$$ be the set of all the vertices on the path $$$P$$$. We define the beauty of path P as: $$$$$$ c \cdot \mathop{\operatorname{mex}}\limits_{x\in V } \{ a_x \} + d \cdot \max\limits_{x\in V} \{ a_x \} $$$$$$ hezlik wants to know the maximum beauty among all simple paths. Can you help him?

Note: $$$\operatorname{mex} V$$$ is the smallest non-negative integer that does not belong to $$$V$$$, $$$\max V$$$ is the maximum integer that does belong to $$$V$$$.

A simple path is a sequence of distinct vertices $$$x_1, x_2, \dots , x_k$$$ where $$$k \ge 1$$$ such that there is an edge $$$(x_i, x_{i+1})$$$ for all integers $$$i$$$ where $$$1 \le i \le k-1$$$.

The first line consists of three space-separated integers $$$n,c,d$$$ ($$$2\le n\le 10^5$$$, $$$0\le c,d\le 10^9$$$).

The second line consists of $$$n$$$ space-separated integers $$$a_1,a_2,\cdots,a_{n}$$$ ($$$0\le a_i\le n-1$$$).

Each of the next $$$n-1$$$ lines contains two space-separated integers $$$u$$$ and $$$v$$$ ($$$1\le u,v\le n$$$), denoting there is an edge between $$$u$$$ and $$$v$$$.

Output a single integer, the maximum beauty among all simple paths.

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

18

20 1 1
10 18 13 8 19 15 0 14 11 17 12 5 4 9
16 2 1 6 7 3
17 9
6 17
20 17
4 17
18 9
15 17
2 18
13 2
3 20
12 15
10 18
5 3
11 20
7 13
16 12
1 12
8 15
19 11
14 7

21

Sample $$$1$$$: For the simple path $$$P=\{ 3,1,2,5 \}$$$, $$$\mathop{\operatorname{mex}}\limits_{x\in V } \{ a_x \}=\operatorname{mex}\{ 0,1,2,4 \}=3,\max\limits_{x\in V} \{ a_x \}=\max\{ 0,1,2,4 \}=4$$$, so the beauty of the simple path $$$P$$$ is $$$2\times 3+3\times 4=18$$$.