P4281 [AHOI2008] 紧急集合 / 聚会

· · 题解

P4281 [AHOI2008] 紧急集合 / 聚会

题目翻译；

给你一颗数，边权为1，在，给你x,y,z三个节点，求一个节点，使x,y,z到该节点的花费最小

思路：

求树上路径，我们一定会想到lca，但本题要求求出3个点，那我们先求出两两之间的lca，发现其中深度最深的就是答案。原因是若两点已经到了lca若它还需要继续往上跳，花费就是双倍，不如让另一点跳到该点。

实现：

因此，我们只需要求出三者任意两两间的lca，在找到深度最深的，最后用深度来计算，其总花费即可；

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int>e[N];
int f[N][35],dep[N];
void dfs(int u,int fa){
    f[u][0]=fa;
    dep[u]=dep[fa]+1;
    for(int i=1;i<=20;i++){
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(auto ed:e[u]){
        if(ed==fa)continue;
        dfs(ed,u);
    }

}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--){
        if(dep[f[x][i]]<dep[y])continue;
        x=f[x][i];
    }
    if(x==y)return x;
    for(int i=20;i>=0;i--){
        if(f[x][i]==f[y][i])continue;
        x=f[x][i];
        y=f[y][i];
    }
    return f[x][0];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;  
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    dfs(1,0);
    while(m--){
        int x,y,z;
        cin>>x>>y>>z;
        int a=lca(x,y),b=lca(x,z),c=lca(y,z);
        int p,q,e,lc;
        if(dep[a]>=dep[b] && dep[a]>=dep[c]){
            q=x,p=y,e=z,lc=a;
        }
        else if(dep[b]>=dep[a] && dep[b]>=dep[c]){
            q=x,p=z,e=y,lc=b;
        }
        else if(dep[c]>=dep[b] && dep[c]>=dep[a]){
            q=z,p=y,e=x,lc=c;
        }
        int w=lca(q,e);
        int ans=dep[q]+dep[p]-2*dep[lc]+dep[e]+dep[lc]-2*dep[w];
        cout<<lc<<" "<<ans<<endl;
    }
}

最近公共祖先讲解