P11241 [KTSC 2024 R2] 病毒

**请用 C++14 或 C++17 提交本题** 你需要在代码开头加入如下代码： ```cpp #include std::vector find_spread(int N, int M, std::vector A, std::vector B, std::vector P, std::vector D, std::vector C); ```

**题目译自 [2024년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사](https://www.ioikorea.kr/archives/ioitst/2024/) T4 「[바이러스](https://assets.ioikorea.kr/ioitst/2024/2/virus/virus_statement.pdf)」** 由于上次新冠疫情的严重影响，KOI 城市决定为未来可能发生的疫情做好充分准备。为此，KOI 城市希望分析当前城市结构对病毒的脆弱程度。 KOI 城市由 $N$ 个地点和 $N-1$ 条双向道路组成，任意两个不同的地点都可以通过这些道路互相到达。也就是说，城市的道路网络是一个树结构。每个地点用 $0$ 到 $N-1$ 的不同整数表示。由于城市的道路网络是树结构，对于任意两个地点 $u$ 和 $v$，从 $u$ 到 $v$ 的唯一简单路径上的边数定义为 $u$ 和 $v$ 之间的距离。 KOI 城市有 $M$ 名居民。对于每个 $j$ $(0 \leq j \leq M-1)$，第 $j$ 个人住在 $P[j]$ 号地点，并且可以到达距离 $P[j]$ 不超过 $D[j]$ 的地点。 KOI 城市的病毒学家们建立了一个模型来模拟病毒在两个人之间的传播过程。对于每个 $0 \leq v \leq N-1$，第 $v$ 号地点的传播时间用一个正整数 $C[v]$ 表示。假设第 $j$ 个人在时间 $t$ 首次感染病毒，并且第 $k$ 个人从第 $j$ 个人那里接收到病毒。如果存在一个地点 $w$，使得 $w$ 号地点与 $P[j]$ 号地点的距离不超过 $D[j]$，且 $w$ 号地点与 $P[k]$ 号地点的距离不超过 $D[k]$，那么 $w$ 号地点就是传播的媒介。 如果没有这样的传播媒介，第 $k$ 个人不会直接从第 $j$ 个人那里感染病毒（当然，他可能通过其他人间接感染）。如果存在传播媒介，那么在所有可能的传播媒介中，选择传播时间最短的地点 $x$。如果第 $k$ 个人在时间 $t+C[x]$ 之前没有感染病毒，那么他将在时间 $t+C[x]$ 被第 $j$ 个人感染。病毒以这种方式在所有不同的两个人之间传播。 在上述模型下，KOI 城市的研究人员希望计算当第 $0$ 个人在时间 $0$ 感染病毒时，其他人何时感染病毒。你需要计算对于每个 $0 \leq j \leq M-1$，第 $j$ 个人首次感染病毒的时间。如果第 $j$ 个人没有感染病毒，则记录为 $-1$。 你需要实现以下函数： ```cpp std::vector find_spread(int N, int M, std::vector A, std::vector B, std::vector P, std::vector D, std::vector C); ``` - `N`：KOI 城市的地点数量。 - `M`：KOI 城市的居民数量。 - `A, B`：长度为 $N-1$ 的数组。对于每个 $i$ $(0 \leq i \leq N-2)$，存在一条连接 $A[i]$ 和 $B[i]$ 的道路。每条道路在两个数组中只出现一次。 - `P, D`：长度为 $M$ 的数组。对于每个 $j$ $(0 \leq j \leq M-1)$，第 $j$ 个人住在 $P[j]$ 号地点，并且可以到达距离 $P[j]$ 不超过 $D[j]$ 的地点。 - `C`：长度为 $N$ 的数组。对于每个 $v$ $(0 \leq v \leq N-1)$，第 $v$ 号地点的传播时间为 $C[v]$。 - 该函数返回一个长度为 $M$ 的数组 $T$。对于每个 $j$ $(0 \leq j \leq M-1)$，如果第 $j$ 个人感染病毒，$T[j]$ 表示他首次感染病毒的时间；如果没有感染，则为 $-1$。 - 该函数在每个测试用例中只会被调用一次。

示例评测程序按以下格式读取输入： - 第 $1$ 行：$N\,M$ - 第 $2+i$ $(0 \leq i \leq N-2)$ 行：$A[i]\,B[i]$ - 第 $1+N+j$ $(0 \leq j \leq M-1)$ 行：$P[j]\,D[j]$ - 第 $1+N+M$ 行：$C[0]\,C[1]\,\ldots\,C[N-1]$

示例评测程序按以下格式输出： - 第 $1+j$ $(0 \leq j \leq M-1)$ 行：函数 `find_spread` 返回的数组的第 $j$ 个元素

对于所有输入数据，满足： - $1 \leq N \leq 10^5$ - $1 \leq M \leq 10^5$ - 对于所有 $i$ $(0 \leq i \leq N-2)$，$0 \leq A[i], B[i] \leq N-1, A[i] \neq B[i]$ - 对于所有 $j$ $(0 \leq j \leq M-1)$，$0 \leq P[j], D[j] \leq N-1$ - 对于所有 $v$ $(0 \leq v \leq N-1)$，$1 \leq C[v] \leq 10^{9}$ 详细子任务附加限制及分值如下表所示。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $5$ | $N \leq 500, M \leq 500$；
对于所有 $i$ $(0 \leq i \leq N-2)$，$A[i]=i, B[i]=i+1$ | | $2$ | $8$ | $N \leq 5000, M \leq 5000$；
对于所有 $i$ $(0 \leq i \leq N-2)$，$A[i]=i, B[i]=i+1$ | | $3$ | $27$ | 对于所有 $i$ $(0 \leq i \leq N-2)$，$A[i]=i, B[i]=i+1$ | | $4$ | $5$ | $N \leq 500, M \leq 500$ | | $5$ | $8$ | $N \leq 5000, M \leq 5000$ | | $6$ | $47$ | 无附加限制 |