【每日一题】MMSet2 题解

Description

Solution

可以把题目转化成求 1-n 里到点集S的最远距离最小的结果，而这个点应该出现在点集S中离得最远的两个点连线的中点上。
而点集S的最远距离就是求直径，直接dfs的复杂度是 的，但是我们可以通过处理出LCA，先找到深度最大的点作为直径的一端，另一端通过枚举得到。设直径的长度为 ,最终结果就是ceil().

Code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int mod = 1e9 + 7; 
const int N = 5e5 + 5;
struct node {
  int to, nextz;
}edge[N << 1];
int tot, head[N];
void addedge(int u, int v) {
  edge[tot].to = v;
  edge[tot].nextz = head[u];
  head[u] = tot++;
}
void init() {
  memset(head, -1, sizeof(head));
  tot = 0;
}
int fa[N][40];
int deg[N];
void bfs(int root) {
  fa[root][0] = root;
  deg[root] = 0;
  queue<int> q; q.push(root);
  while(!q.empty()) {
    int tmp = q.front(); q.pop();
    for(int i = 1; i < 35; i++) {
      fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1];
    }
    for(int i = head[tmp]; ~i; i = edge[i].nextz) {
      int v = edge[i].to;
      if(v == fa[tmp][0]) continue;
      q.push(v); deg[v] = deg[tmp] + 1; fa[v][0] = tmp;
    }
  }
}
int LCA(int u, int v) {
  if(deg[u] > deg[v]) swap(u, v);
  int hu = deg[u], hv = deg[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 = 34; 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) {
  return deg[x] + deg[y] - 2 * deg[LCA(x, y)];
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  init();
  int n, m; cin >> n;
  for(int i = 1; i <= n - 1; i++) {
    int x, y; cin >> x >> y; addedge(x, y); addedge(y, x);
  }
  bfs(1);
  cin >> m;
  while(m--) {
    vector<int> v;
    int num, x; cin >> num;
    int maxz = 0, u = 0;
    for(int i = 1; i <= num; i++) {
      cin >> x, v.push_back(x);
      //cout << x << ' ' << deg[x] << "\n";
      if(deg[x] > maxz) {
        maxz = deg[x];
        u = x;
      }
    }
    maxz = 0;
    for(auto x : v) {
      maxz = max(maxz, cal(u, x));
    }
    cout << (maxz + 1) / 2 << "\n";
  }
  return 0;
}