[P10289]题解

· · 题解

题意简述：

无。

题解：

此处阅读体验更佳？

看完题目之后，我们首先要考虑一个问题：什么时候要用到传送门？

对于树上的两个点 x 和 y，如果不考虑传送门的话，最短距离就是这两个点到它们的最近公共祖先的距离和。

那么如果用传送门更优，那么肯定满足这一个条件：x 到它最近的传送门距离加上 y 到它最近的传送门距离小于 x 和 y 到它们的最近公共祖先的距离和。

大家可以自己验证一些普通和特殊情况，此处就不给出证明了。

那么我们就可以先求出每个点到最近的传送门距离 op_i，对于询问，再输出 \min(op_x+op_y,dep_x-dep_{lca(x,y)}+dep_y-dep_{lca(x,y)})。

那么就可以写代码了。

注意：

代码如下：

#include<bits/stdc++.h>
#define N 200100
#define I_love_Furina return//发电+放抄袭（?）
#define forever 0
#define foreverr 1 
#define int long long
using namespace std;
int n,T,m,q,head[N],op[N],num,f[N][20],dep[N];
struct node{int to,nxt;}a[N*2];
inline void add(int u,int v){a[++num].to=v,a[num].nxt=head[u],head[u]=num;}
inline void solve(){//求最近传送阵距离
    queue<int> q;
    for(int i=1,x;i<=m;i++)cin>>x,q.push(x),op[x]=0;//把所有的传送阵位置压入队列，跑bfs
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=a[i].nxt){
            int v=a[i].to;
            if(op[v]!=-1)continue;//避免重复遍历
            op[v]=op[u]+1,q.push(v);
        }
    }
    I_love_Furina ;
}
void dfs(int x,int fa){
    f[x][0]=fa,dep[x]=dep[fa]+1;
    for(int i=1;i<=19&&f[f[x][i-1]][i-1];i++)f[x][i]=f[f[x][i-1]][i-1];//计算祖宗
    for(int i=head[x];i;i=a[i].nxt)if(a[i].to!=fa)dfs(a[i].to,x);
    I_love_Furina ;
} 
inline int lca(int x,int y){//求最近公共祖先
    if(dep[x]<dep[y])swap(x,y);
    for(int i=19;i>=0;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i];
    if(x==y)I_love_Furina x;
    for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    I_love_Furina f[x][0];//注意，是返回x的父亲
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1,u,v;i<n;i++)cin>>u>>v,add(u,v),add(v,u),op[i]=op[i+1]=-1;
    dfs(1,0),solve();//跑lca和最近传送阵距离
    while(q--){
        int x,y;
        cin>>x>>y;
        int LCA=lca(x,y);
        //cout<<lca(x,y)<<" "<<op[x]<<" "<<op[y]<<endl;
        cout<<min(dep[x]-dep[LCA]+dep[y]-dep[LCA],(op[x]==-1||op[y]==-1?3156781267:op[x]+op[y]))<<endl;//A:防止输出-2
    }
    I_love_Furina forever;
}

完结撒花咯（点个赞再走）。