LCA-RE30玄关求调
查看原帖
LCA-RE30玄关求调
749811
Licis_Subway楼主2024/7/9 12:01
#include<cstdio>
#include<vector>
#include<cmath>//for log2()
#include<queue>
#include<cstring>
using namespace std;
inline int min(const int x,const int y){return x<=y?x:y;}
const int N=2e5+5;
vector<int> G[N];
int fa[N][35],dep[N],transdis[N];
queue<int> Q;
inline int lowbit(const int x){return x&(-x);}
void swap(int &x,int &y){x^=y;y^=x;x^=y;}
void dfs(int u,int f)
{
    fa[u][0]=f;
    dep[u]=dep[f]+1;
    vector<int>::iterator it=G[u].begin();
    for(;it!=G[u].end();it++)
    {
        if(*it==f) continue;
        dfs(*it,u);
    }
    return;
}
void calcfa(int n)
{
    for(int j=1;j<=29;j++)
        for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1];
    return;
}
int LCA(int x,int y,const int n)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=dep[x]-dep[y];i;i-=lowbit(i)) x=fa[x][(unsigned int)log2(lowbit(i))];
    if(x==y) return x;
    for(int i=log2(n);i>=0;i--)
    {
        if(fa[x][i]==fa[y][i]) continue;
        x=fa[x][i];y=fa[y][i];
    }
    return fa[x][0];
}
void trans()
{
    while(!Q.empty())
    {
        int cur=Q.front();
        Q.pop();
        vector<int>::iterator it=G[cur].begin();
        for(;it!=G[cur].end();it++)
        {
            if(transdis[*it]!=2e9) continue;
            transdis[*it]=transdis[cur]+1;
            Q.push(*it);
        }
    }
}
int calnoTRSFdis(int l,int r,const int n)
{
    int lca=LCA(l,r,n);
    int disl=dep[l]-dep[lca],disr=dep[r]-dep[lca];
    return disl+disr;
}
int calTRSFdis(int l,int r,const int n)
{
    if(transdis[l]==2e9||transdis[r]==2e9) return 2e9;
    else return calnoTRSFdis(l,transdis[l],n)+calnoTRSFdis(r,transdis[r],n);
}
int main()
{
    int n,k,q;
    scanf("%d%d%d",&n,&k,&q);
    for(int i=1;i<n;i++)
    {
        int curx,cury;
        scanf("%d%d",&curx,&cury);
        G[curx].push_back(cury);
        G[cury].push_back(curx);
        transdis[i]=2e9;
    }
    transdis[n]=2e9;
    for(int i=1;i<=k;i++)
    {
        int cur;
        scanf("%d",&cur);
        Q.push(cur);
    }
    trans();
    dfs(1,0);
    calcfa(n);
    while(q--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        int dis1=calnoTRSFdis(u,v,n),dis2=calTRSFdis(u,v,n);
        printf("%d\n",min(dis1,dis2));
    }
    return 0;
}

2024/7/9 12:01
加载中...