LAC和RMQ的转化---zoj_3195
??????? 我擦。。纠结了好久啊,从SF到TLE，先总结2个错误1：(int)(log(1.0*(b-a+1))/log(2.0));注意括号。2：i+(1<<(j-1))位移操作符加上括号，以后一定要记住，不然就是(1+i)<<j-1，这我去。解决掉越界，然后使用c输入输出，使用++i,最后终于AC了
??????? 这题其实LCA的tarjan也可以搞，但是tarjan的一个不爽的地方就是Q个查询必须对每一个节点做成类似邻接表的形式，才能保证对于每个查询都是O(1)的消耗，而这题更加恶心的地方就是求3个点的LCA。。。。，所以考虑转化为在线的方法去求解。
??????? 那么自然想到转化为RMQ问题，如何转化，DFS题目中的树，按照遍历的顺序形成一个序列，长度为2*N-1，这个序列中每个节点不只出现一次（废话）。那么对于一个询问（u,v）,LAC(G,U,V)其实就是RMQ（L,a,b），a,b是序列中U,V第一次出现的序号。
??????? 那么RMQ对于哪个量求最值呢，这里选取了树中节点的深度。。根为0。在预处理时，需要先DFS这棵树，存好每一个节点对应的深度，和到根的路径长度。
??????? 然后就是基于DP的RMQ初始话，对于res[50001*2-1][18],j从1到log(2)(2*n-1)，i从0到n-(1<<(j-1))+1，这里不处理好会越界。然后就是DP，状态转移方程为f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]).
??????? 最后求解RMQ就很简单了。。。对于RMQ(L,a,b)=min(f[a][k],f[b-(1<<k)+1][k])其中，K=log(2)(b-a+1).
?????? 最后要补充一点的是，对于题中图G的表达，尽量使用类似邻接表的形式，遍历的效率是E+V，如果使用邻接矩阵，效率是V*V.
zoj_3195
#include<iostream>#include<vector>#include<cstdio>#include<cmath>#include<string.h>using namespace std;int n,q;const static int MM=50005;int length[MM+1];//int deep[MM+1];int first[MM+1];//int res[100005][18];int path[2*MM-1][18];bool visit[MM];int indx;class block{public:int deep;int id;};block rmq[2*MM-1];class node{public://int id;//vector<node*>v;//vector<int>dist;int t;int dis;};vector<node>nlist[MM];/*void dfs(node*p,node*pre,int dept,int l){int size=p->v.size();block b;b.deep=dept;b.id=p->id;first[p->id]=indx;rmq[indx++]=b;for(int i=0;i<size;++i){if(pre!=p->v[i]){length[p->v[i]->id]=l+p->dist[i];deep[p->id]=dept+1;dfs(p->v[i],p,dept+1,l+p->dist[i]);rmq[indx++]=b;}}return;}*/void dfs(int x,int dept,int l){int size=nlist[x].size();block b;b.deep=dept;b.id=x;first[x]=indx;rmq[indx++]=b;length[x]=l;visit[x]=true;for(int i=0;i<size;++i){int y=nlist[x][i].t;if(!visit[y]){//deep[p->id]=dept+1;dfs(y,dept+1,l+nlist[x][i].dis);rmq[indx++]=b;}}return;}void rmqInit(){int maxi=2*n-1;int maxj=(int)(log(maxi*1.0)/log(2.0));for(int i=0;i<maxi;++i){//res[i][0]=rmq[i].deep;path[i][0]=i;}for(int j=1;j<=maxj;++j){for(int i=0;i<maxi+1-(1<<j);++i){if(rmq[path[i][j-1]].deep<rmq[path[i+(1<<(j-1))][j-1]].deep)//if(res[i][j-1]<res[i+1<<(j-1)][j-1]){//res[i][j]=res[i][j-1];path[i][j]=path[i][j-1];}else{//res[i][j]=res[i+1<<(j-1)][j-1];path[i][j]=path[i+(1<<(j-1))][j-1];}}}}int getRmq(int a,int b){if(a>b){int temp=a;a=b;b=temp;}int k=(int)(log(1.0*(b-a+1))/log(2.0));if(rmq[path[a][k]].deep<rmq[path[b-(1<<k)+1][k]].deep)//if(res[a][k]<res[b-(1<<k)+1][k]){return path[a][k];}else{return path[b-(1<<k)+1][k];}}//vector<node*>nlist;int main(){freopen("e:\\zoj\\zoj_3195.txt","r",stdin);int cases=0;while(scanf("%d",&n)!=EOF){if(cases!=0)printf("\n");++cases;//nlist.clear();memset(visit,false,sizeof(visit));//memset(length,0,sizeof(length));//memset(deep,0,sizeof(deep));//memset(rmq,0,sizeof(rmq));//memset(first,0,sizeof(first));//memset(path,0,sizeof(path));//memset(res,0,sizeof(res));indx=0;/*for(int i=0;i<n;i++){node*nn=new node;nn->id=i;nlist.push_back(nn);}*/for(int i=0;i<n;++i) nlist[i].clear();for(int i=0;i<n-1;i++){int a,b,d;//cin>>a>>b>>d;scanf("%d%d%d",&a,&b,&d);node tmp;tmp.t=b;tmp.dis=d;nlist[a].push_back(tmp);tmp.t=a;nlist[b].push_back(tmp);//nlist[a]->v.push_back(nlist[b]);//nlist[a]->dist.push_back(d);//nlist[b]->v.push_back(nlist[a]);//nlist[b]->dist.push_back(d);}//dfs(nlist[0],NULL,0,0);dfs(0,0,0);rmqInit();//cin>>q;scanf("%d",&q);int ans=0;while(q--){int a,b,c;//cin>>a>>b>>c;scanf("%d%d%d",&a,&b,&c);int fa=first[a];int fb=first[b];int fc=first[c];int lab=getRmq(fa,fb);int lac=getRmq(fa,fc);int lbc=getRmq(fb,fc);int labc=getRmq(lab,fc);if(rmq[lab].deep>rmq[labc].deep)ans=length[a]+length[b]+length[c]-2*length[rmq[labc].id]-length[rmq[lab].id];else if(rmq[lac].deep>rmq[labc].deep)ans=length[a]+length[b]+length[c]-2*length[rmq[labc].id]-length[rmq[lac].id];else if(rmq[lbc].deep>rmq[labc].deep)ans=length[a]+length[b]+length[c]-2*length[rmq[labc].id]-length[rmq[lbc].id];else ans=length[a]+length[b]+length[c]-3*length[rmq[labc].id];printf("%d\n",ans);}}return 0;}?