Peter's Snazzy Sock Shopping Spree

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type

Prom is coming up soon, and Peter doesn't own any good socks!

Requiring the snazziest socks for this occasion, he plans on riding the Snazzy Sock Shopping Bus for Q days. The Bus has a set of N stores it can visit, each with a snazziness value s_i. There is guaranteed to be exactly one path between every pair of stores. In order to keep styles fresh, the Bus will change which store, a, it starts at, and which store, b, it ends at every day.

Being an impulsive sock-lover, Peter will buy socks at every store he visits, adding s_i to his total snazziness sum for the day's trip. Wanting to stay hip and cool, he ropes you in to decide when to start/stop riding the bus for the maximum snazziness sum. Having limited time, he will only ride for one continuous series of stores. He will also always visit at least one store per day, as he can't go to prom without socks!

Input Specification

The first line contains 2 integers N, Q\ (1 \le N, Q \le 2 \times 10^5).

The next line contains N integers s_i\ (-10^9 \le s_i \le 10^9), the snazziness value of store i.

The next N - 1 lines contain 2 integers u, v\ (1 \le u, v \le N), indicating there is a street between u and v.

The next Q lines contain 2 integers a, b\ (1 \le a, b \le N).

Output Specification

For each day, print the maximum snazziness value Peter can achieve on a new line.

Subtasks

Subtask 1 [30%]

N \le 1000

Q \le 1000

Subtask 2 [70%]

No further constraints.

Sample Input

9 10
-7 10 0 3 5 0 6 -9 1
1 6
4 3
7 9
5 9
6 2
9 2
3 6
8 9
1 3
3 4
6 6
3 8
9 6
7 4
6 2
3 5
7 9
1 4

Sample Output

0
3
0
11
11
20
10
16
7
3

Comments

There are no comments at the moment.