DDOSvoid's Blog

Luogu T197745 病毒

发表于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/T197745

简要题意：给定一棵 $n$ 个点的树，现在有 $m$ 次询问，每次询问给定 $k$ 个点，求是否存在一个到这 $k$ 点的距离相等的点，如果有多个点求距离最小的那个

$n\le 10^6,\sum k\le 10^6$

Solution

不妨假设存在这么一个点 $x$ 且距离为 $d$，我们以 $x$ 为根，容易在给定点集中一定有两个点的距离为 $2\times d$

那么我们直接把这个路径中点拿出来判断即可，至于如何求点集中最远点对，显然其中一个点是深度最大的点

时间复杂度 $O(n\log n )$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#define maxn 1000010
using namespace std;

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int dep[maxn], f[maxn][21];
void dfs(int u, int fa) {
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        dep[v] = dep[u] + 1; f[v][0] = u; 
        dfs(v, u); 
    } 
}

void init_lca(int n) {
    for (int j = 1; j <= 20; ++j)
        for (int i = 1; i <= n; ++i) f[i][j] = f[f[i][j - 1]][j - 1]; 
}

int get_lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y); 
    for (int i = 20; ~i; --i)
        if (dep[f[x][i]] >= dep[y]) x = f[x][i];
    if (x == y) return x;
    for (int i = 20; ~i; --i)
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}

inline int D(int x, int y) { return dep[x] + dep[y] - 2 * dep[get_lca(x, y)]; }

int jump(int u, int n) {
    for (int x = 0; n; n >>= 1, ++x)
        if (n & 1) u = f[u][x];
    return u;
}

int n, m, a[maxn];

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x); 
    } dep[1] = 1; dfs(1, 0); init_lca(n); cin >> m;
    while (m--) {
        int k; cin >> k;
        for (int i = 1; i <= k; ++i) cin >> a[i];
        int u = 0, v, dis = 0;
        for (int i = 1; i <= k; ++i)
            if (dep[a[i]] > dep[u]) u = v = a[i];
        for (int i = 1; i <= k; ++i) {
            int tdis = D(u, a[i]); 
            if (tdis > dis) v = a[i], dis = tdis;
        }
        if (dis & 1) { cout << -1 << "\n"; continue; }
        u = jump(u, dis / 2); bool ok = 1;
        for (int i = 1; i <= k; ++i)
            if (D(u, a[i]) != dis / 2) {
                ok = 0; cout << -1 << "\n";
                break;
            }
        if (ok) cout << u << " " << dis / 2 << "\n";
    }
    return 0; 
}