[AHOI2008]MEET 紧急集合

题目链接

https://ac.nowcoder.com/acm/problem/20532

解题思路

整体思路：
考虑每两个节点之间的最短距离就是求这两个点的 LCA ，那么三个点我们可以先两两一组找到 LCA。我们可以发现三个点的 LCA 要么是完全一样，要么是有两个（两个相同，一个不同），如果是有两种 LCA 那么此时我们要选择不同的那一个这样才能使路径最短，因为可以保证有一条路径不会重复两遍。
这个的粗略证明应该比较简单，自己手画画就行。肯定要找祖先作为集合地点，之后总结一下什么情况下用哪个祖先，整理一下得到上面的结论。

具体实现

代码1是通过ST表+欧拉序实现的，因为当时只会这个方法求LCA，但是时间复杂度有点高，所以出现了有时AC有时WA的现象；（有关例题及讲解）
代码2是通过树上倍增实现的，复杂度明显比上面的方法低，能完美AC。下面着重讲一下“树上倍增”
~~其实理解了ST表之后理解倍增易如反掌~~

倍增

如果你刚接触倍增就看看这个吧
你会发现上面的讲解真的是一点代码都没给，哈哈，但是讲的通俗易懂，Orz。

树上倍增

树上倍增，字面意思，树上实现倍增，

链式前向星

学起来！会的忽略

介绍几个数组：

dp[i]含义为节点i的深度；
fa[x][i]含义为节点x往根的方向探索i个节点（含i节点）所到达的节点序号，也可以理解为节点x的上方第i-1个父亲；
lg[i]含义为深度为i的节点向根方向跳的范围是[1,log2(i)]。也就是说我们之后用lg数组，其下标永远为节点的深度，含义为当前这个深度的节点最多能探索 2^lg[i] 个节点，再直接点：找一个最大的t，2^t <= dp[i]，让lg[dp[i]] = t。

求lg数组：

for(int i=1;i<=n;i++){//求出log2(i)+1的值
    lg[i]=lg[i-1]+(1<<lg[i-1]==i);
}

可以模拟一下：

lg[1]=0+(1==1)=1
lg[2]=1+(1==1)=2
lg[3]=2+(4==3)=2
lg[4]=2+(4==4)=3

这里为什么用递推公式求log2(i)+1，而不用cmath里的函数求log2(i)，原因是：
log是以e为底数， log10是以10为底数
求log2(i)，则：log(i)/log(2)速度慢，不如求出log2(i)+1的值存在lg[i]数组里，需要的时候用lg[i]-1

核心代码

求倍增LCA的思想是：

先让深度大的节点跳到与深度小的节点深度相同的节点且此节点必须为深度大的节点的祖先；
再让现在两个同深度的节点一起往上跳且每次跳的步数也相同，直到找到相同的祖先，此节点为公共祖先。

图片说明
比如节点7和9,9先跳到8，此时和7是同一层，若是跳地太多到1，就会错认为1是LCA
正确的是7->4 9->8->5
fa[4][0]或fa[5][0]=3就是答案

int LCA(int x,int y)
{
    if(dp[x]<dp[y]) swap(x,y);//永远让x节点为深度较大的节点    
    while(dp[x]>dp[y]) x=fa[x][lg[dp[x]-dp[y]]-1];//只要x节点的深度大于y节点的深度，就让x变成自己所能到达的离y深度最近的节点且此节点必须为x的祖先节点
    if(x==y) return x;//发现x与y为同一点了，公共祖先就是当前的x点
    for(int i=lg[dp[x]];i>=0;i--)//尽可能往远跳，如果当前遍历到的x，y的祖先不是同一个祖先的话，就不停的往上跳
    if(fa[x][i]!=fa[y][i])
    x=fa[x][i],y=fa[y][i];
    return fa[x][0];//x点的父亲就是公共祖先了
}

AC代码1

//代码1
//ST表+欧拉序实现求LCA 
//可能AC，也可能WA，说明时间有点紧张
//不用read直接WA不停
#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;

int path[N<<1],pos[N<<1][20],st[N<<1][20],dp[N],in[N],head[N];
int n,m,a,b,c,x,y,z,Time,cnt,pp;

struct node
{
    int v,next;    
}e[N<<1];

inline int read()
{
    int x,f=1;
    char ch='*';
    while(!isdigit(ch=getchar()))
    if(ch=='-') f=-1;
    x=ch-'0';
    while(isdigit(ch=getchar()))
    x=(x<<3)+(x<<1)+ch-'0';
    return x*f;
}

