Bamboo Communication Network

In ancient times the villagers communicated by sending small objects through a bamboo‐pipe water channel – a clever technique that minimized the elevation‐difference cost. In our abstraction, a settlement network is represented by a rooted tree T = (V, E) with n nodes. Each node v is assigned a unique integer label p(v) taken from the set {1,2,…,n}. For an edge (u,v) the cost (or weight) is defined as

\(w(u,v)=|p(u)-p(v)|\).

The total cost on the tree is W(T)=\(\sum_{e\in E}w(e)\).

However, there is an extra twist: The labeling must be done in such a way that if one defines an auxiliary graph G(T)=(V,E') by adding an edge between two nodes u and v if and only if the unique path between them in T has labels that are either monotonic increasing or monotonic decreasing (that is, the sequence \(p_1,p_2,\dots,p_\ell\) along the path is either strictly increasing or strictly decreasing), then the diameter of G(T) does not exceed 2. In other words, for any two nodes, either the labels along their unique connecting path in T are monotonic, or there exists a third node which can serve as an intermediate so that each of the two pairs has a monotonic labeled path.

It turns out that a necessary (and sufficient) condition is that there exists a center c such that for every other node v the labels on the unique path from c to v are monotonic (either increasing or decreasing) – but different children of any node may choose different directions. Moreover, if we assign the label differences on each edge as small as possible then the base cost on an edge is 1; however, when a node has multiple children whose paths must avoid clashing (since the label values must be distinct) extra gaps are needed.

Here is one way to view the optimization. Suppose the tree (settlement network) has n nodes. For any node v with degree deg(v) in the undirected tree, if v is not chosen as the center then it will have deg(v)-1 children in the tree rooted at the chosen center; if v is the center then it has deg(v) children. For each such node the base cost contributed by its incident edges is exactly the number of edges and would be n-1 overall if we could assign every edge a cost of 1. However, when a node has multiple children in the same "direction", we must assign them distinct gaps to keep the labels strictly monotonic. In a free group (i.e. at the center where both increasing and decreasing assignment can start from 1) an optimal assignment for a group of k edges is to assign the gaps 1,2,…,k so that the extra penalty (above the base cost of k) is

\(R(k)=\frac{k(k+1)}{2}-k=\frac{k(k-1)}{2}\).

On the other hand, for a non‐center node the group corresponding to the side that contains the parent must avoid using the parent's label, so if that group has size k the optimal extra cost is

\(Q(k)=\frac{(k+1)(k+2)}{2}-1-k=\frac{k(k+1)}{2}\).

By choosing the partition of the children of a node into an increasing group and a decreasing group optimally, one may show that the extra penalty at a node v depends only on \(x = deg(v)-1\) (when v is not the center) or \(x = deg(v)\) (when v is the center). In fact, one may prove that for every node the minimum extra penalty is given by a function f(x) defined for nonnegative integers x (with the convention that for a leaf \(x=0\)) by:

\(f(x)=\min_{a+b=x}\Bigl\{\frac{a(a+1)}{2}+\frac{b(b-1)}{2}\Bigr\}\),

where the optimum is achieved by partitioning \(x\) as evenly as possible. It turns out that one may show that f(x)=0 for \(x\le1\), \(f(2)=1\), \(f(3)=2\), \(f(4)=4\), \(f(5)=6\), \(f(6)=9\), etc. Then the minimum total cost (over all valid labelings) is given by

\(M(T)= (n-1)+\sum_{v\in V} f(\bigl(\,deg(v)-1\bigr))\).

Now, your task is as follows.

• Given an initial tree T with n nodes and n-1 edges, compute M(T) as defined above.
• Then, there will be several operations. In each operation a new leaf is attached to an existing node x (i.e. add a new vertex v with an edge (x, v)). After each operation, update the tree and output the new value of M(T).

Input and Output details: See below.

inputFormat

The first line contains two integers n and q (n is the number of nodes in the initial tree, q is the number of operations).

Then follow n-1 lines, each containing two integers u and v representing an edge in the initial tree.

Then follow q lines, each containing a single integer x (1-indexed) indicating that a new leaf is attached to node x. The new vertex will be assigned the next available index.

It is guaranteed that the given edges form a tree.

outputFormat

Output q+1 lines. The first line is the value of M(T) for the initial tree. Then for each operation, output the updated value of M(T) on a new line.

sample

3 2
1 2
2 3
2
1

2
4
5

</p>