P16957 [SCCPC 2026] 那一年的秘密基地

那个夏天，大家在小镇的树荫下约定：一定要找到最适合的秘密基地。 小镇中有 $n$ 个地点，由 $n-1$ 条小路连接，任意两个地点之间都存在唯一一条简单路径。因此，这些地点和小路构成了一棵无根树，地点编号为 $1$ 到 $n$。 每天，大家会按照一个顺序依次来到小镇中的所有地点。这个顺序用一个长度为 $n$ 的排列 $a_1,a_2,\ldots,a_n$ 表示，其中 $a_i$ 表示第 $i$ 个被访问的地点。 如果选择地点 $r$ 作为秘密基地，就可以把整棵树以 $r$ 为根。此时，对于两个不同地点 $x,y$，如果 $x$ 位于从 $r$ 到 $y$ 的简单路径上，则称 $x$ 是 $y$ 的祖先。 大家认为，如果某个地点先被访问，而它的某个祖先后被访问，就会产生一次``暴露风险''。形式化地，对于一个秘密基地 $r$，定义危险度 $f_r(a)$ 为满足以下条件的二元组 $(i,j)$ 的数量：$1\le i

第一行包含两个整数 $n,q$ ($1\le n,q\le 2\cdot 10^5$)，分别表示地点数量和操作次数。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ($1\le a_i\le n$)，表示初始访问顺序。保证 $a_1,a_2,\ldots,a_n$ 是一个排列。 接下来 $n-1$ 行，每行包含两个整数 $u_i,v_i$ ($1\le u_i,v_i\le n$)，表示地点 $u_i$ 和地点 $v_i$ 之间有一条小路。保证给出的 $n-1$ 条小路构成一棵树。 接下来 $q$ 行，每行包含一个整数 $x_i$ ($1\le x_i

输出 $q+1$ 行。 第一行输出初始访问顺序对应的最小危险度。 之后第 $i$ 行输出第 $i-1$ 次操作后的最小危险度。