题目描述

题目译自 Romanian Master of Informatics 2018 Day1 T3 「Traffickers」

在狂野西部，帕布罗是最臭名昭著的人物之一，他控制着 $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$ 的查询，在单独的一行输出答案。

5
1 2
2 3
2 4
1 5
1
4 1
3
3 3 5 0 3
1 2 5
3 4 5 1 5

2
10

在样例中，第一个查询（类型 $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$ 个城市（包括端点）

每个测试点将单独评分。