ZOJ 3195 Design the city LCA转RMQ

题意：给定n个点，下面n-1行 u , v ,dis 表示一条无向边和边权值，这里给了一颗无向树

下面m表示m个询问，问 u v n 三点最短距离

典型的LCA转RMQ

#include
#include
#include
#define N 100000
#define INF 1<<29
#define Logo 17
using namespace std;

inline int Min(int a,int b){return a>b b:a;}

struct node{
	int f,to,dis,nex;
}edge[N];
int edgenum,head[N],dis[N];
int E[N*2],R[N],D[N*2],en;//LCA
int ST[N*2][Logo];


void addedge(int u,int v,int dis){
	edge[edgenum].f=u;	    edge[edgenum].to=v;
	edge[edgenum].dis=dis;	edge[edgenum].nex=head[u];
	head[u]=edgenum++;
}
void makeRmqIndex(int n,int b[]) //返回最小值对应的下标   
{  
    int i,j;  
    for(i=0;iv){k=s;s=v;v=k;}
    k=(int)(log((v-s+1)*1.0)/log(2.0));  
    return b[ST[s][k]]