ZOJ 3195 Design the city LCA转RMQ

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

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

典型的LCA转RMQ

#include<stdio.h>

#include<string.h>

#include<math.h>

#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;i<n;i++)

        ST[i][0]=i;

    for(j=1;(1<<j)<=n;j++)

        for(i=0;i+(1<<j)-1<n;i++)

            ST[i][j]=b[ST[i][j-1]] < b[ST[i+(1<<(j-1))][j-1]]? ST[i][j-1]:ST[i+(1<<(j-1))][j-1];

}

int LCA(int s,int v,int b[])  //这里返回的是最小值的  D中的下标(和E中下标一样)

{

	s=R[s],v=R[v];

	int k;	if(s>v){k=s;s=v;v=k;}

    k=(int)(log((v-s+1)*1.0)/log(2.0));

    return b[ST[s][k]]<b[ST[v-(1<<k)+1][k]]? E[ST[s][k]]:E[ST[v-(1<<k)+1][k]];

}

void DFS(int x,int deep){

	E[en]=x;D[en]=deep; R[x]=en++;

	for(int i=head[x];i!=-1;i=edge[i].nex){

		int v=edge[i].to;

		if(R[v]==-1)

		{

			dis[v]=dis[x]+edge[i].dis;

			DFS(v,deep+1);

			E[en]=x; D[en++]=deep;

		}

	}

}

void Input(int n){

	memset(head,-1,sizeof(head));

	edgenum=0;

	while(--n)

	{

		int u,v,dis; scanf("%d %d %d",&u,&v,&dis);

		addedge(u,v,dis);

		addedge(v,u,dis);

	}

	memset(R,-1,sizeof(R));

	en=0;

	dis[0]=0;

}

int main(){

	int n,i,que,first=0;

	while(~scanf("%d",&n)){

		if(first++)printf("\n");

		Input(n);

		DFS(0,0);

		makeRmqIndex(en,D);

		scanf("%d",&que);

		while(que--)

		{

			int a,b,c;

			scanf("%d %d %d",&a,&b,&c);

			int ans=dis[a]+dis[b]+dis[c]-(dis[LCA(a,c,D)]+dis[LCA(b,c,D)]+dis[LCA(a,b,D)]);

			printf("%d\n",ans);

		}

	}

	return 0;

}