#P18578. Bandits
Bandits
Bandits
一个王国中有 N 个村庄,以及 N−1 条双向道路。沿这些道路可以从任意一个村庄到达任意另一个村庄。第 i 条道路连接村庄 A_i 和 B_i,长度为 C_i。
国王不断收到关于强盗袭击过路商人的投诉,于是雇用了若干支忠诚的护卫队。每一份安保合同指定一个总部村庄 X 和一个安保半径 R。
如果一条道路属于某条从 X 出发、到另一个村庄、总长度不超过 R 的路径,那么这条道路受到该合同保护。这里要求整条道路包含在该路径中,仅覆盖道路的一部分不算。道路可以同时受到多份合同保护。
请依次处理添加安保合同、查询某条道路当前受到多少份合同保护的操作。
输入格式
第一行包含村庄数 N。
接下来 N−1 行,每行包含三个整数 A_i、B_i、C_i,描述第 i 条道路。村庄编号为 1 至 N,道路按输入顺序编号为 1 至 N−1。
接下来一行包含操作数 Q。
随后 Q 行,每行是一种操作:
-
- X R:添加一份总部位于村庄 X、半径为 R 的安保合同。
- ? Y:查询编号为 Y 的道路当前受到多少份合同保护。
操作按输入顺序发生,尚未添加的合同不参与当前询问。重复添加相同总部和半径的合同,仍算不同的合同。
输出格式
对于每一个 ? 操作,输出一行当前保护该道路的合同数。
如果没有 ? 操作,则没有需要输出的答案。
数据范围
- 1 ≤ N, Q ≤ 10^5。
- 0 ≤ C_i, R ≤ 10^9。
- 1 ≤ A_i, B_i, X ≤ N。
- 1 ≤ Y ≤ N−1。
- 给出的道路构成一棵树。
道路长度可以为 0。N=1 时没有道路,因此合法操作只能是添加合同。
样例输入 1
7
1 2 4
4 2 7
5 1 3
3 6 4
1 6 9
2 7 1
7
+ 2 6
? 3
? 1
+ 6 14
? 1
? 2
? 3
样例输出 1
0
1
2
0
1