有巨佬能看看这个lca求最小距离哪里错了吗

Question

#include<bits/stdc++.h>
//#define int unsigned long long
#define long long int 
//const int mod=1000000007;
const int mn=100005;
using namespace std;
int anc[mn],n,m,ans,dep[mn];
bool vis[mn];
vector<int> q[mn],a[mn];

int dfs(int u,int fa,int d){
 dep[u]=d;
 for(int i=0;i<a[u].size();i++){
     int v=a[u][i];
     if(v==fa) continue;
     dfs(v,u,d+1);
 }    
 return 0;
}

int find(int x){
    
    if(x==anc[x]) return x;
    anc[x]=find(anc[x]);
    
    return anc[x];
    
}

void lca(int u,int fa){
    for(int i=0;i<a[u].size();i++){
    if(a[u][i]==fa) continue;
    lca(a[u][i],u);    
    }
                
    for(int i=0;i<q[u].size();i++){
        int e=q[u][i];
        if(vis[e]) {
        int r=find(e);
        cout<<dep[e]+dep[u]-2*dep[r]<<'\n';    
        }
    }
    
    anc[u]=find(fa);
    vis[u]=true;
}
                                                                
int main()
{
  cin>>n;
 for(int i=1;i<=n;i++) 
 anc[i]=i;
    
   for(int i=1;i<n;i++) {
      int u,v; 
    cin>>v>>u;
      a[v].push_back(u);
      a[u].push_back(v);
  }
  cin>>m;
  for(int i=1;i<=m;i++) { 
      int u,v; 
    cin>>v>>u;
    q[u].push_back(v);
      q[v].push_back(u);
      
  }
   dfs(1,1,1);
   lca(1,1); 
    return 0;

}

```c++

```

Answer 1

在你的代码中，似乎缺少了对树上两个节点的 LCA（最近公共祖先）的求解。在 lca 函数中，你只是递归地遍历了每个节点，并标记了它们为已访问，但是没有进行 LCA 的求解。

为了解决这个问题，你需要修改 lca 函数，使其能够正确地求解每个查询的 LCA 并计算最短距离。以下是修改后的代码：

void lca(int u, int fa) {
    anc[u] = u; // 初始化每个节点的祖先为自己
    for (int i = 0; i < a[u].size(); i++) {
        int v = a[u][i];
        if (v == fa) continue;
        lca(v, u);
        anc[v] = u; // 更新 v 的祖先为 u
    }
    vis[u] = true; // 标记节点 u 为已访问
    for (int i = 0; i < q[u].size(); i++) {
        int v = q[u][i];
        if (vis[v]) {
            int r = find(v); // 求解 v 和 u 的 LCA
            cout << dep[v] + dep[u] - 2 * dep[r] << '\n'; // 计算最短距离
        }
    }
}

在 lca 函数中，我们对每个节点的祖先进行了初始化，并在递归中更新了每个节点的子孙的祖先。在处理完每个节点的子节点后，我们标记了该节点为已访问，并对其所有查询进行处理。对于每个查询 (u, v)，如果节点 v 已被访问，则通过 find(v) 求解 v 和 u 的 LCA，并使用 LCA 计算 u 和 v 的最短距离。