题解 P4616 【[COCI2017-2018#5] Pictionary】

· · 题解

题目需要一种支持合并一些点集的数据结构，显然是并查集，我们考虑对每个时间都合并一次点集，显然复杂度为O(nlogn)

然后每个点记录的是他和他父亲合并时的时间戳，那么显然，在查询两个点(x,y)的联通时间时，就是x到lca(x,y)的最大值加上lca(x,y)到y的最大值，注意不能包含lca(x,y)，因为这个点存储的时间是和另外一个点集的合并时间

然后往上跳就行，因为不能路径压缩，我们采用启发式合并

/*deco loves Chino*/
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int n,m,q;
int f[100010],siz[100010],t[100010],app[100010],dep[100010],maxn[100010]; 
vector<int> vc[100010];
int find(int x)
{
    if(x==f[x])
    {
        return x;
    }
    return find(f[x]);
}
void dfs(int u)
{
    for(int i=0;i<vc[u].size();i++)
    {
        int v=vc[u][i];
        dep[v]=dep[u]+1;
        dfs(v);
    }
}
int main()
{
    //freopen("pictionary.in","r",stdin);
    //freopen("pictionary.out","w",stdout);
    cin>>n>>m>>q;
    int rt;
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
        siz[i]=0;
    }
    for(int i=m;i>=1;i--)
    {
        for(int j=(i<<1);j<=n;j+=i)
        {
            int nt=(m-i+1);
            int dx=find(i),dy=find(j);
            if(dx==dy)
            {
                continue;
            }
            if(siz[dx]<siz[dy])
            {
                swap(dx,dy);
            }
            f[dy]=dx;
            vc[dx].push_back(dy);
            rt=dx;
            if(siz[dx]==siz[dy])
            {
                ++siz[dx];
            }
            t[dy]=nt;
        }
    }
    dfs(rt);
    for(int i=1;i<=q;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        int ans=0;
        if(dep[x]<dep[y])
        {
            swap(x,y);
        }
        while(dep[x]>dep[y])
        {
            ans=max(ans,t[x]);
            x=f[x];
        }
        while(x!=y)
        {
            ans=max(max(t[x],t[y]),ans);
            x=f[x],y=f[y];
        }
        cout<<ans<<"\n";
    }
}