void add(int u,int v)
{
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x,int fa,int deep)
{
    path[++Time]=x;
    if(dp[x]==0) dp[x]=deep;
    if(in[x]==0) in[x]=Time;
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].v==fa) continue;
        dfs(e[i].v,x,deep+1);
        path[++Time]=x;
    }
}

void ST()
{
    for(int i=1;i<=Time;i++) st[i][0]=dp[path[i]],pos[i][0]=i;

    for(int j=1;(1<<j)<=Time;j++)
    for(int i=1;i+(1<<j-1)-1<=Time;i++)
    if(st[i][j-1]<st[i+(1<<j-1)][j-1]) st[i][j]=st[i][j-1],pos[i][j]=pos[i][j-1];
    else st[i][j]=st[i+(1<<j-1)][j-1],pos[i][j]=pos[i+(1<<j-1)][j-1];
}

int LCA(int x,int y)
{
    int k=0,l=in[x],r=in[y];
    if(l>r) swap(l,r);
    while(l+(1<<k+1)-1<=r) k++;
    return st[l][k]<st[r-(1<<k)+1][k]?path[pos[l][k]]:path[pos[r-(1<<k)+1][k]];
}


int main()
{
    n=read(),m=read();
/    for(int i=1;i<n;i++) 
    {
        a=read(),b=read();
        add(a,b);add(b,a);    
    }

    dfs(1,-1,1);ST();
    while(m--)
    {
        a=read(),b=read(),c=read();
        x=LCA(a,b);y=LCA(a,c);z=LCA(b,c);

        if(x==y) pp=z;
        else if(x==z) pp=y;
        else pp=x;
        printf("%d %d\n",pp,dp[a]+dp[b]+dp[c]-dp[x]-dp[y]-dp[z]);//这个输出好灵魂啊！！！
    }
    return 0;
}

AC代码2

//树上倍增 完美AC
#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;

int dp[N],head[N],fa[N][20],lg[N];
int n,m,a,b,c,x,y,z,cnt,ans;

struct node
{
    int v,next;    
}e[N<<1];

inline int read()
{
    int x,f=1;
    char ch='*';
    while(!isdigit(ch=getchar()))
    if(ch=='-') f=-1;
    x=ch-'0';
    while(isdigit(ch=getchar()))
    x=(x<<3)+(x<<1)+ch-'0';
    return x*f;
}

void add(int u,int v)
{
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x,int fath)
{
    dp[x]=dp[fath]+1;
    fa[x][0]=fath;
    for(int i=1;i<=lg[dp[x]];i++)
    fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].v==fath) continue;
        dfs(e[i].v,x);
    }
}

void getlg()
{
    for(int i=1;i<=n;i++)
    lg[i]=lg[i-1]+(1<<lg[i-1]==i);
}

int LCA(int x,int y)
{
    if(dp[x]<dp[y]) swap(x,y);    
    while(dp[x]>dp[y]) x=fa[x][lg[dp[x]-dp[y]]-1];
    if(x==y) return x;
    for(int i=lg[dp[x]];i>=0;i--)
    if(fa[x][i]!=fa[y][i])
    x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

int main()
{
    n=read(),m=read();

    for(int i=1;i<n;i++) 
    {
        a=read(),b=read();
        add(a,b);add(b,a);
    }
    getlg();dfs(1,0);
    while(m--)
    {
        a=read(),b=read(),c=read();
        int x=LCA(a,b),y=LCA(b,c),z=LCA(a,c);
        if(x==y) ans=z;
        else if(y==z) ans=x;
        else ans=y;
        printf("%d %d\n",ans,dp[a]+dp[b]+dp[c]-dp[x]-dp[y]-dp[z]);//这个输出好灵魂啊！！！
    }
}

总结

不知道为什么我只想感叹求花费的方法好牛皮，我还用了多个判断输出，Orz。
总的来说大致思路是想到了，想到了和祖先有关，粗略证明了要选祖先，分了几种情况讨论，但是我是根据三个点的是否位于同一条树枝上讨论的，而正解是根据祖先是否相等讨论的，所以当时想到这思路的时候，发现还要求相对位置，就得再dfs一遍欧拉序，觉得时间复杂度不允许，就直接看了题解，发现果然有点问题。还是TCL。