P4281 紧急集合 lca 树上点间距离计算

· · 个人记录

这道题，很容易想到先把最近的人聚在一起，剩下一个人去找他们，加上是树，想到求Lca。集合的点肯定是两两的Lca之一。最简单思路就是3个点都算出来。

1.不把6个点都算出来，又为了避免都在同一子树上往上走的浪费，故想到了以其中一个点为根，跑tarjan

40pts：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,s,ans;
int head[N],nxt[N],to[N],cnt;
int deep[N],fa[N],vis[N],aim[N],Lca,ok;
void add(int u,int v){
    nxt[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
    return ;
}
int find(int x){
    if(fa[x]!=x) return fa[x]=find(fa[x]);
    return x;
}
void dfs(int x,int father){
    fa[x]=x;
    vis[x]=1;
    deep[x]=deep[father]+1;
    int v;
    for(int i=head[x];i;i=nxt[i]){
        v=to[i];
        if(ok==1) return ;
        if(!vis[v]){
            dfs(v,x);
            fa[v]=x;
        }
    }
    if(vis[aim[x]]) Lca=find(aim[x]),ok=1;
    return ;
}
int main(){
    scanf("%d%d",&n,&m);
    int a,b,c;
    for(int i=1;i<n;++i){
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }   
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&a,&b,&c);
        memset(vis,0,sizeof(vis));
//      for(int j=1;j<=n;++j) fa[j]=j;
        ok=0;
        aim[b]=c,aim[c]=b;
        dfs(a,0);
        aim[b]=aim[c]=0;
        printf("%d %d\n",Lca,deep[b]+deep[c]-deep[Lca]-1);
    }
    return 0;
}

因为每个问都要跑一遍，O（nm）T掉，卡常卡到70tps

70pts：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,s,ans;
int head[N],nxt[N],to[N],cnt;
int deep[N],fa[N],vis[N],aim[N],Lca,ok;
void add(int u,int v){
    nxt[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
    return ;
}
int find(int x){
    if(fa[x]!=x) return fa[x]=find(fa[x]);
    return x;
}
int st[N],top;
void dfs(int x,int father){
    fa[x]=x;
    vis[x]=1;
    st[++top]=x;
    deep[x]=deep[father]+1;
    int v;
    for(int i=head[x];i;i=nxt[i]){
        v=to[i];
        if(ok==1){
            return ;
        }
        if(!vis[v]){
            dfs(v,x);
            fa[v]=x;
        }
    }
    if(vis[aim[x]]) 
    {
        Lca=find(aim[x]),ok=1;
        while(top){
            vis[st[top]]=0;
            top--;
        }
    }
    return ;
}
int main(){
    scanf("%d%d",&n,&m);
    int a,b,c;
    for(int i=1;i<n;++i){
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }   
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&a,&b,&c);
//      memset(vis,0,sizeof(vis));
//      for(int j=1;j<=n;++j) fa[j]=j;
        ok=0;
        aim[b]=c,aim[c]=b;
        dfs(a,0);
        aim[b]=aim[c]=0;
        printf("%d %d\n",Lca,deep[b]+deep[c]-deep[Lca]-1);
    }
    return 0;
}

优化不下去了，回到一开始的想法，算3个Lca，取最深的一个

100pts：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m;
int head[N],nxt[N],to[N],cnt;
int deep[N],fa[N][26];      //24会因为数组越界出错 
void add(int u,int v){
    nxt[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
    return ;
}
void dfs(int x,int father){
    deep[x]=deep[father]+1;
    fa[x][0]=father;
    for(int i=1;(1<<i)<=deep[x];++i)    fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=head[x];i;i=nxt[i])   if(to[i]!=father) dfs(to[i],x); 
    return ;
}
int lca(int a,int b){
    if(deep[a]<deep[b]) swap(a,b);
    for(int i=24;i>=0;i--)  if(deep[a]-(1<<i)>=deep[b]) a=fa[a][i];
    if(a==b)    return a;
    for(int i=24;i>=0;i--)  
        if(fa[a][i]!=fa[b][i]){         
            a=fa[a][i],b=fa[b][i];
        }
    return fa[a][0];
}
int main(){
    scanf("%d%d",&n,&m);
    int a,b,c,Lca,Lcb,Lcc;
    for(int i=1;i<n;i++){
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }   
    dfs(1,0);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        Lca=lca(a,b),Lcb=lca(b,c),Lcc=lca(c,a);
        if(deep[Lcb]>deep[Lca]) swap(a,b),swap(Lca,Lcb);
        if(deep[Lcc]>deep[Lca]) swap(a,c),swap(Lca,Lcc);
        printf("%d %d\n",Lca,deep[a]+deep[b]+deep[c]-deep[Lca]-deep[Lcb]-deep[Lcc]);
    }
    return 0;
}

在计算距离时一开始想到是这样的：

deep[a]+deep[b]-deep[Lca]-deep[c]

让c最高

但这样只在3个点都在同一颗子树上才成立

by the way，计算Lca时要注意倍增数组不要越界，自己写的时候出现好几次这个问题，唐完了