Problem Description

That summer, everyone made a promise under the shade of the trees in the town: they must find the most suitable secret base.

There are $n$ locations in the town, connected by $n-1$ paths. Between any two locations, there is a unique simple path. Therefore, these locations and paths form an unrooted tree, with locations numbered from $1$ to $n$.

Every day, everyone visits all locations in the town one by one following an order. This order is represented by a permutation $a_1,a_2,\ldots,a_n$ of length $n$, where $a_i$ is the $i$-th visited location.

If we choose location $r$ as the secret base, we can root the whole tree at $r$. Then, for two different locations $x,y$, if $x$ lies on the simple path from $r$ to $y$, we say $x$ is an ancestor of $y$.

Everyone believes that if a location is visited earlier, but one of its ancestors is visited later, then an “exposure risk” occurs. Formally, for a secret base $r$, define the danger level $f_r(a)$ as the number of pairs $(i,j)$ satisfying: $1\le i<j\le n$, and when rooted at $r$, $a_j$ is an ancestor of $a_i$.

In other words, $f_r(a)$ is the number of pairs of locations such that, in the current visiting order, the later location is an ancestor of the earlier location.

However, as time goes by, plans may change. Next, there are $q$ operations. Each operation gives an integer $x$, meaning we swap the two adjacent locations $a_x$ and $a_{x+1}$ in the visiting order.

Before all operations, and after each operation, you need to choose the most suitable secret base again to make the danger level as small as possible, and output this minimum danger level.

Input Format

The first line contains two integers $n,q$ ($1\le n,q\le 2\cdot 10^5$), representing the number of locations and the number of operations.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le n$), representing the initial visiting order. It is guaranteed that $a_1,a_2,\ldots,a_n$ is a permutation.

The next $n-1$ lines each contain two integers $u_i,v_i$ ($1\le u_i,v_i\le n$), indicating there is a path between location $u_i$ and location $v_i$. It is guaranteed that these $n-1$ paths form a tree.

The next $q$ lines each contain one integer $x_i$ ($1\le x_i<n$), indicating an operation where $a_{x_i}$ and $a_{x_i+1}$ need to be swapped.

Output Format

Output $q+1$ lines.

The first line outputs the minimum danger level for the initial visiting order.

Then, the $i$-th line outputs the minimum danger level after the $(i-1)$-th operation.

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

3
3
4
4

Hint

Translated by ChatGPT 5