P16371 [IATI 2026] Infection
题目背景
$\huge{\text{滥用本题评测资源将封号。}}$
题目描述
Athena 现在已经长大，并且早已成为 Slopia 国的 VIP（非常重要的派对常客）。由于 Slopia 拥有非常高效的设计师，这个国家由 $N$ 个城市以及连接它们的 $N-1$ 条双向道路 $(U_j, V_j)$ 组成，使得任意两个城市之间都可以仅通过道路互相到达。
然而，上个月 Slopia 政$ $府发现有一种高度传染性的感染正在蔓延，现在非常担心 VIP 们的健康。为此，政$ $府追踪到了所有 $M$ 个派对常客的精确行程：每个常客 $i$ 的开始派对日（从宇宙诞生起计）$D_i$，他们将要出发的城市 $S_i$，以及他们最终要到达的城市 $T_i$。
由于最时尚的派对方式是在不同的城市度过每一夜，每个派对常客 $i$ 将在第 $D_i$ 天的傍晚抵达 Slopia 的城市 $S_i$ 并在那里参加当晚的派对，随后他们将继续旅行，每天沿一条道路移动，沿着前往 $T_i$ 的最短路径行进，并且每晚在他们当时所在的城市参加一场派对。在 $T_i$ 参加完派对后，他们将于第二天早上乘飞机离开 Slopia，从而结束他们的派对之旅。
此外，Slopia 政$ $府还获知了每个派对常客在其派对之旅开始时是否已经携带该感染，记为 $I_i$。由于派对是一种社交性极强的活动，如果某个感染者在某城市的某场派对上在场，那么同一天晚上在同一城市参加派对的其他所有人都会被感染。由于该感染尚无治愈方法，每位感染者在他们余下的派对之旅中将一直保持感染状态。
Slopia 政$ $府希望计算出每位派对常客在自己的派对之旅中，将在感染状态下度过多少个夜晚。你需要通过实现一个高效的解决方案来帮助他们。
### 实现细节
你必须实现函数 $\verb|solve|$：
```cpp
std::vector solve(
std::vector R,
std::vector D,
std::vector S,
std::vector T,
std::vector I
);
```
- $R$：包含 $N-1$ 个整数对的向量 —— 第 $j$ 条道路连接的两个城市 $U_j$ 和 $V_j$；
- $D$：包含 $M$ 个整数的向量 —— 派对常客 $i$ 的开始日；
- $S$：包含 $M$ 个整数的向量 —— 派对常客 $i$ 的起始城市；
- $T$：包含 $M$ 个整数的向量 —— 派对常客 $i$ 的目的城市；
- $I$：包含 $M$ 个布尔值的向量 —— 派对常客 $i$ 的初始感染状态，用布尔值表示，其中 $1$ 表示已感染，$0$ 表示未感染。
该函数在每个测试点中只会被调用一次，并且必须返回一个包含 $M$ 个整数的向量，表示每位派对常客 $i$ 将在感染状态下度过的夜晚数。
输入格式
输入格式：
- $N \ M$
- $U_{0} \ V_{0}$
- $U_{1} \ V_{1}$
- $\cdots$
- $U_{N-2} \ V_{N-2}$
- $D_0 \ S_0 \ T_0 \ I_0$
- $\cdots$
- $D_{M-1} \ S_{M-1} \ T_{M-1} \ I_{M-1}$
输出格式
输出格式：
- $Ans_0$
- $Ans_1$
- $\cdots$
- $Ans_{M-1}$
说明/提示
### Slopia 的基础设施
:::align{center}
:::
所有 VIP 的派对路线见下表，其中每个人处于感染状态的日期以 **粗体** 标出。
| -- | **0** | **1** | **2** | **3** | **4** |
| :---: | :---: | :---: | :---: | :---: | :---: |
| 0 | -- | -- | -- | -- | -- |
| 1 | **0** | -- | -- | -- | -- |
| 2 | **1** | -- | -- | -- | -- |
| 3 | **2** | 5 | -- | -- | -- |
| 4 | **3** | 4 | 5 | -- | -- |
| 5 | **4** | 3 | **4** | -- | -- |
| 6 | **5** | 6 | **3** | -- | -- |
| 7 | -- | 7 | **6** | -- | -- |
| 8 | -- | -- | **7** | **7** | -- |
| 9 | -- | -- | -- | **6** | -- |
| 10 | -- | -- | -- | **8** | 0 |
| 11 | -- | -- | -- | -- | 1 |
### 数据范围
- $1 \leq N, M \leq 150000$
- $0 \leq D_i \leq 10^{12}$
- $0 \leq U_j, V_j, S_i, T_i < N$
- $I_i \in \{0, 1\}$
### 子任务
| **子任务** | **分数** | **子任务依赖** | **$N, M$** | **其他限制** |
| :---: | :---: | :---: | :---: | :---: |
| $0$ | $0$ | $--$ | $--$ | 样例测试。 |
| $1$ | $5$ | $--$ | $\leq 100$ | $D_i = 0$ |
| $2$ | $6$ | $1$ | $\leq 5000$ | $D_i = 0$ |
| $3$ | $7$ | $0 - 2$ | $\leq 5000$ | $--$ |
| $4$ | $5$ | $--$ | $\leq 150000$ | $D_i = 10^6 \times i$ |
| $5$ | $20$ | $--$ | $\leq 150000$ | $(U_j, V_j) = (j, j + 1)$
$D_i = 0$ | | $6$ | $19$ | $5$ | $\leq 150000$ | $(U_j, V_j) = (j, j + 1)$ | | $7$ | $18$ | $0 - 3$ | $\leq 100000$ | $--$ | | $8$ | $20$ | $0 - 7$ | $\leq 150000$ | $--$ | 一个子任务的分数仅当该子任务及其所依赖子任务的全部测试数据均成功通过时才能获得。 翻译由 DeepSeek V4 Pro 完成
$D_i = 0$ | | $6$ | $19$ | $5$ | $\leq 150000$ | $(U_j, V_j) = (j, j + 1)$ | | $7$ | $18$ | $0 - 3$ | $\leq 100000$ | $--$ | | $8$ | $20$ | $0 - 7$ | $\leq 150000$ | $--$ | 一个子任务的分数仅当该子任务及其所依赖子任务的全部测试数据均成功通过时才能获得。 翻译由 DeepSeek V4 Pro 完成