|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Round #18Ended |
B - Árbol
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
El mapa de Fitolandia, en donde se aprecian las conexiones entre ciudades de Fitolandia, es representado por un árbol. Nuestra tarea es saber dada dos ciudades cual es la distancia entre estas, pero como este tipo de consultas se debe de realizar muchas veces, debemos hacer esto de manera eficiente.
Input
La primera línea de la entrada es un número $n (1 \le n \le 50000)$ con la cantidad de ciudades del mapa. Cada ciudad está numerada de $0$ a $n-1$. Luego en las próximas $n-1$ líneas hay tres enteros $u$, $v$ y $w$ que corresponden a la arista $(u,v)$ que tiene costo $w (0 \le w \le 1000)$. La próxima línea tiene un entero $q (1 \le q \le 75000)$ que representa la cantidad de consultas que se van a hacer. En las próximas $q$ líneas hay dos enteros que representan las ciudades a las que se les necesita saber la distancia entre ellas.
Output
Por cada consulta en una línea se debe de imprimir la distancia que hay entre las dos ciudades.
Sample test(s)
Input
3
1 0 1
2 0 1
3
0 1
0 2
1 2
Output
1
1
2