Journey

Time Limit: 1 Sec  

Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/problem/show/92

Description

Bob has traveled to byteland, he find the N cities in byteland formed a tree structure, a tree structure is very special structure, there is exactly one path connecting each pair of nodes, and a tree with N nodes has N−1 edges.

As a traveler, Bob wants to journey between those N cities, and he know the time each road will cost. he advises the king of byteland building a new road to save time, and then, a new road was built. Now Bob has Q journey plan, give you the start city and destination city, please tell Bob how many time is saved by add a road if he always choose the shortest path. Note that if it's better not journey from the new roads, the answer is 0.

Input

First line of the input is a single integer T(1≤T≤20), indicating there are T test cases.

For each test case, the first will line contain two integers N(2≤N≤105) and Q(1≤Q≤105), indicating the number of cities in byteland and the journey plans. Then N line followed, each line will contain three integer x, y(1≤x,y≤N) and z(1≤z≤1000) indicating there is a road cost z time connect the xth city and the yth city, the first N−1 roads will form a tree structure, indicating the original roads, and the Nth line is the road built after Bob advised the king. Then Q line followed, each line will contain two integer x and y(1≤x,y≤N), indicating there is a journey plan from the xth city to yth city.

Output

For each case, you should first output Case #t: in a single line, where t indicating the case number between 1 and T, then Q lines followed, the ith line contains one integer indicating the time could saved in ith journey plan.

Sample Input

15 51 2 32 3 44 1 53 5 13 1 51 21 32 53 44 5

 

Sample Output

Case #1:02022

HINT

 

题意

给你一棵树，然后加了一条边，然后给Q次询问，问你这些点之间的最短距离缩短了多少

题解：

加了边之后，你走的方式就变成三种了，要么和原来一样，要么就是u-A-B-v,要么就是u-B-A-v这种

tarjan预处理一下距离跑一发就好了

代码：

//qscqesze#pragma comment(linker, "/STACK:1024000000,1024000000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include