30pts 求调
查看原帖
30pts 求调
1476569
L0_0楼主2025/6/23 21:14
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+1, K = 18;
int n, k, Q, fa[N][K], dep[N], d[N];
vector<int> e[N];
queue<int> q;
bool vis[N];
void dfs(int x){
    vis[x] = 1;
    for(auto y:e[x]){
        if (vis[y]) continue;
        fa[y][0] = x;
        dep[y] = dep[x] + 1;
        dfs(y);
    }
}
int lca(int x, int y){
    if (dep[x] < dep[y]) swap(x, y);
    int k = dep[x] - dep[y], i = 0;
    while(k){
        if (k&1) x = fa[x][i];
        i++; k>>=1;
    }
    if (x==y) return x;
    for(int i=K-1;i>=0;i--)
        if (fa[x][i] != fa[y][i])
            {x = fa[x][i];y = fa[y][i];}
    return fa[x][0];
}

int main(){
    cin>>n>>k>>Q;
    for(int i=1;i<n;i++){
        int u, v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1);
    for(int j=1;j<K;j++)
        for(int i=1;i<=n;i++)
            fa[i][j] = fa[fa[i][j-1]][j-1];
    memset(d, 0x3f, sizeof d);
    for(int i=1;i<=k;i++){
        int b;
        cin>>b;
        d[b] = 0;
        q.push(b);
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for (auto v:e[u])
            if (d[v] > d[u] + 1){
                d[v] = d[u] + 1;
                q.push(v);
            }
    }
    while(Q--){
        int u, v;
        cin>>u>>v;
        int ans = d[u] + d[v];
        int lc = lca(u, v);
        ans = min(ans, dep[u] + dep[v] - dep[lc]);
        cout << ans << endl;
    }
}

分数:3030

2025/6/23 21:14
加载中...