题解：P14653 [集训队互测 2025] 你的互相追逐的头

Priestess_SLG · 2026-11-10 21:02:53 · 题解

可能是对官方题解的复述。

求出所有初始有人的点组成的虚树，记其任意直径端点为 p_1,p_2，距离为 d=\operatorname{dist}(p_1,p_2)，直径中点为 c（这个点可能在某条边的中间），则因为虚树上任意点到 c 的距离都不超过 \frac d2 因此考虑某个时刻距离 c 最远的人 A，若其在追逐人 B 则因为 A 是最远的人 B 不可能在 A 的更外侧，而在树上 A 走向任何不在更外侧的位置只能走向虚树上和她唯一相邻的结点，该结点必然朝向 c，同理可得操作一轮后所有叶子结点上都没有实体了，扒一层叶子即可。然后这个东西可以递归执行，如果几个人恰好重合则其必然一起追逐下一个不在同一个位置的人因此结论仍然成立。同样容易得出恰好从时刻 \frac d2 开始所有人都一起位于 c 点不再继续移动。

进一步观察后可以发现每个人在追上后继结点前必然走的是树上的一段连续简单路径，追上之后就继续沿着后继的轨迹移动。考虑维护 tim_i 表示第 i 个人追上后继的时刻以及 pos_i 表示两个人第一次相遇时处于的位置。这个东西考虑倒着递推，设已经求出了 i+1 个人的完整轨迹要求第 i 个人的轨迹，维护一个单调栈存储后继的分段轨迹，每段记录起点信息 (A,a) 和终点信息 (B,b)，信息分别表示所在的位置和时刻。若 \operatorname{dist}(x_i,B)>b 则说明直到后继走到 B 重合第 i 个人仍然没法追上后继，因此这段轨迹可以直接弹出单调栈，否则两个人就会在这段路径上相遇，相遇时刻显然是 tim_i=\frac{\operatorname{dist}(x_i,A)+a}2，相遇位置 pos_i 就是路径中点，然后把当前的轨迹入栈即可。

询问判掉 t\ge\frac d2 的 corner case，然后考虑从 p 开始找到后面第一个满足 tim_q>t 的人 q，此时第 p 个人已经追上了第 q 个人，在第 q 个人追后继的简单路径上根据时间倍增求出其当前时刻所在的点即可。

实现上为了方便处理路径中点的情况把一条边 u\to v 拆成两条边 u\to tmp\to v 即可。代码细节不咋多。

namespace lowspeed_song {

mt19937_64 mt(time(0));

inline void init() {
}

pair<int, int> e[N];
vector<int> adj[N];

int dep[N], st[N][20];

inline void dfs(int u, int fa) {
    st[u][0] = fa, dep[u] = dep[fa] + 1;
    for (int &v : adj[u]) if (v != fa) dfs(v, u);
}

inline int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (int i = 19; ~i; --i) if (dep[a] - dep[b] >> i & 1) a = st[a][i];
    if (a == b) return a;
    for (int i = 19; ~i; --i) if (st[a][i] != st[b][i]) a = st[a][i], b = st[b][i];
    return st[a][0];
}

inline int dist(int a, int b) {
    return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}

inline int kth(int x, int k) {
    for (int i = 19; ~i; --i) if (k >> i & 1) x = st[x][i];
    return x;
}

inline int get(int u, int v, int dist) {
    int LCA = lca(u, v);
    if (dist <= dep[u] - dep[LCA]) return kth(u, dist);
    return kth(v, dep[u] + dep[v] - 2 * dep[LCA] - dist);
}

int st_ne[N][20], st_mx[N][20];

inline void sol([[maybe_unused]]int __testcase_id, [[maybe_unused]]int __testcase_sum) {
    int n, m; cin >> n >> m;
    for (int i = 1; i < n; ++i) {
        int a, b; cin >> a >> b;
        if (a > b) swap(a, b);
        e[i] = {a, b};
        adj[a].emplace_back(i + n);
        adj[i + n].emplace_back(a);
        adj[b].emplace_back(i + n);
        adj[i + n].emplace_back(b);
    } dfs(1, 0);
    for (int i = 1; i < 20; ++i)
        for (int j = 1; j <= n + n; ++j) st[j][i] = st[st[j][i - 1]][i - 1];
    while (m--) {
        int k, q; cin >> k >> q;
        vector<int> x(k), tim(k, 0), pos(k, 0);
        for (int &i : x) cin >> i;
        int a = 0, mx = 0;
        for (int i = 0; i < k; ++i) {
            int d = dist(x[0], x[i]);
            if (mx < d) mx = d, a = i;
        } int b = a; mx = 0;
        for (int i = 0; i < k; ++i) {
            int d = dist(x[a], x[i]);
            if (mx < d) mx = d, b = i;
        } int half = dist(x[a], x[b]) / 2;
        int center = get(x[a], x[b], half);
        tim[a] = half, pos[a] = center;
        vector<pair<int, int>> stk = {
            {center, half}, 
            {x[a], 0}
        };
        for (int o = 1; o < k; ++o) {
            int i = (a - o + k) % k;
            while (1) {
                auto [A, timA] = stk.back();
                auto [B, timB] = stk[stk.size() - 2];
                if (dist(x[i], B) > timB) stk.pop_back();
                else {
                    tim[i] = (timA + dist(x[i], A)) / 2, pos[i] = get(A, B, tim[i] - timA);
                    stk.back() = {pos[i], tim[i]}, stk.emplace_back(x[i], 0);
                    break;
                }
            }
        } for (int i = 0; i < k; ++i) {
            st_mx[i][0] = tim[i];
            st_ne[i][0] = (i + 1) % k;
        } for (int i = 1; i < 20; ++i)
            for (int j = 0; j < k; ++j) {
                st_ne[j][i] = st_ne[st_ne[j][i - 1]][i - 1];
                st_mx[j][i] = max(st_mx[j][i - 1], st_mx[st_ne[j][i - 1]][i - 1]);
            }
        while (q--) {
            int p, t; cin >> p >> t;
            if (2 * t >= half) {
                if (center <= n) cout << center << ' ' << center << '\n';
                else {
                    auto [u, v] = e[center - n];
                    cout << u << ' ' << v << '\n';
                }
            } else {
                --p;
                for (int j = 19; ~j; --j)
                    if (st_mx[p][j] <= 2 * t) p = st_ne[p][j];
                int id = get(x[p], pos[p], 2 * t);
                if (id <= n) cout << id << ' ' << id << '\n';
                else {
                    auto [u, v] = e[id - n];
                    cout << u << ' ' << v << '\n';
                }
            }
        }
    }
}

} // namespace lowspeed_song