A maximum path

★★★★★

3.7

10 votes

Algorithms, Dynamic Programming, 2D dynamic programming, C++

Details

Problem

You are given an undirected tree $T$ with $N$ nodes rooted at node $1$ . Every node is assigned a value denoted by $A[i]$ .

You are given $Q$ queries of type:

$u \ v$ : Print the maximum value of the node present on a simple path between node $u$ and $v$ .

Input format

The first line contains two space-separated integers $N \ Q$ denoting the number of nodes and queries respectively.
Next line contains space-separated integers denoting array $A$ .
Next $N - 1$ lines contain two space-separated integers $a \ b$ denoting an edge between node $a$ and $b$ .
Next $Q$ lines contain two space-separated integers $u \ v$ denoting the query.

Output format

For each query, print the required answer in a new line.

Constraints

$1 \le N, Q \le 5 \times 10^5 \\ 1 \le A[i] \le 10^9 \\ 1 \le a, b \le N \\ 1 \le u,v \le N$

Subtasks

For $40\%$ score: $1 \le N, Q \le 10^3$

Time Limit: 3

Memory Limit: 256

Source Limit:

Explanation

For Query 1:

Simple path between node $1$ and $4$ is $1-4$ . Maximum value of node present on simple path is $5$ which is value of node $1$ .

For Query 2:

Simple path between node $2$ and $5$ is $2-3-5$ . Maximum value of node present on simple path is $6$ which is value of node $5$ .