Maximum War Disaster

This problem is set in a world with n cities connected by exactly \(n-1\) bidirectional roads so that any two cities are reachable from one another. City 1 lies at the center; whoever seizes control of city 1 is said to conquer the world.

Initially, no city is under any country's control. Over time, however, cities rise and form countries. For convenience, when city \(i\) rises, the country originating from it is called country \(i\). In the rising process of city \(i\), country \(i\) takes control of every city on the unique path from city \(i\) to city 1. (That is, it takes control of all cities on the path \(i \rightarrow 1\).)

War breaks out if, during the rise of country \(i\), it needs to take control of a city that is already controlled by a different country \(j\) (with \(j \neq i\)). Note that if a city rises consecutively (i.e. there are two or more successive rise events for the same city), then no war occurs since the country already controls those cities.

History recorded that city \(i\) had a total of \(a_i\) rise events. The only knowable order constraint is that no other city rises until one city rises and conquers the world (i.e. until some rise event acquires city 1). In other words, the last event must be a rise (from some city) that takes over city 1. Prior to that, events can be arranged arbitrarily and even interleaved in order to maximize conflicts. In each rise event, the disaster degree is defined as the number of different countries that country \(i\) ends up having to fight (even if it fights the same country several times, that country is only counted once).

Your task is, given the initial \(a_i\) for each city, to determine, over all valid orders of rise events, what the maximum possible total disaster degree is. Moreover, there will be queries that update the \(a_i\) values. Each query adds an integer \(w\) to \(a_x\) (i.e. \(a_x := a_x+w\)). After each query, compute the maximum total disaster degree again.

Additional Clarifications:

• For any city, its multiple rise events belong to the same country. Thus, if a city’s events occur consecutively, no war is triggered.
• Even if a country loses control of cities later, when its origin city rises the next time, it again takes control of the cities on the path from that city to city 1.
• The only event that terminates the sequence is when a rise event conquers city 1. Hence, you may arrange all rise events with the guarantee that the final event is the one that seizes control of city 1.

Observation and Hints:

Consider an edge \(e\) connecting a city \(v\) (with parent \(p\)) in the tree (with the tree rooted at 1). Every rise event in the subtree of \(v\) will update the control of that edge. The first event on this edge does not cause a war because the city is uncontrolled initially. Every subsequent event will cause a war if the country taking over is different from the one that previously controlled that edge. However, if rise events from the same city occur consecutively, no war occurs. With complete freedom to choose the order (subject to the rule that no new rise begins after city 1 is conquered), one may alternate the control on every edge as much as possible.

It turns out that if for an edge \(e\), the total number of rise events from the subtree is \(S\) and the maximum number of rise events from a single city in that subtree is \(M\), then the maximum number of alternations (i.e. wars) that can be forced on that edge is

\[ f(e)=\min(S-1,\; S-M). \]

The final answer is the sum of \(f(e)\) over all edges (or, equivalently, over all cities \(v\neq1\)) in the tree.

inputFormat

The first line contains two integers \(n\) and \(q\) \( (2 \le n \le N,\; 1 \le q \le Q)\) representing the number of cities and the number of queries.

The next \(n-1\) lines each contain two integers \(u\) and \(v\) indicating there is a bidirectional road connecting cities \(u\) and \(v\).

The following line contains \(n\) integers \(a_1, a_2, \dots, a_n\) where \(a_i\) represents the number of times city \(i\) rose.

Each of the next \(q\) lines contains two integers \(x\) and \(w\) indicating that \(w\) is added to \(a_x\) (i.e. \(a_x := a_x + w\)).

outputFormat

After each query, output one line with a single integer: the maximum total disaster degree summed over all rise events under an optimal valid ordering.

sample

2 1
1 2
1 2
2 1

0

</p>