Description

There are $n$ cities in this world, connected by exactly $n - 1$ bidirectional roads, so any two cities are mutually reachable. City $1$ lies at the center of the world; whoever takes this city dominates the world.

Initially, none of the $n$ cities is controlled by any country. As society develops, some cities will rise to form countries and seize world hegemony. For convenience, we label the country that rises at city $i$ as country $i$. During the rise at city $i$, country $i$ will take control of all cities on the path from city $i$ to city $1$.

The rise of a new city often means war and death. If, during the rise of country $i$, it needs to take a city that is currently controlled by another country $j$ ($j \ne i$), then country $i$ must declare war on country $j$ and fight.

Now, Kelian knows that in history, city $i$ rose exactly $a_i$ times. However, the relative order of these events is unknown. The only information is that while one city is rising to dominate the world, no new city will start rising.

War is catastrophic for the people. Kelian defines the disaster degree of a single rise as the number of distinct countries it goes to war with during that rise (multiple wars against the same country within one rise count only once). She wants to know, among all possible rise orders, what is the maximum possible sum of the disaster degrees.

Meanwhile, thanks to archaeologists’ efforts, more and more historical records are being unearthed. Based on these new materials, Kelian will adjust the values of $a_i$. Specifically, she will perform operations on $a_i$, each time adding $w$ to $a_x$. She hopes that after each modification, the maximum total disaster degree can be computed.

However, Kelian is not interested in complicated calculations, so she wants you to help her compute these values.

Additional notes:

• Multiple rises at the same city form the same country. This means that if the same city rises twice in a row, it will not go to war with any country, because those cities are already under its control.
• Over the course of history, country $i$ may temporarily control no city. This does not mean country $i$ is destroyed. When city $i$ rises, country $i$ will still take control of all cities on the path from $1$ to $i$.

Input Format

The first line contains two integers $n$, $m$, the number of cities and the number of operations.

The second line contains $n$ integers, the initial values of $a_i$.

The next $n - 1$ lines each contain two integers $u_i$, $v_i$ ($1 \le u_i, v_i \le n$) describing a road.

The next $m$ lines each contain two integers $x_i$, $w_i$, meaning add $w_i$ to $a_{x_i}$.

Output Format

Output $m + 1$ lines. The first line is the answer for the initial $a_i$. Each of the next $m$ lines is the answer after that modification.

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

6 
7 
9
10

Hint

Before the modifications, if the cities rise in the order $4, 1, 5, 3, 2$, then they will go to war with $0, 1, 2, 1, 2$ countries, respectively.

A total of $6$ pairs of hostile relationships will be produced. It can be proven that this is the maximum among all rise orders.

Translated by ChatGPT 5