3744 - Fito Begins in Fashion

Created by Norge Vizcay Zaldívar
Added by ymondelo20 (2016-10-03)
Limits
Total Time: 45000 MS | Test Time: 7000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Our problem takes place in a country known as Borland. This country is peculiar as it consists of N cities numbered from 1 to N, and N-1 bidirectional roads that allow at least one path to exist between each pair of cities formed by such roads. In this country lives the main character of our story, Fito, a programmer hired by a famous fashion company called Vog. This company plans to exhibit two fashion shows in the country and has already calculated, for each city, the number of gold coins it would gain by holding the first and second parade in that city. However, this gain can change every day. We also know that each trip between two cities directly connected by a road cost them exactly one gold coin. The company asks Fito to "program" his computer to efficiently answer these three types of questions:
  • 0 u x - Change the number of gold coins gained by exhibiting the first parade in city u to x (x <= 104).
  • 1 u x - Change the number of gold coins gained by exhibiting the second parade in city u to (x <= 104).
  • 2 u - If the first parade were to be held in city u, what is the optimal city where the second parade should take place to maximize the total profit? What would this optimal total profit be?
The total profit is defined as the number of gold coins gained by the first parade in city u plus the gold coins gained by the second parade in city v (where city v is the choice for the second parade) minus the number of coins needed to travel from city u to v. It may also be possible that the optimal city for the second parade is the same city where the first parade takes place.
Nuestro problema se desarrolla en un país conocido como Borland. Este país es bastante peculiar pues está formado por N ciudades numeradas de 1 a N, y N-1 carreteras bidireccionales que permiten que exista al menos un camino entre cada par de ciudades formados por dichas carreteras. En dicho país vive el personaje principal de nuestra historia, Fito, que es un programador contratado por una compañía muy famosa de moda llamada Vog. Esta empresa planea exhibir dos desfiles de moda en el país y ya han calculado la ganancia en monedas del primer y segundo desfile en cada ciudad, pero esta ganancia puede cambiar cada día. También conocen que cada viaje entre dos ciudades conectadas directamente por una carretera les costará una moneda exactamente. Para ellos Fito deberá desarrollar un sistema que garantice tres tipos de preguntas de la forma más eficiente posible:
  • 0 u x - La ganancia del primer desfile en la ciudad u cambió a x (x <= 104)..
  • 1 u x - La ganancia del segundo desfile en la ciudad u cambió a x (x <= 104)..
  • 2 u - Si se realizara el primer desfile en la ciudad u, cuál sería la ciudad en la que se debería realizar el segundo desfile para maximizar la ganancia total y cual sería esta ganancia.
La ganancia total está definida como la ganancia del primer desfile en la ciudad u más la del segundo desfile en la ciudad v menos la cantidad de carreteras a recorrer para viajar de u a v. Puede también ser posible que el segundo desfile se decida realizar en la misma ciudad que el primero.
Our problem takes place in a country known as Borland. This country is peculiar as it consists of N cities numbered from 1 to N, and N-1 bidirectional roads that allow at least one path to exist between each pair of cities formed by such roads. In this country lives the main character of our story, Fito, a programmer hired by a famous fashion company called Vog. This company plans to exhibit two fashion shows in the country and has already calculated, for each city, the number of gold coins it would gain by holding the first and second parade in that city. However, this gain can change every day. We also know that each trip between two cities directly connected by a road cost them exactly one gold coin. The company asks Fito to "program" his computer to efficiently answer these three types of questions:
  • 0 u x - Change the number of gold coins gained by exhibiting the first parade in city u to x (x <= 104).
  • 1 u x - Change the number of gold coins gained by exhibiting the second parade in city u to (x <= 104).
  • 2 u - If the first parade were to be held in city u, what is the optimal city where the second parade should take place to maximize the total profit? What would this optimal total profit be?
The total profit is defined as the number of gold coins gained by the first parade in city u plus the gold coins gained by the second parade in city v (where city v is the choice for the second parade) minus the number of coins needed to travel from city u to v. It may also be possible that the optimal city for the second parade is the same city where the first parade takes place.

Input specification

The first line of input contains an integer N (1 N 105) the number of cities in Borland. The following N-1 lines will have two integers u and v representing a two-way road between cities u and v. Then a line with N space separated integers, the i-th of these will be Ai (0  Ai 104), the number of coins gained by exhibiting the first parade in the i-th city. Then, a line with N space separated integers, the i-th of these will be Bi (0 Bi 104) the number of coins gained by exhibiting the second parade in the i-th city. The next line contains integer Q (0 105), the number of questions to process. Next Q lines will follow, each with a question in the described format.
La primera línea de la entrada contiene un entero N (1 N 105) la cantidad de ciudades en Borland. Las siguientes N-1 líneas tendrán dos enteros u y v representando una carretera bidireccional entre las ciudades u y v. Luego una línea con N enteros, el iésimo será el valor Ai (0  Ai 104), la ganancia de hacer el primer desfile en la ciudad iésima. Luego una línea con N enteros, el iésimo será el valor Bi (0 Bi 104), la ganancia de hacer el segundo desfile en la ciudad iésima. La siguiente línea contiene un entero Q (0 105), la cantidad de preguntas que se realizarán. Finalmente se tendrán Q líneas, cada una con una pregunta en el formato descrito.
;jsessionid=5897C7E603ACFB1818E20C943ADD9E85
The first line of input contains an integer N (1 N 105) the number of cities in Borland. The following N-1 lines will have two integers u and v representing a two-way road between cities u and v. Then a line with N space separated integers, the i-th of these will be Ai (0  Ai 104), the number of coins gained by exhibiting the first parade in the i-th city. Then, a line with N space separated integers, the i-th of these will be Bi (0 Bi 104) the number of coins gained by exhibiting the second parade in the i-th city. The next line contains integer Q (0 105), the number of questions to process. Next Q lines will follow, each with a question in the described format.

Output specification

For each of the questions of type 2, print two integers v and g, where v represents the ID of the optimal city where the second parade should be held to maximize total profit and g is the optimal total profit. If there are several cities that meet those conditions, you must choose the one that has the smallest ID. Notice that your answer should take into consideration all previous changes of types 0 and 1 that have occurred before each corresponding question of type 2.
Para cada una de las preguntas de tipo 2 imprima dos enteros v y g, donde representa el ID de la ciudad óptima donde el segundo desfile debe ser realizado para maximizar la ganancia total y que es la ganancia total. Si hay varias ciudades que cumplen estas condiciones se deberá imprimir la de menor ID. Notar que su respuesta debe tener en cuenta todos los cambios previos de tipo 0 y 1 que ocurrieron antes de la pregunta de tipo 2 correspondiente. 
The first line of input contains an integer N (1 N 105) the number of cities in Borland. The following N-1 lines will have two integers u and v representing a two-way road between cities u and v. Then a line with N space separated integers, the i-th of these will be Ai (0  Ai 104), the number of coins gained by exhibiting the first parade in the i-th city. Then, a line with N space separated integers, the i-th of these will be Bi (0 Bi 104) the number of coins gained by exhibiting the second parade in the i-th city. The next line contains integer Q (0 105), the number of questions to process. Next Q lines will follow, each with a question in the described format.

Sample input

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

Sample output

2 5
1 4
4 5

Hint(s)

Use fast I/O (i.e. scanf/printf for C/C++, BufferedReader for java, etc.).
Use entrada y lectura rápida (i.e. scanf/printf para C/C++, BufferedReader para java, etc.).
Use fast I/O (i.e. scanf/printf for C/C++, BufferedReader for java, etc.).