P8805 [蓝桥杯 2022] 机房

题意

给出一颗大小为 $n$ 的树和 $m$ 次询问，每个点的权值为它的边数。每次询问输入两个正整数 $u,v$，输出 $u$ 到 $v$ 的路径大小。

数据范围：$n,m\leq 10^5$

思路

题目虽然说是求 $u$ 到 $v$ 的最短路径，但对于一颗树来说，只需要保证不重复经过边即可保证这点。也就是说只要能把点权转化一下，这道题就变成了 $LCA$ 的模板题了。（不会 $LCA$？这里有模板）

将点权作为这个点与它的父亲的边权，用 $LCA$ 算出路径的长度之后，会发现 $LCA$处的点权被抵消了，再加上 $LCA$ 处的点权即为答案。

举一个例子来说明一下：

先把点权转化为边权，计算出所有点到根节点 $1$ 的距离 $dis$。对应代码dis[v]=dis[u]+a[v];

若要计算节点 $6$ 与 $7$ 的距离，可以发现它们路径上深度最小的点便是它们的最近公共祖先。节点 $6$ 和 $7$ 到根节点 $1$ 的路径合并后，多余的地方便是它们的 $LCA$ 节点 $3$ 到根节点的距离乘二。此时节点 $3$ 的点权没被计算到，加上就行了。

其他细节见代码。

代码

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+9;
int n,m,a[N],fa[N][21],dep[N],dis[N];
vector<int> e[N];

void dfs(int u,int f){
    fa[u][0]=f;
    dep[u]=dep[f]+1;
    for(int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int v:e[u]){
        if(v==f) continue;
        dis[v]=dis[u]+a[v];//a[v]即为u,v边权，dis[v]为v与根节点的距离
        dfs(v,u);
    }
}
int lca(int u,int v){//倍增求lca
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=20;i>=0;i--){
        if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    }
    if(u==v) return u;
    for(int i=20;i>=0;i--){
        if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    }
    return fa[u][0];
}

int main(){
    scanf("%d%d",&n,&m);
    int u,v;
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
        a[u]++,a[v]++;//点权
    }
    dfs(1,0);
    while(m--){
        scanf("%d%d",&u,&v);
        int d=lca(u,v);
        printf("%d\n",dis[u]+dis[v]-2*dis[d]+a[d]);//路径长度+lca处点权
    }
    return 0;
}

打赏