26186번 - Bandits 다국어

There is a kingdom with $N$ villages and $N-1$ bidirectional roads that allow the citizens to travel between any pair of villages following a path consisting of one or more roads. The $i$-th road connects villages $A_i$ and $B_i$ and has length $C_i$.

The king has noticed an increasing number of complaints about bandits attacking the merchants travelling along the roads in the kingdom. He has tasked his advisor with solving this problem by hiring loyal groups of thugs that will act as security agencies. Each such security contract guarantees security of all roads in a radius of $R_j$ from the village $X_j$ with the group's headquarters. A road is protected by the contract if it is part of a path of length at most $R_j$ from $X_j$ to some other village. Some roads may be protected by several contracts and are therefore more secure.

Write a program that will process queries about new contracts and answer queries about the security of individual roads, that is the number of contracts currently securing that road.

The first line contains the number of villages $N$. The roads connecting these villages are described in the following $N-1$ lines. The description of each road consists of space-separated integers $A_i$, $B_i$ and $C_i$, which represent a road of length $C_i$ between villages $A_i$ and $B_i$. The villages are numbered from $1$ to $N$.

Next line contains the number of queries $Q$. The following $Q$ lines describe the queries. The query that represents a new security contract starts with character '+' and is followed by the headquarters village $X_j$ and security radius $R_j$. The query about the security of some road starts with character '?' and is followed by the number $Y_j$ of that road. The roads are numbered from $1$ to $N-1$ in order in which they are given in the input.

Process the queries in the given order and for every query of type '?' output one line with the current number of contracts securing the road $Y_j$.

• $1 \leq N, Q \leq 10^5$
• $0 \leq C_i, R_j \leq 10^9$