Distance query - MarisaOJ: Marisa Online Judge

Distance query

Time limit: 1000 ms
Memory limit: 256 MB
You are given a weighted tree of n vertices rooted at 1. There are q queries, each of the form (u,v), find the shortest distance between u and v. ### Input - The first line contain 2 integers n,q. - The next n−1 lines, each line contains 3 integers u,v,w, there is an edge of weight w between u and v. - The next q lines, each line contains 2 integers u,v, an query. ### Output - Print q integers, the answers to q queries. ### Constraints - 1≤n,q≤105. - 1≤u,v≤n. - 1≤w≤109. ### Example Input: 73121132243252361373454627 Output: 576