8.18每日一题-[NC14250]MMSet2

题意简述：

有一个 $n$ 个节点的树，点编号为 $1\sim n$ 。
有 $Q$ 次询问。每次询问给出一个子集 $S$ ，令 $f(u)=\max_{v\in S}\operatorname{dist}(u,v)$ 。
其中 $\operatorname{dist}(u,v)$ 表示点 $u$ 与点 $v$ 的距离。
求 $\min_{u=1\cdots n}f(u)$ 。

做法简述

因为 $f(u)=\max_{v\in S}\operatorname{dist}(u,v)$ ，
所以 $\min_{u=1\cdots n}f(u)=\min_{u=1\cdots n}\max_{v\in S}\operatorname{dist}(u,v)$ 。
暴力求的话，复杂度是平方的。
我们需要优化。
从等式的右边的意思出发。
我们需要求的就是某个点 $u$ ，它到点集中所有点的最大距离最小。
因为要求最小，所以这个 $u$ 点必须也要在点集 $S$ 中。
所以我们可以换个角度考虑。既然 $u,v$ 都在点集 $S$ 中了，我们可以直接求 $S$ 的直径即可，所以 $v$ 点的深度要尽可能地大。
求法不再赘述（前人之述备矣），代码里会有一些注释。
时间复杂度 $O(q|S|\log n)$ ，可以通过。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxN = 300005;
struct Edge {
    int to, nxt;
} edge[maxN << 1];
int fa[maxN][20], dep[maxN], hd[maxN], n, tot;
void rd(int&), dfs(int, int), add(int, int);
int LCA(int, int), dis(int, int);
int main() {
    rd(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        rd(u);
        rd(v);
        add(u, v);
        add(v, u);
    }
    dfs(1, 1); // 先 dfs 预处理 fa 和 dep
    int q;
    rd(q);
    while (q--) {
        int S;
        rd(S);
        vector<int> ver(S + 1); // 点集
        int id = 0, max_dep = 1, ans = 0;
        for (int i = 1; i <= S; i++) {
            rd(ver[i]);
            if (dep[ver[i]] > max_dep) {
                max_dep = dep[ver[i]];
                id = ver[i];
            }
        // 找出点集中深度最大的点
        }
        // id 即是题解中的 v 点
        for (int i = 1; i <= S; i++) {
            if (id == ver[i]) {
                continue;
            }
            int d = dis(id, ver[i]);
            ans = max(ans, d);
        // 计算树的直径
        }
        printf("%d\n", (ans + 1) / 2);
    }
}
void dfs(int u, int d) {
    dep[u] = d;
    for (int i = hd[u]; i; i = edge[i].nxt) {
        int o = edge[i].to;
        if (dep[o]) {
            continue;
        }
        fa[o][0] = u;
        for (int j = 1; fa[o][j - 1]; j++) {
            fa[o][j] = fa[fa[o][j - 1]][j - 1];
        }
        dfs(o, d + 1);
    }
}
int LCA(int u, int v) { // 经典倍增 LCA 求法
    if (dep[u] < dep[v]) {
        swap(u, v);
    }
    // 先强制使 u 点的深度比 v 点大
    for (int i = 19; i >= 0; i--) {
        if (dep[u] - (1 << i) >= dep[v]) {
            u = fa[u][i];
        }
    }
    // 用倍增思想让 u 点往上跳
    if (u == v) {
        return u;
    }
    for (int i = 19; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    // 然后 u 和 v 一起往上跳
    return fa[u][0];
}
int dis(int u, int v) { // 计算 u 点与 v 点之间的距离
    return dep[u] + dep[v] - 2 * dep[LCA(u, v)];
}
void add(int x, int y) {
    edge[++tot].to = y;
    edge[tot].nxt = hd[x];
    hd[x] = tot;
}
void rd(int& x) {
    x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
}