 | ||||||||||
| ||||||||||
| ***重磅消息——[BestCoder Round #4]冠军将获得iPad Mini一部！ 《BestCoder用户手册》下载 | ||||||||||
How far away ？Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5091 Accepted Submission(s): 1927 Problem Description There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people. Input First line is a single integer T(T<=10), indicating the number of test cases. For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n. Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j. Output For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case. Sample Input |
题意：求两个节点之间的距离，每个节点只能走一次
思路：LCA，求的时候保存下根节点到当前节点的距离，那么两个节点的距离就是dis[u]+dis[v]-2*dis[ance].我们从根开始深搜遍历树，每当回溯到一个节点时，那就意味着我们已经完成了该节点子树的遍历，显然这个节点就是子树中点以及其本身的最近公共祖先，以此类推到整个树。这里非常巧妙的一点是，对于一个点，只有完成了其子树的遍历，我们才改变其 父节点 的值（赋初值为father[ i ] = i），这样，对于每次询问（就是给出两点标号，要求求出两点间最短距离，算一次询问。假设为 A 和 B），我们搜到 A （或B）时，如果 B （或A）已经被访问过，那么向上回溯，直到第一个 父节点 已经改变的点，就是包括点 A 和点 B 在内子树的根，这就是我们要找的 A 和 B 的最近公共祖先。
离线：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=40010;
int n,m;
vector<pair<int,int> > g[maxn];
vector<pair<int,int> > q[maxn];
int pre[maxn],ance[maxn],vis[maxn];
long long dis[maxn],ans[maxn];
int find(int x)
{
if(x==pre[x])return x;
return pre[x]=find(pre[x]);
}
void unite(int a,int b)
{
int x=find(x),y=find(b);
pre[y]=x;
}
void LCA(int u)
{
pre[u]=u;
ance[u]=u;
vis[u]=1;
int len=g[u].size();
for(int i=0;i<len;i++)
{
int v=g[u][i].first;
int w=g[u][i].second;
if(vis[v])continue;
dis[v]=dis[u]+w;
LCA(v);
unite(u,v);
ance[find(v)]=u;
}
len=q[u].size();
for(int i=0;i<len;i++)
{
int v=q[u][i].second;
int x=ance[find(v)];
if(vis[v])
ans[q[u][i].first]=dis[v]+dis[u]-2*dis[x];
}
}
void init()
{
for(int i=0;i<=n;i++)
{
g[i].clear();
q[i].clear();
}
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
init();
for(int i=1;i<n;i++)
{
int a,b,k;
scanf("%d%d%d",&a,&b,&k);
g[a].push_back(make_pair(b,k));
g[b].push_back(make_pair(a,k));
}
for(int i=0;i<m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
q[u].push_back(make_pair(i,v));
q[v].push_back(make_pair(i,u));
}
LCA(1);
for(int i=0;i<m;i++)cout<<ans[i]<<endl;
}
return 0;
}
在线算法：LCA转换成RMQ问题，E记录经过的节点的欧拉序列，dep记录经过的每个节点的深度，pos记录第一次出现的位置。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=80010;
int n,m,num;
int E[maxn],pos[maxn],dep[maxn],d[maxn][30],dis[maxn],vis[maxn];
vector<pair<int,int> >g[maxn];
void init()
{
for(int i=0;i<=n;i++)g[i].clear();
num=0;
memset(pos,-1,sizeof(pos));
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
}
void dfs(int u,int depth)
{
E[++num]=u,dep[num]=depth;
if(pos[u]==-1)pos[u]=num;
vis[u]=1;
int len=g[u].size();
for(int i=0;i<len;i++)
{
int v=g[u][i].first;
int w=g[u][i].second;
if(vis[v])continue;
dis[v]=dis[u]+w;
dfs(v,depth+1);
E[++num]=u;
dep[num]=depth;
}
}
void initRMQ(int len)
{
for(int i=0;i<=len;i++)d[i][0]=i;
for(int j=1;(1<<j)<=len;j++)
for(int i=1;i+(1<<j)<=len;i++)
{
int x=d[i][j-1],y=d[i+(1<<(j-1))][j-1];
if(dep[x]<=dep[y])d[i][j]=x;
else d[i][j]=y;
}
}
int LCA(int x,int y)
{
int a=pos[x],b=pos[y];
if(a>b)swap(a,b);
int k=0;
while((1<<(k+1))<=b-a+1)k++;
int l=d[a][k],r=d[b-(1<<k)+1][k];
if(dep[l]<dep[r])return E[l];
return E[r];
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
init();
for(int i=1;i<n;i++)
{
int u,v,f;
scanf("%d%d%d",&u,&v,&f);
g[u].push_back(make_pair(v,f));
g[v].push_back(make_pair(u,f));
}
dfs(1,1);
initRMQ(num);
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
int fa=LCA(x,y);
printf("%d\n",dis[x]+dis[y]-2*dis[fa]);
}
}
return 0;
}