60分求调
查看原帖
60分求调
588080
n_bluetea楼主2024/6/27 21:36
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int maxn = 1e6 + 10;
const int inf = LLONG_MAX;

struct edge {
    int to, next;
} e[maxn * 2];

int cnt = 1;
int head[maxn];
void add(int u, int v) {
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

int dist[maxn];
int deep[maxn];
int ance[maxn][21]; 

void dfs(int now, int fa) {
    deep[now] = deep[fa] + 1;
    ance[now][0] = fa;

   
    for (int i = 1; i <= 20; i++) {
        ance[now][i] = ance[ance[now][i - 1]][i - 1];
    }

    for (int i = head[now]; i; i = e[i].next) {
        int tx = e[i].to;
        if (tx == fa) continue;
        dfs(tx, now);
    }
}

int lca(int u, int v) {
    if (deep[u] < deep[v])
        swap(u, v);

    int p = deep[u] - deep[v];
    for (int i = 20; i >= 0; i--) {
        if (p>>i & 1) {
            u = ance[u][i];
        }
    }

    if (u == v) return u;

    for (int i = 20; i >= 0; i--) {
        if (ance[u][i] != ance[v][i]) {
            u = ance[u][i];
            v = ance[v][i];
        }
    }
    return ance[u][0];
}

int dis(int u, int v) {
    return deep[u] + deep[v] - 2 * deep[lca(u, v)];
}

void run() {
    int n, k, m;
    cin >> n >> k >> m;

    cnt = 1;
    memset(head, 0, sizeof(head));
    memset(dist, 0x3f, sizeof(dist));

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }

    queue<int> q;
    for (int i = 1; i <= k; i++) {
        int u;
        cin >> u;
        q.push(u);
        dist[u] = 0;
    }

    while (!q.empty()) {
        int now = q.front();
        q.pop();

        for (int i = head[now]; i; i = e[i].next) {
            int tx = e[i].to;
            if (dist[tx] == inf) {
                dist[tx] = dist[now] + 1;
                q.push(tx);
            }
        }
    }

    dfs(1, 0);

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        cout << min(dis(u, v), dist[u] + dist[v]) << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) {
        run();
    }
    return 0;
}

2024/6/27 21:36
加载中...