Estructuras Celulares

Submit solution
Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
Forte11
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Patricia la bioquímica está investigando sobre unas estructuras celulares especiales las cuales tienen la propiedad de representarse en forma de grafo. Las células de las estructuras están unidas por un ectoplasma del cual Patricia está buscando propiedades interesantes. Ella se da cuenta que existe un solo camino para cualquier par de células en el grafo. Un camino está formado por la unión de uno o varios caminos.

Patricia está interesada en transportar cierta sustancia química entra cualquier par de células. Cada célula está representada por un único número entero y cada ectoplasma tiene un costo de energía de pasar por él para transportarse de una célula a otra. Patricia le dará algunas preguntas la cual consiste en dos células.

Usted tiene que encontrar el ectoplasma donde la sustancia que se transportará consuma más energía y el ectoplasma que se consuma menos energía en el camino de una célula a otra. ¿Cree que pueda ayudarla en su investigación?

enter image description here

Entrada

La primera línea contiene N \; (2 \le N \le 10^5) que denota el número de células. Entonces habrá N - 1 líneas que contienen tres enteros cada una. Se darán en la forma \(u \; v \; w \; (1 \le u, v \le n, 0 <w \le 10^5, u ≠ v)\) lo que significa que hay un ectoplasma entre la célula u y v y el costo de energía es w. La siguiente línea contiene un número entero q \; (1 \le q \le 25000) que representa el número de preguntas. Cada una de las siguientes líneas q contiene dos enteros x e \(y \; (1 \le x, y \le n, x ≠ y)\).

Salida

Para cada consulta x \; y, debe imprimir una línea que contenga el ectoplasma de menor energía y el de mayor separados por un espacio.

Ejemplo de Entrada

6
3 6 50
2 5 30
2 4 300
1 2 100
1 3 200
4
1 4
4 6
2 5
3 5

Ejemplo de salida

100 300
50 300
30 30
30 200

Comments


  • 4
    jmrh_1  commented on Sept. 3, 2019, 1:38 p.m.

    Si hay mas maneras de resolver este problema pero son mas complicadas . Se puede resolver por Heavy Light Descomposition y Sqrt Descomposition en tree . Saludos


  • 0
    Sekai02  commented on Sept. 1, 2019, 11:39 p.m.

    Muchas gracias por responder.


  • 0
    Sekai02  commented on Aug. 27, 2019, 7:53 p.m.

    ????


  • 4
    Sekai02  commented on Aug. 27, 2019, 7:53 p.m.

    No es posible anadirle al DMOJ la funcionalidad de poder mandar correos a otros usuarios en vez de tener que estar comentando en los problemas o tener que estar pidiendo el correo personal.


    • 0
      Primervirgen  commented on Aug. 28, 2019, 6:38 a.m.

      Bueno men, no creo q sea posible ya q el DMOJ es simplemente una web portable q puede ser montada en cualquier dominio, si buscas en Google te darás cuenta de q no solo existe el: dmoj.uclv.cu sino q también habrán varias q no son cubanas.


  • 0
    Primervirgen  commented on Aug. 22, 2019, 2:36 a.m.

    No hay alguna otra forma de resolver este ejercicio sin usar Ancestro Común más Bajo (LCA)???


    • -5
      Leonardo  commented on Aug. 26, 2019, 1:28 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.