P14531 [RMI 2018] 贩运 / Traffickers

翻译来自于 [LibreOJ](https://loj.ac/p/5126)。

**题目译自 [Romanian Master of Informatics 2018](https://rmi.lbi.ro/rmi_2018/) Day1 T3 「[Traffickers](https://rmi.lbi.ro/rmi_2018/_dwl/public.zip)」** 在狂野西部，帕布罗是最臭名昭著的人物之一，他控制着 $N$ 个通过道路连接成树状结构的城市。他的心腹手下是贩运者，日夜不停地运输货物。每名贩运者由一对城市 $(u, v)$ 定义：从时间 $0$ 开始，贩运者从城市 $u$ 沿最短路径前往城市 $v$。在每个整数时间点，贩运者交付 $1$ 单位货物，然后移动到下一个城市。 帕布罗的贩运者难以追踪：一旦一名贩运者到达目标城市 $v$ 并交付货物，在下一时间点，他会瞬间传送回城市 $u$（如果他在时间 $t$ 在城市 $v$ 交付货物，那么在时间 $t + 1$ 他将在城市 $u$ 交付）。由于生意兴隆，帕布罗希望永不停止，贩运者将永远按照他们的路线行动。 尽管帕布罗的系统看似无懈可击，你还是想知道是否能进一步优化。因此，你将对系统执行以下 $3$ 种查询： - $1\ u\ v$：添加一名在城市 $(u, v)$ 间运输的贩运者。 - $2\ u\ v$：移除一名在城市 $(u, v)$ 间运输的贩运者。保证这样的贩运者存在。 - $3\ u\ v\ t_1\ t_2$：你想知道在时间 $t_1$ 到 $t_2$（包含）内，所有现有贩运者在城市 $u$ 到 $v$ 最短路径上（包含两端城市）交付的货物单位总数。

第一行包含一个整数 $N$，表示城市数量。接下来的 $N - 1$ 行每行包含两个整数 $u, v$，表示城市 $u$ 和 $v$ 之间有一条直接道路。 下一行包含一个整数 $K$，表示帕布罗网络中初始的贩运者数量。接下来的 $K$ 行每行包含两个整数 $u, v$，表示一名贩运者的路径城市对。 下一行包含一个整数 $Q$，表示你打算执行的查询数量。接下来的 $Q$ 行每行包含一个查询，格式如上所述。

对于每种类型 $3$ 的查询，在单独的一行输出答案。

### 样例 1 解释 在样例中，第一个查询（类型 $3$）询问在时间 $0$ 到 $3$ 内，城市 $3$ 到 $5$ 的最短路径（路径为 $3-2-1-5$）上交付的货物总量。初始只有一名贩运者从城市 $4$ 到 $1$，他在时间 $1$ 在城市 $2$ 交付 $1$ 单位货物，时间 $2$ 在城市 $1$ 交付 $1$ 单位货物，总计 $2$ 单位。 第二个查询（类型 $1$）添加一名从城市 $2$ 到 $5$ 的贩运者。 第三个查询（类型 $3$）询问在时间 $1$ 到 $5$ 内，城市 $4$ 到 $5$ 的最短路径（路径为 $4-2-1-5$）上交付的货物总量。两名贩运者的交付情况导致总计 $10$ 单位货物。 ### 数据范围 对于所有输入数据，满足： - $1 \leq N \leq 30000$ - $0 \leq K \leq 50000$ - $1 \leq Q \leq 50000$ - $0 \leq t_1 \leq t_2 \leq 2000000000$ - 每名贩运者的路径最多覆盖 $20$ 个城市（包括端点） 每个测试点将单独评分。 | 子任务 | 分值 | 附加限制 | | :----: | :----: | :-------: | | $1$ | $15$ | $N \leq 1000$，$K, Q \leq 500$，$0 \leq t_1 \leq t_2 \leq 10$ | | $2$ | $45$ | $N \leq 10000$，$K, Q \leq 5000$ | | $3$ | $40$ | 无附加限制 |