题目链接：传送门
题意：
给定一棵树，，求两个点之间的距离。
分析：
LCA 的模板题目 ans = dis[u]+dis[v] – 2*dis[lca(u,v)];
在线算法：具体讲解 传送门
代码如下：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 40010;struct nod{int to,next,w;}edge[maxn*2];int head[maxn],ip,tot;bool vis[maxn];int R[maxn*2],ver[maxn*2];int dp[maxn*2][25];int first[maxn];int dis[maxn];void init(){memset(head,-1,sizeof(head));memset(vis,false,sizeof(vis));dis[1]=0,ip=0,tot=0;}void add(int u,int v,int w){edge[ip].to=v;edge[ip].w=w;edge[ip].next=head[u];head[u]=ip++;}/***ver[i]=x:第i个点是x.first[i]=x: 点i第一次出现的位置是xR[i]=x：第i个点的深度为x;dis[i]=x;点i到根节点的距离为x.***/void dfs(int u,int dept){vis[u]=true,ver[++tot]=u,first[u]=tot,R[tot]=dept;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(!vis[v]){dis[v]=dis[u]+edge[i].w;dfs(v,dept+1);ver[++tot]=u,R[tot]=dept;}}}void ST(int n){for(int i=1;i<=n;i++) dp[i][0]=i;for(int i=1;(1<<i)<=n;i++){for(int j=1;j+(1<<i)<=n;j++){int a = dp[j][i-1],b=dp[j+(1<<(i-1))][i-1];if(R[a]<R[b]) dp[j][i]=a;else dp[j][i]=b;}}}int RMQ(int l,int r){int k=0;while(1<<(k+1)<=r-l+1)k++;int x = dp[l][k], y=dp[r-(1<<k)+1][k];if(R[x]<R[y]) return x;else return y;}int LCA(int u,int v){u=first[u],v=first[v];if(u>v) swap(u,v);return ver[RMQ(u,v)];}int main(){int t,n,m;scanf("%d",&t);while(t–){scanf("%d%d",&n,&m);init();for(int i=0;i<n-1;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);}dfs(1,1);ST(2*n-1);for(int i=0;i<m;i++){int u,v;scanf("%d%d",&u,&v);printf("%d\n",dis[u]+dis[v]-2*dis[LCA(u,v)]);}}return 0;}
离线算法： 具体讲解 传送门
代码如下：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 40010;struct nod{int u,v,next,w,lca;}edge[maxn*2],edge1[maxn];int par[maxn],ancestors[maxn];int head[maxn],head1[maxn];int dis[maxn],ip,ip1;bool vis[maxn];void init(){memset(head1,-1,sizeof(head1));memset(head,-1,sizeof(head));memset(vis,false,sizeof(vis));for(int i=1;i<maxn;i++) par[i]=i;dis[1]=0,ip1=0,ip=0;}int find_par(int x){if(x!=par[x]) return par[x]=find_par(par[x]);return par[x];}void Union(int u,int v){u=find_par(u);v=find_par(v);if(u!=v) par[v]=u;}void add(int u,int v,int w){edge[ip].v=v;edge[ip].w=w;edge[ip].next=head[u];head[u]=ip++;}void add1(int u,int v){edge1[ip1].u=u;edge1[ip1].v=v;edge1[ip1].lca=-1;edge1[ip1].next=head1[u];head1[u]=ip1++;}void tarjan(int u){vis[u]=1;ancestors[u]=par[u]=u;for(int i=head[u];i!=-1;i=edge[i].next){int v = edge[i].v;if(!vis[v]){dis[v]=dis[u]+edge[i].w;tarjan(v);Union(u,v);}}for(int i=head1[u];i!=-1;i=edge1[i].next){int v = edge1[i].v;if(vis[v]){edge1[i].lca=edge1[i^1].lca=ancestors[find_par(v)];}}}int main(){int t,n,m;scanf("%d",&t);while(t–){scanf("%d%d",&n,&m);init();for(int i=0;i<n-1;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);add1(u,v);add1(v,u);}tarjan(1);for(int i=0;i<m;i++){printf("%d\n",dis[edge1[i*2].u]+dis[edge1[i*2].v]-2*dis[edge1[i*2].lca]);}}return 0;}
联系朋友别欠费，天空辽阔任你飞，再多困难别后退! “
