国际大学生程序设计竞赛例题_5.9距离

1,求树的两个结点之间的距离
2,解答:求u和v的最近公共祖先(LCA)
先做一次dfs,转化为求第一次出现的u和v之间深度最大的点即是它们的公共祖先.
3,实例代码:

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

const int maxn=20010;

struct node
{
    int v;//孩子结点
    int d;//到该节点的距离
};

//注意vector在树问题中的使用
vector<node> tree[maxn];

int dfsnum[maxn]; //记录遍历的节点
int depth[maxn]; //记录节点对应的深度
int first[maxn]; //记录结点第一次访问到时的下标
int dis[maxn];//记录个点到根的距离
int top; //记录总的步伐数
void dfs(int m,int f,int dep,int d) //当前节点编号,父节点编号,深度
{
    dfsnum[top]=m;
    depth[top]=dep;
    first[m]=top;
    dis[m]=d;
    top++;
    for(unsigned i=0;i<tree[m].size();i++)
    {
        if(tree[m][i].v==f)
            continue;
        dfs(tree[m][i].v,m,dep+1,d+(tree[m][i].d));
        dfsnum[top]=m; //注:每条边回溯一次,所以top的值=n+n-1
        depth[top]=dep;
        top++;
    }
}

int dp[maxn][18];
void makeRmqIndex(int n,int b[]) //返回最小值对应的下标
{
    int i,j;
    for(i=0;i<n;i++)
        dp[i][0]=i;
    for(j=1;(1<<j)<=n;j++)
        for(i=0;i+(1<<j)-1<n;i++)
            dp[i][j]=b[dp[i][j-1]] < b[dp[i+(1<<(j-1))][j-1]]? dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
}
int rmqIndex(int s,int v,int b[])
{
    int k=(int)(log((v-s+1)*1.0)/log(2.0));
    return b[dp[s][k]]<b[dp[v-(1<<k)+1][k]]? dp[s][k]:dp[v-(1<<k)+1][k];
}


int n,qnum;//边数和询问数
int cnt;//测试数目
int main()
{
    freopen("5.9.in","r",stdin);
    cin>>cnt;
    while(cnt--)
    {
        cin>>n>>qnum; //n是节点数
        for(int i=0;i<n;i++)
            tree[i].clear();
        top=0;
        int x,y,d;
        node temp;
        for(int i=0;i<n-1;i++)
        {
            cin>>x>>y>>d;
            x--,y--;
            temp.d=d;
            temp.v=y;
            tree[x].push_back(temp);
            temp.v=x;
            tree[y].push_back(temp);
        }
        dfs(0,-1,0,0);
        makeRmqIndex(top,depth);
        while(qnum--)
        {
            cin>>x>>y;
            x--,y--;
            if(first[x]>first[y])
            {
                d=x;
                x=y;
                y=d;
            }
            int lca=dfsnum[rmqIndex(first[x],first[y],depth)];//得到lca
            cout<<dis[x]+dis[y]-2*dis[lca]<<endl;
        }
    }
    return 0;
}