Submeter | Todas submissőes | Melhores | Voltar |
PWALKING - Pasture Walking |
Points: 200
The N cows (2 <= N <= 1,000) conveniently numbered 1..N are grazing among the N pastures also conveniently numbered 1..N. Most conveniently of all, cow i is grazing in pasture i.
Some pairs of pastures are connected by one of N-1 bidirectional walkways that the cows can traverse. Walkway i connects pastures A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N) and has a length of L_i (1 <= L_i <= 10,000).
The walkways are set up in such a way that between any two distinct pastures, there is exactly one path of walkways that travels between them. Thus, the walkways form a tree.
The cows are very social and wish to visit each other often. Ever in a hurry, they want you to help them schedule their visits by computing the lengths of the paths between Q (1 <= Q <= 1,000) pairs of pastures (each pair given as a query p1,p2 (1 <= p1 <= N; 1 <= p2 <= N).
Input
- Line 1: Two space-separated integers: N and Q
- Lines 2..N: Line i+1 contains three space-separated integers: A_i, B_i, and L_i
- Lines N+1..N+Q: Each line contains two space-separated integers representing two distinct pastures between which the cows wish to travel: p1 and p2
Output
- Lines 1..Q: Line i contains the length of the path between the two pastures in query i.
Example
Input: 4 2 2 1 2 4 3 2 1 4 3 1 2 3 2 Output: 2 7
Output details
Query 1: The walkway between pastures 1 and 2 has length 2.
Query 2: Travel through the walkway between pastures 3 and 4, then the one between 4 and 1, and finally the one between 1 and 2, for a total length of 7.
Adicionado por: | Wanderley Guimarăes |
Data: | 2008-10-24 |
Tempo limite: | 0.200s-0.400s |
Tamanho do fonte: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Linguagem permitida: | ADA95 DOC ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |
Origem: | USACO October 2008 Qualifying Round |