P15822 [JOI Open 2013] 同步系统 / Synchronization

JOI 有限公司在全球共有 $N$ 台服务器。每台服务器都存有一份重要的信息，且不同服务器存有的信息内容各不相同。JOI 有限公司目前正在服务器之间铺设数字线路，以便信息能够在服务器之间共享。当两台服务器之间铺设好线路后，它们便可以互相交换信息。信息可以从一台服务器传递到另一台服务器，只要通过已铺设好的线路能够到达对方。 每台服务器都配备了一个高性能的同步系统。当两台服务器能够互相交换信息，且它们存有的信息不同时，它们会自动同步信息。在服务器 A 和服务器 B 进行一次同步后，服务器 A 和服务器 B 都会拥有同步前它们之中至少一方所持有的全部信息。 为了降低成本，只能铺设 $N - 1$ 条线路。当这 $N - 1$ 条线路铺设完毕后，任意两台服务器之间将存在唯一一条不重复经过同一台服务器的路径来交换信息。 初始时（时刻 0），没有任何线路。有时，线路需要在恶劣条件下铺设（例如在沙漠中、在海底）。某些线路会在某个时刻变得不可用。一旦线路变得不可用，在它被重新铺设之前将无法使用。 已知在时刻 $j$（$1 \le j \le M$），恰好有一条线路的状态会发生改变。 我们需要知道在时刻 $M + 1$ 时，某些服务器上存有的不同信息的总数。 ### 任务 编写一个程序，根据给定的待铺设线路信息和线路状态变化情况，确定指定服务器上存有的不同信息的总数。

从标准输入读取以下数据。 - 输入的第一行包含三个以空格分隔的整数 $N, M, Q$。这表示服务器数量为 $N$，给出了一个包含 $M$ 次线路状态变化的列表，并且我们需要知道 $Q$ 台服务器上存有的不同信息的总数。 - 接下来的 $N - 1$ 行中，第 $i$ 行（$1 \le i \le N - 1$）包含两个以空格分隔的整数 $X_i, Y_i$。这表示线路 $i$ 在被铺设时，将连接服务器 $X_i$ 和服务器 $Y_i$。 - 接下来的 $M$ 行中，第 $j$ 行（$1 \le j \le M$）包含一个整数 $D_j$。这表示在时刻 $j$，线路 $D_j$ 的状态发生了改变。具体来说，如果在时刻 $j$ 之前线路 $D_j$ 是不可用的，那么在时刻 $j$ 这条线路就会被铺设好（变为可用）。如果在时刻 $j$ 之前线路 $D_j$ 是可用的，那么在时刻 $j$ 这条线路就会变得不可用。当状态在时刻 $j$ 发生改变时，所有相关的同步过程都将在时刻 $j + 1$ 之前完成。 - 接下来的 $Q$ 行中，第 $k$ 行（$1 \le k \le Q$）包含一个整数 $C_k$。这表示我们需要知道最终时刻服务器 $C_k$ 上存有的不同信息的总数。

输出到标准输出，共 $Q$ 行。第 $k$ 行（$1 \le k \le Q$）应输出一个整数，表示最终时刻服务器 $C_k$ 上存有的不同信息的总数。

### 样例解释 1 初始时，我们假设服务器 $i$（$1 \le i \le 5$）存有信息片段 $i$。 - 在时刻 1，线路 1 被铺设，服务器 1 和 2 连通。随后，服务器 1 和 2 都存有信息片段 1 和 2。 - 在时刻 2，线路 2 被铺设，服务器 1 和 3 连通。结合已有的线路 1，服务器 1、2、3 相互连通。服务器 1、2、3 都存有信息片段 1、2 和 3。 - 在时刻 3，由于在此之前线路 1 是可用状态，现在它变得不可用。 - 在时刻 4，线路 4 被铺设，服务器 2 和 5 连通。服务器 2 和 5 都存有信息片段 1、2、3 和 5。注意，此时因为线路 1 已不可用，服务器 1 和 2 之间无法交换信息。 - 在时刻 5，线路 4 变得不可用。 - 在时刻 6，线路 3 被铺设，服务器 2 和 4 连通。随后，服务器 2 和 4 都存有信息片段 1、2、3、4 和 5。 如上所述，最终时刻，服务器 1、4、5 上分别存有 3、5、4 种不同的信息片段。 ### 约束条件 所有输入数据满足以下条件。 - $2 \le N \le 100\,000$。 - $1 \le M \le 200\,000$。 - $1 \le Q \le N$。 - $1 \le X_i \le N$，$1 \le Y_i \le N$，$X_i \ne Y_i$（$1 \le i \le N - 1$）。 - $1 \le D_j \le N - 1$（$1 \le j \le M$）。 - $1 \le C_k \le N$（$1 \le k \le Q$）。 - $C_k$ 的值互不相同。 - 如果所有线路都被铺设，则任意两台服务器之间都存在一条可达路径。 ### 子任务 #### 子任务 1 [30 分] - 满足 $Q = 1$。 #### 子任务 2 [30 分] - 满足 $X_i = i$，$Y_i = i + 1$（$1 \le i \le N - 1$）。 #### 子任务 3 [40 分] - 无额外约束。 翻译由 DeepSeek V3.2 完成