P16957 [SCCPC 2026] The Secret Base of That Year

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

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

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.

Translated by ChatGPT 5