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

题目需要一种支持合并一些点集的数据结构，显然是并查集，我们考虑对每个时间都合并一次点集，显然复杂度为$O(nlogn)$ 然后每个点记录的是他和他父亲合并时的时间戳，那么显然，在查询两个点$(x,y)$的联通时间时，就是$x$到$lca(x,y)$的最大值加上$lca(x,y)$到$y$的最大值，注意不能包含$lca(x,y)$，因为这个点存储的时间是和另外一个点集的合并时间 然后往上跳就行，因为不能路径压缩，我们采用启发式合并 ```cpp /*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"; } } ```