codevs 1036 商务旅行 (LCA)

Description

某首都城市的商人要经常到各城镇去做生意,他们按自己的路线去做,目的是为了更好的节约时间。

假设有N个城镇,首都编号为1,商人从首都出发,其他各城镇之间都有道路连接,任意两个城镇之间如果有直连道路,在他们之间行驶需要花费单位时间。该国公路网络发达,从首都出发能到达任意一个城镇,并且公路网络不会存在环。

你的任务是帮助该商人计算一下他的最短旅行时间。

 

Input Description

输入文件中的第一行有一个整数N,1<=n<=30 000,为城镇的数目。下面N-1行,每行由两个整数a 和b (1<=a, b<=n; a<>b)组成,表示城镇a和城镇b有公路连接。在第N+1行为一个整数M,下面的M行,每行有该商人需要顺次经过的各城镇编号。

 

Output Description

在输出文件中输出该商人旅行的最短时间。

 

Sample Input

5
1 2
1 5
3 5
4 5
4
1
3
2
5

 

Sample Output

7

 

思路

所有的道路都是双向的,并且没有环,因此我们可以根据边来建树。

如下图(样例):

img

依次经过 1 33 22 5 这几条路径,从图中我们可以发现,路径的长度刚好等于两端点与其最近公共祖先的深度差之和。

于是:

1->3: $dep[1]+dep[3]-2×dep[1]=1+3-2=2$

3->2: $dep[2]+dep[3]-2×dep[1]=2+3-2=3$

2->5: $dep[2]+dep[5]-2×dep[1]=2+2-2=2$

 

然后题目便转化为基础的 LCA 问题咯~

 

AC 代码

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;

const int maxn=31000;
int fa[maxn];
int rank[maxn];
bool visit[maxn];
vector<int> tree[maxn],Qes[maxn];
int ancestor[maxn];
int ans;
int dep[maxn];

void init(int n)
{
    memset(rank,0,sizeof(rank));
    memset(visit,false,sizeof(visit));
    memset(ancestor,0,sizeof(ancestor));
    memset(dep,0,sizeof(dep));
    ans=0;
    for(int i=1; i<=n; i++)
    {
        fa[i]=i;
        tree[i].clear();
        Qes[i].clear();
    }
}

int find_set(int x)     //并查集 查询+路径压缩
{
    if(x!=fa[x])
        fa[x]=find_set(fa[x]);
    return fa[x];
}

void union_set(int x,int y)     //并查集 合并
{
    x=find_set(x);
    y=find_set(y);
    if(rank[x]>rank[y])
        fa[y]=x;
    else
    {
        fa[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}


void LCA(int u,int pa,int deep)
{
    ancestor[u]=u;
    dep[u]=deep;
    int len = tree[u].size();
    for(int i=0; i<len; i++)
    {
        if(tree[u][i]==pa)continue;
        LCA(tree[u][i],u,deep+1);
        union_set(u,tree[u][i]);
        ancestor[find_set(u)]=u;
    }
    visit[u]=true;
    len = Qes[u].size();
    for(int i=0; i<len; i++)
    {
        if(visit[Qes[u][i]])
            ans+=dep[u]+dep[Qes[u][i]]-2*dep[ancestor[find_set(Qes[u][i])]];
    }
}

int data[maxn];
int main()
{
    int n,m;
    while(~scanf("%d",&n))
    {
        init(n);
        for(int i=0; i<n-1; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        scanf("%d",&m);
        for(int i=0; i<m; i++)
        {
            scanf("%d",data+i);
            if(i)
            {
                Qes[data[i]].push_back(data[i-1]);
                Qes[data[i-1]].push_back(data[i]);
            }
        }
        LCA(1,0,1);
        printf("%d\n",ans);
    }
    return 0;
}