P2912 [USACO08OCT] Pasture Walking G

The $N$ cows ($2 \le N \le 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 \le A_i \le N; 1 \le B_i \le N$) and has a length of $L_i$ ($1 \le L_i \le 10,000$). The walkways are set up so 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. Being in a hurry, they want you to help schedule their visits by computing the lengths of the paths for $Q$ pairs of pastures ($1 < Q < 1,000$). Each pair is given as a query $p1$, $p2$ ($1 \le p1 \le N; 1 \le p2 \le N$).

* 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$.

* Lines $1$…$Q$: Line $i$ contains the length of the path between the two pastures in query $i$.

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$. Translated by ChatGPT 5