【？】距离（distance）

Time Limit:1000MS  Memory Limit:65536K
 Total Submit:15 Accepted:7

Description

 【问题描述】
　　给出n个点的一棵树，多次询问两点之间的最短距离。（边是双向的）

【输入格式】
　　测试数据第一行为两个整数 N 和 M（1 < n≤10000, 0 < m≤20000）。 N表示点数，M表示询问次数。下来 n-1行，每行三个整数 x y k，表示点x和点y之间存在一条边长度为k（ 0 < k≤100）。再接下来m行，每行两个整数 x y，表示询问点x到点y的最短距离。

【输出格式】
　　输出m行。对于每次询问，输出一行。

Input

 2 2
1 2 100
1 2
2 1

Output

 100
100

Sample Input

3 2
1 2 10
3 1 15
1 2
3 2


Sample Output

10
25

我不明白怎么建树

我知道怎么建树了，但是如何应用RMQ。。。

我这有一个讲RMQ和LCA的空间，讲的不错，等回宿舍了发上来。我也只做过一道RMQ的题，LCA还没做。。

http://community.(ST)_algorithm
希望对你有用

看不到。。。

测试数据过了，但是WRONG ANSEWER。错哪里了？？

#include<iostream>
#include<cmath>
using namespace std;

const int maxn=10000+5;
int tol=0,n,m;
int map[maxn][maxn];
int f[maxn][3];
int deep[maxn]; //第i点在树中的深度 
int dist[maxn]; //第i点离树的根节点的距离
int p[maxn][15]; //第i点的2^j父亲

void init()
{
     cin>>n>>m;
     for (int i=1;i<n;i++)
     {
         int x,y,z;
         cin>>x>>y>>z;
         map[x][++map[x][0]]=y;
         map[y][++map[y][0]]=x;
         f[i][0]=x;f[i][1]=y;f[i][2]=z;
     }
}

void build(int x,int d)
{
     deep[x]=d++;//记录深度
     for (int i=1;i<=map[x][0];i++)
     {
         if (deep[map[x][i]]!=0) continue;
         p[map[x][i]][0]=x;
         for (int j=1;j<n;j++)
           if (f[j][0]==x && f[j][1]==map[x][i]
           || f[j][0]==map[x][i] && f[j][1]==x)
           {
              dist[map[x][i]]=dist[x]+f[j][2];
              break;
           }
         if (map[map[x][i]][0]==1) continue;
         build(map[x][i],d);
     } 
}

void tree()
{
     //设根节点为点1并建树
     dist[1]=0;
     build(1,1); 
}

void find()
{
     //预处理 
     for (int i=2;i<=n;i++)
     {
         for (int j=1;j<=n;j++)
         {
             int a=(int)pow(2,(double)j);
             if (a>deep[i]) break;
             p[i][j]=p[p[i][j-1]][j-1];
         }
     }
}

int solve(int x,int y)
{
    if (deep[x]>deep[y]) {int z=x; x=y; y=z;}
    
    int j=14;
    while (deep[x]<deep[y])
    {
          while (deep[y]-(1<<j)<deep[x]) j--;
          y=p[y][j];
    }
    
    j=14;
    while (x!=y)
    {
          while (j>0 && (deep[x]-(1<<j)<0 || p[x][j]==p[y][j])) j--;
          x=p[x][j];
          y=p[y][j];
    }
}

void doit()
{
     for (int i=1;i<=m;i++)
     {
         int x,y;
         cin>>x>>y;
         int com=solve(x,y);
         cout<<dist[x]-dist[com]+dist[y]-dist[com]<<endl;
     }
}

int main()
{
    init();
    tree();
    find();
    doit();
    return 0;   
}