How far away ？ HDU - 2586
程序员文章站
2022-03-23 13:58:51
...
理解这个算法一定要抓住`递推`的思想(也有递归在里面, 也要抓住).
Tarjan是利用并查集实现的, 在递推过程中, 一棵树的root节点代表这棵树(联系并查集来想), 这样做的好处是, 如果问点i与j的lca, 我们只要找i,j都属于的最小的哪棵子树就行了, 因为该子树就是我们的答案. 那如何确定是那颗子树呢? 这一点后面再解释一下.
下面说Tarjan最巧妙的点了. 因为是在建树的过程中计算所有query, 也就表示我们此刻是否能计算某一query对(u,v)的条件是 : u和v是否都已经遍历过. 所以我们可以在遍历到点v(假设经历v的时间比u晚)的时候把query给计算出来. 比如lcm(u,v)就是find(u). 那此刻的find(v)和lcm(u,v)相不相等呢? 答案是不相等, 至少在我的代码实现上不相等. 因为father[x]的更新是在`递归回去`的时候更新的, 而此刻在遍历v点, 还没递归回去呢, father[v]当然也就没更新啦.点击打开链接 3
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=40010;
struct node
{
int from,to,weight,lca,next;
}edge[maxn*2],qedge[maxn];
int first[maxn],qfirst[maxn],index,index1;
int m,n;
int father[maxn],vis[maxn],dist[maxn],res[maxn][3];
void init()
{
memset(vis,0,sizeof(vis));
memset(dist,0,sizeof(dist));
memset(first,0,sizeof(first));
memset(qfirst,0,sizeof(qfirst));
index=index1=1;
}
void add(int u,int v,int w)
{
edge[index].to=v;
edge[index].weight=w;
edge[index].next=first[u];
first[u]=index++;
}
void qadd(int u,int v,int w)
{
qedge[index1].to=v;
qedge[index1].weight=w;
qedge[index1].next=qfirst[u];
qfirst[u]=index1++;
}
int Find(int x)
{
// if(father[x]==x)
// return x;
// return father[x]=Find(father[x]);
int root=x;
while(root!=father[root])
root=father[root];
int j;
while(root!=father[x])
{
j=father[x];
father[x]=root;
x=j;
}
return root;
}
void tarjan(int u)
{
vis[u]=1;
father[u]=u;
for(int i=first[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(!vis[v])
{
dist[v]=dist[u]+edge[i].weight;
tarjan(v);
//Union(u,v);
father[v]=u;
// cout<<v<<"father :"<<father[u]<<endl;
}
}
for(int i=qfirst[u];i;i=qedge[i].next)
{
int v=qedge[i].to;
if(vis[v])
{
res[qedge[i].weight][2]=Find(v);//最近的公共祖先
// cout<<res[i][0]<<" and "<<res[i][1]<<" lca :"<<res[i][2]<<endl;
}
}
}
int main()
{
int T;
int u,v,w;
scanf("%d",&T);
while(T--)
{
init();
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
for(int i=0;i<m;i++)
{
scanf("%d%d",&u,&v);
qadd(u,v,i);
qadd(v,u,i);
res[i][0]=u;
res[i][1]=v;
}
dist[1]=0;
tarjan(1);
for(int i=0;i<m;++i)
{
//cout<<res[i][2]<<" ";
printf("%d\n",dist[res[i][0]]+dist[res[i][1]]-2*dist[res[i][2]]);
}
}
return 0;
}
/*
1
11 3
1 2 1
1 3 2
2 5 3
3 6 4
5 8 5
5 9 6
6 10 7
6 11 8
2 4 1
3 7 2
8 9
10 11
9 10
*/
wa的一个：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=40010;
struct node
{
int from,to,weight,lca,next;
}edge[maxn*2],qedge[maxn];
int first[maxn],qfirst[maxn],index,index1;
int m,n;
int father[maxn],vis[maxn],dist[maxn];
void init()
{
memset(vis,0,sizeof(vis));
memset(dist,0,sizeof(dist));
memset(first,-1,sizeof(first));
memset(qfirst,-1,sizeof(qfirst));
index=index1=0;
}
void add(int u,int v,int w)
{
edge[index].to=v;
edge[index].weight=w;
edge[index].next=first[u];
first[u]=index++;
}
void qadd(int u,int v)
{
qedge[index1].from=u;
qedge[index1].to=v;
qedge[index1].lca=-1;
qedge[index1].next=qfirst[u];
qfirst[u]=index1++;
}
int Find(int x)
{
if(father[x]==x)
return x;
return father[x]=Find(father[x]);
}
void Union(int x,int y)
{
x=Find(x);
y=Find(y);
if(x!=y)
father[y]=x;
}
void tarjan(int u)
{
vis[u]=1;
father[u]=u;//ance[u]=father[u]=u;
for(int i=first[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(!vis[v])
{
dist[v]=dist[u]+edge[i].weight;
tarjan(v);
//Union(u,v);
father[v]=u;
}
}
for(int i=qfirst[u];i!=-1;i=qedge[i].next)
{
int v=qedge[i].to;
if(vis[v])
{
if(v%2)
{
qedge[i+1].lca=qedge[i].lca=Find(v);
}
else
qedge[i].lca=qedge[i-1].lca=Find(v);//ance[Find(v)];
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
init();
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
for(int i=0;i<m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
qadd(u,v);
qadd(v,u);
}
dist[1]=0;
tarjan(1);
for(int i=0;i<m;++i)
{
int j=i*2;
int u=qedge[j].from;
int v=qedge[j].to;
int lca=qedge[j].lca;
printf("%d\n",dist[u]+dist[v]-2*dist[lca]);
}
}
return 0;
}