题目链接：

题意：

给定一棵树，求两个点之间的距离。

分析：

LCA 的模板题目 ans = dis[u]+dis[v] - 2*dis[lca(u,v)];

在线算法：详细解说

代码例如以下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         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<
         
          <=n;i++){        for(int j=1;j+(1<
          
           <=n;j++){ int a = dp[j][i-1],b=dp[j+(1<<(i-1))][i-1]; if(R[a]
           
            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
           
          
         
        
       
      
     

离线算法： 详细解说

代码例如以下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         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