How far away ？

 

There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.

Input

First line is a single integer T(T<=10), indicating the number of test cases. 

  For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n. 

  Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.

Output

For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.

Sample Input

23 21 2 103 1 151 22 32 21 2 1001 22 1

Sample Output

1025100100

LCA的裸模板题，求出两点的LCA之后用两点到根节点的距离减去LCA到根节点的距离的两倍即可

#include
    
     #include
     
      #include
      
       using namespace std;const int size=4e4+5;struct node{	int u,v,w;	node(){}	node(int u,int v,int w):u(u),v(v),w(w){} };vector
       
         G[size];int dis[size],dep[size],pa[size][20];void dfs(int u,int F,int d,int dd){	dep[u]=d;	dis[u]=dd;	if(u==1) 	{		for(int i=0;i<20;i++) pa[u][i]=1;	}	else	{		pa[u][0]=F;		for(int i=1;i<20;i++)		{			pa[u][i]=pa[pa[u][i-1]][i-1];		}	}	for(int i=0;i
        
         =0;j--)	{		if((1<
         
          =0;i--) { if(pa[u][i]!=pa[v][i]) { u=pa[u][i]; v=pa[v][i]; } } return pa[u][0];}int main(){ int n,m; int t; cin>>t; while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) G[i].clear(); for(int i=1;i
         
        
       
      
     
    

Balanced Lineup

 

For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

Input

Line 1: Two space-separated integers, N and Q. 

Lines 2.. N+1: Line i+1 contains a single integer that is the height of cow i 

Lines N+2.. N+ Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.

Output

Lines 1.. Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.

Sample Input

6 31734251 54 62 2

Sample Output

630

RMQ裸题，可以线段树处理，也可以直接ST处理，这里使用了刘汝佳的白书上的模板。

#include
    
     #include
     
      #include
      
       using namespace std;const int size=5e4+5;int dmax[size][20],dmin[size][20];void RMQ_init(const vector
       
         &A){	int n=A.size();	for(int i=0;i