|
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.
V Copa UHEnded |
D - Viaje turístico
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Fito quiere hacer turismo por cierto país y está estudiando las ofertas de algunas agencias. El viaje está compuesto por $n$ atracciones de diverso tipo y Fito quiere visitarlas todas.
La compañía incluye en el plan el vuelo al primer lugar escogido por Fito, pero de ahí en adelante le corresponde a él moverse por el país. Por suerte en esa zona hay una red de transporte por tren gratuita. La red está compuesta por $n-1$ líneas que conectan pares de atracciones y se puede viajar entre cualquier par usando solo esta red. La razón de que el viaje en tren sea gratis es para promover el turismo, pero también hay otra razón menos noble. Al entrar en la zona turística se le entrega un documento que lo acredita como turista permitiéndole el uso gratuito del tren. Cada vez que un turista se monta en el tren solo debe enseñar dicho documento y puede viajar sin problemas. Sin embargo en cada viaje se añade al documento una marca indicando que se utilizó el tren. La parte negativa es que la primera vez que un turista llega a una atracción le cobran un impuesto por cada marca en su documento. La razón de esta medida es que los dueños de cada atracción quieren ser siempre los primeros en ser visitados y por tanto penalizan a los turistas según el tiempo que se demoran en llegar. En esta zona son muy celosos con las reglas y se cuidan mucho de trampas posibles, como viajar en tren sin marcar el documento o utilizar algún otro medio de transporte.
Fito está decidido a visitar todas las atracciones turísticas por lo que quiere saber el menor gasto, por concepto de impuestos, que le permita hacer esto.
La compañía incluye en el plan el vuelo al primer lugar escogido por Fito, pero de ahí en adelante le corresponde a él moverse por el país. Por suerte en esa zona hay una red de transporte por tren gratuita. La red está compuesta por $n-1$ líneas que conectan pares de atracciones y se puede viajar entre cualquier par usando solo esta red. La razón de que el viaje en tren sea gratis es para promover el turismo, pero también hay otra razón menos noble. Al entrar en la zona turística se le entrega un documento que lo acredita como turista permitiéndole el uso gratuito del tren. Cada vez que un turista se monta en el tren solo debe enseñar dicho documento y puede viajar sin problemas. Sin embargo en cada viaje se añade al documento una marca indicando que se utilizó el tren. La parte negativa es que la primera vez que un turista llega a una atracción le cobran un impuesto por cada marca en su documento. La razón de esta medida es que los dueños de cada atracción quieren ser siempre los primeros en ser visitados y por tanto penalizan a los turistas según el tiempo que se demoran en llegar. En esta zona son muy celosos con las reglas y se cuidan mucho de trampas posibles, como viajar en tren sin marcar el documento o utilizar algún otro medio de transporte.
Fito está decidido a visitar todas las atracciones turísticas por lo que quiere saber el menor gasto, por concepto de impuestos, que le permita hacer esto.
Input
La primera línea de la entrada contiene un entero $n$ $(1 \leq n \leq 10^{6})$ representando la cantidad de atracciones que va visitar Fito. Las siguientes $n-1$ líneas describen los posibles viajes en tren, cada una con dos números enteros, separados por un espacio.
Output
La salida debe ser un número entero, que indica la menor cantidad de impuestos que debe pagar Fito si visita todas las atracciones.
Sample test(s)
Input
3
1 2
1 3
Output
3