【每日一题】倍增专题 紧急集合题解

Description

给出一棵树，每次查询给三个点，找到一个集合点，使得三个点到它的距离和最小。

Solution

做法是求LCA(最近公共祖先)

给出样例的图，查询情况如下：
4 5 6，显然集合点走5这个点最优，总花费为2
6 3 1，显然集合点走2这个点最优，总花费为5
2 4 4，显然集合点走4这个点最优，总花费为1
6 6 6，显然集合点走6这个点最优，总花费为0

可以看到，给出 最终选择的最优集合点只能会是 ，此时只需要找三个点哪个最优即可。
实际上，至少会有两组点对他们的 是一样的，如果出现这种情况，只需要把集合点定为第三个LCA点。如下图，选择LCA1是最优的。

所以主要问题就是如何求 ， 这里我用倍增法求 , 时间复杂度

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
typedef long long ll;
vector<int> G[N];
int a[N], dep[N];
bool vis[N]; 
int fa[N][32];
void bfs(int root) {
  queue<int> q;
  q.push(root);
  vis[root] = 1;
  dep[root] = 0, fa[root][0] = root;
  while(!q.empty()) {
    int u = q.front(); q.pop();
    for(int i = 1; i < 31; i++) {
      fa[u][i] = fa[fa[u][i - 1]][i - 1];
    } 
    for(auto &x : G[u]) {
      if(!vis[x]) {
        vis[x] = 1;
        dep[x] = dep[u] + 1;
        fa[x][0] = u;
        //cout << fa[x][0] << endl;
        //cout << x << "fa:" << u << ' ' << fa[x][0] << endl; 
        q.push(x);
      }
    }
  }
}
int LCA(int u, int v) {
  if(dep[u] > dep[v]) swap(u, v);
  int hu = dep[u], hv = dep[v];
  int tu = u, tv = v;
  for(int det = hv - hu, i = 0; det; det >>= 1, i++) {
    if(det & 1) {
      tv = fa[tv][i];
    }
  }
  if(tu == tv) return tu;
  for(int i = 30; i >= 0; --i) {
    if(fa[tu][i] == fa[tv][i]) continue;
    tu = fa[tu][i];
    tv = fa[tv][i];
  }
  return fa[tu][0];
}
int cal(int x, int y) {
  int anc = LCA(x, y);
  return dep[x] + dep[y] - 2 * dep[anc];
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n, m; cin >> n >> m;
  for(int i = 1; i <= n - 1; i++) {
    int u, v; cin >> u >> v;
    G[u].push_back(v), G[v].push_back(u); 
  }
  bfs(1);
  while(m--) {
    int u, v, w; cin >> u >> v >> w;
    int anc1 = LCA(u, v), anc2 = LCA(v, w), anc3 = LCA(u, w);
    if(anc1 == anc2) {
      //cout << 1 << ' ' << anc1 << ' ';
      cout << anc3 << ' ' << cal(u, anc3) + cal(v, anc3) + cal(w, anc3) << '\n';
    } else if(anc1 == anc3) {
      //cout << 2 << ' ' << anc1 << ' ';
      cout << anc2 << ' ' << cal(u, anc2) + cal(v, anc2) + cal(w, anc2) << '\n';
    } else {
      //cout << 3 << ' ' << anc3 << ' ';
      cout << anc1 << ' ' << cal(u, anc1) + cal(v, anc1) + cal(w, anc1) << '\n';
    }
  }
  return 0;
}