链接:http://wikioi.com/problem/1036/
题意不写了。
思路:很明显找到lca然后用两个点的深度相加-lca的深度就是这一步的最近步数。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <queue>
#define loop(s,i,n) for(i = s;i < n;i++)
#define cl(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn = ;
int low[maxn],dfn[maxn],set[maxn],father[maxn],dfsclock,cut;
int depth[maxn]; vector<int >g[maxn];
int find(int x)
{
if(set[x] != x)
set[x] = find(set[x]); return set[x];
}
int merge(int x,int y)
{
x = find(x);
y = find(y);
if(y != x)
{
set[y] = x;
return ;
}
return ;
}
void tarjan(int u,int pre,int deep)
{
int v,i,j;
dfn[u] = low[u] = ++dfsclock;
depth[u] = deep;
loop(,i,g[u].size())
{
v = g[u][i];
if(!dfn[v])
{
tarjan(v,u,deep+);
father[v] = u;
low[u] = min(low[v],low[u]);
if(low[v] > dfn[u])
cut++;
else
merge(u,v);
}
else if(v != pre)
low[u] = min(low[u],dfn[v]);
}
}
int lca(int u,int v)
{ while(u != v)
{
while(dfn[u] >= dfn[v] && u != v)
{
if(merge(u,father[u]))
cut--;
u = father[u];
}
while(dfn[v] >= dfn[u] && u != v)
{
if(merge(v,father[v]))
cut--;
v = father[v];
}
}
return u;
}
int main()
{
int n,m;
int i,x,y;
scanf("%d",&n);
{
int u,v;
loop(,i,n+)
{
g[i].clear();
set[i] = i;
father[i] = ;
}
loop(,i,n)
{
scanf("%d %d",&u,&v);
g[u].push_back(v);
g[v].push_back(u); }
cl(dfn,);
cl(low,);
cut = dfsclock = ; int k;
scanf("%d",&k);
tarjan(,-,);
u = ;
int ans;
ans = ;
while(k--)
{
scanf("%d",&v);
int f;
f = lca(u,v);
ans += depth[u]+depth[v]-*depth[f];
u = v;
}
cout<<ans<<endl;
}
return ;
}