HDU 2586 How far away? LCA 转化成RMQ

链接：http://acm.hdu.edu.cn/showproblem.php?pid=2586

【题意】

给出一个N 个和N-1条边的连通图，询问任意两点间的距离。N<=40000 。

【分析】

点太多了，用最短路算法来求超时。只够求一个点的单源最短路，而且不能用O(n²)的算法。正确的做法就是求出两点的最近公共祖先，利用点v到树的根节点距离dis[v]来换算。设要求的两点分别为u和v, 那么u和v的距离d=dis[u]+dis[v]-2*dis[LCA(u,v)] 。

现在还有一个问题就是输入是一个图，并不是一棵树，怎么有根节点？怎么确定父子关系？
这个挺好办的，随便选一个点当根节点，从这个节点开始分层遍历，这样就有树的结构了。求dis数组我原先是用单源最短路来求的，不过仔细想下，因为原图就是一棵树，从根节点到任意点的路径是唯一的，于是就可以用递推的方式求的，在分层遍历中计算就好了。遍历递归的层数有点多，可能会爆栈。

这里我使用LCA转RMQ的方法来求的。

【代码】

  1 #pragma comment(linker, "/STACK:1024000000,1024000000") //扩栈
  2 #include <stdio.h>
  3 #include <string.h>
  4 #include <vector>
  5 #include <cmath>
  6 using namespace std;
  7 int n,m;
  8 struct edge
  9 {
 10     int d,v,next;
 11     edge(){}
 12     edge(int _d,int _v,int _next)
 13     {
 14         d=_d;v=_v;next=_next;
 15     }
 16 }data[80003];
 17 int map[40003];
 18 int pool;
 19 void addedge(int s,int e,int v)
 20 {
 21     int t=map[s];
 22     data[pool++]=edge(e,v,t);
 23     map[s]=pool-1;
 24 }
 25 vector<int> f;
 26 vector<int> b;
 27 bool ifv[40003];
 28 int pos[40003];
 29 int dis[40003];
 30 void dfs(int cur,int c)
 31 {
 32     if (cur<0 || cur>=n) return;
 33     ifv[cur]=true;
 34     pos[cur]=(int)f.size();
 35     f.push_back(cur);
 36     b.push_back(c);
 37     int p=map[cur];
 38     while (p!=-1)
 39     {
 40        if (!ifv[data[p].d])
 41        {
 42            dis[data[p].d]=dis[cur]+data[p].v;
 43            dfs(data[p].d,c+1);
 44            f.push_back(cur);
 45            b.push_back(c);
 46        }
 47         p=data[p].next;
 48     }
 49 }
 50 int rmq[80003][17];
 51 void makermq(int n,int bitn)
 52 {
 53    for (int i=0; i<n; ++i)
 54        rmq[i][0]=b[i];
 55    for (int j=1; j<bitn; ++j)
 56      for (int i=0; i<n; ++i)
 57      {
 58         if (i+(1<<(j-1))>=n) break;
 59         rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
 60      }
 61 }
 62 int query(int s,int e)
 63 {
 64     int k=(int)((log(e-s+1.0)/log(2.0)));
 65     return min(rmq[s][k],rmq[e-(1<<k)+1][k]);
 66 }
 67 int main()
 68 {
 69     int T;
 70     scanf("%d",&T);
 71     while (T--)
 72     {
 73         pool=0;
 74         f.clear();
 75         b.clear();
 76         memset(map,-1,sizeof map);
 77         memset(ifv,0,sizeof ifv);
 78         scanf("%d%d",&n,&m);
 79         int s,e,v;
 80         for (int i=0;i<n-1;++i)
 81         {
 82             scanf("%d%d%d",&s,&e,&v);
 83             addedge(s-1,e-1,v);
 84             addedge(e-1,s-1,v);
 85         }
 86         dis[0]=0;
 87         dfs(0,0);
 88         makermq(b.size(),(int)(log((double)b.size())/log(2.0)));
 89         for (int i=0;i<m;++i)
 90         {
 91             int u,v;
 92             scanf("%d%d",&u,&v);
 93             --u;--v;
 94             int s=pos[u];
 95             int e=pos[v];
 96             if (s>e) swap(s,e);
 97             int k=query(s,e);
 98             k=f[k];
 99             int ans=dis[u]+dis[v]-2*dis[k];
100             printf("%d
",ans);
101         }
102     }
103 }

View Code