34736번 - Exciting Business Opportunities 다국어

문제

The Treeland subway system consists of $N$ stations connected by $N − 1$ bidirectional tunnels. The tunnels are arranged in such a way that it is always possible to travel between any two stations. The system is already considered to be the most efficient in the country: there are trains between every pair of stations in the system.

Alejandro, from the subway improvement department, has been tasked with making the system even better and more attractive for passengers and businesses. To that end, the department collected $P$ proposals from companies. Each proposal is either to sponsor some station (basically, add a sign with the name of the company on the station), or to open a business at some station (a restaurant, a store, or anything like this). Notice that there is no restriction on the number of proposals that can be accepted for each station.

Companies willing to open businesses in the system, though, informed that they will withdraw their proposals unless the station $X$ where their business is located, is either a sponsored station or there is a train between two sponsored stations that goes through $X$. Of course, Alejandro does not want to select proposals that will later be withdrawn. Thus, he will make sure to select a set of proposals such that no proposal in the set will be withdrawn. He calls such a set a valid set of proposals.

The figure below shows sponsored stations in red/dashed circles and businesses in blue/dotted circles. The set of proposals in (a) is valid because the business proposal for station 3ドル$ is located exactly on the path between the two sponsored stations 2ドル$ and 4ドル$. The set of proposals in (b) is also valid, because the business proposal for station 1ドル$ is located exactly on a sponsored station. On the contrary, the set of proposals in (c) is not valid: even though the business proposal for station 3ドル$ is located on a path between two sponsored stations, the business proposal for station 5ドル$ is not.

To choose a valid set, Alejandro took the $P$ proposals (each one described on a piece of paper), and numbered them from 1ドル$ to $P$. Now he wants to select a contiguous range of proposals that form a valid set. More precisely, he wants to pick two integers $i$ and $j,ドル with 1ドル ≤ i ≤ j ≤ P,ドル such that proposals $i, i + 1, \dots , j$ form a valid set; besides, he wants the set to be as large as possible. Alejandro is not sure about which should be the initial proposal $i$ in the range he will select. Help him compute for each $i$ from 1ドル$ to $P,ドル the size of the largest contiguous range of proposals that form a valid set, starting at proposal $i$.

입력

The first line contains an integer $N$ (2ドル ≤ N ≤ 10^5$) indicating the number of stations in the subway system. Each station is identified by a distinct integer from 1ドル$ to $N$.

Each of the next $N − 1$ lines contains two integers $U$ and $V$ (1ドル ≤ U, V ≤ N$ and $U \ne V$), representing that there is a bidirectional tunnel between stations $U$ and $V$. It is guaranteed that it is possible to go from any station to any other station using the tunnels.

The next line contains an integer $P$ (1ドル ≤ P ≤ 10^5 $) denoting the number of proposals submitted by companies. Each proposal is identified by a distinct integer from 1ドル$ to $P$.

The $i$-th of the next $P$ lines describes proposal $i$ with a character $C$ and an integer $X$ (1ドル ≤ X ≤ N$). For a sponsoring proposal $C$ is the lowercase letter “s”, while for a business proposal it is the lowercase letter “b”; in both cases $X$ is the corresponding station. Notice that each station can have an arbitrary number of proposals of any type.

출력

Output $P$ lines. The $i$-th line must contain an integer indicating the size of the largest valid set of contiguous proposals whose initial proposal is $i$.

제한

노트