【LCA】P4281 [AHOI2008]紧急集合 / 聚会

客官°小女子只卖身不卖艺 2024-03-16 09:39 17阅读 0赞

[P4281 \[AHOI2008\]紧急集合 / 聚会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P4281 _AHOI2008_ _ _ - _ _ _ _luogu.com.cn]

题意：

![10f6b0e596f444858e3314b7e450a9cc.png][]

思路：

手推一下样例发现该点去三个LCA中深度最深的那个点

![6153c28251fc4c4ba9f02776a3e8ec64.jpeg][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    #define ll long long
    const int mxn=5e5+10,mxe=5e5+10;
    struct ty{
        int to,next;
    }edge[mxe<<1];
    queue<int> q;
    int n,m,u,v,tot=0,x,y,z,t,rt;
    int head[mxn],in[mxn],f[mxn][33],dep[mxn],vis[mxn<<1];
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
        }
    }
    int lca(int u,int v){
        if(dep[u]<dep[v]) swap(u,v);
        for(int j=30;j>=0;j--){
            if(dep[f[u][j]]>=dep[v]){
                u=f[u][j];
            }
        }
        if(u==v) return u;
        for(int j=30;j>=0;j--){
            if(f[u][j]!=f[v][j]){
                u=f[u][j];
                v=f[v][j];
            }
        }
        return f[u][0];
    }
    void bfs(){
        q.push(1);vis[1]=1;
        dep[0]=0,dep[1]=1;
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=head[u];~i;i=edge[i].next){
                if(vis[edge[i].to]) continue;
                vis[edge[i].to]=1;
                dep[edge[i].to]=dep[u]+1;
                f[edge[i].to][0]=u;
                for(int j=1;j<=30;j++){
                    f[edge[i].to][j]=f[f[edge[i].to][j-1]][j-1];
                }
                q.push(edge[i].to);
            }
        }
    }
    int dist(int u,int v){
    	return dep[u]+dep[v]-2*dep[lca(u,v)];
    }
    void solve(){
        cin>>n>>m;
        init();
        for(int i=1;i<=n-1;i++){
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }
        bfs();
        //for(int i=1;i<=n;i++) cout<<dep[i]<<" \n"[i==n];
        for(int i=1;i<=m;i++){
            cin>>x>>y>>z;
            //cout<<x<<" "<<y<<" "<<z<<'\n';
            int t1=lca(x,y);
            int t2=lca(x,z);
            int t3=lca(y,z);
    		int t=t1,mx=max(max(dep[t1],dep[t2]),dep[t3]);
    		if(dep[t1]==mx) t=t1;
    		else if(dep[t2]==mx) t=t2;
    		else t=t3;
    		cout<<t<<" "<<dist(x,t)+dist(y,t)+dist(z,t)<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[P4281 _AHOI2008_ _ _ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P4281
[10f6b0e596f444858e3314b7e450a9cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/3d07c423f2524a399cc48e537f46195d.png
[6153c28251fc4c4ba9f02776a3e8ec64.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/514de4173418406bb12034e3d271cec4.png