P4616 [COCI 2017/2018 #5] Pictionary
我们发现，第 \(i\) 天会让所有为 \((m-i+1)\) 倍数的节点相互连通。可以将 \((m-i+1)\) 向它所有的倍数连边，效果是相同的。
我们规定边权为 \(i\)。
那么对于建好的图，我们不难发现查询 \((u,v)\) 其实是在查 \(u,v\) 间的最小瓶颈路。及所有路径上最大值的最小值。
可以对原图跑最小生成树，然后查询两点间最大边权即可。
不过我们加边已经是有序的了，所以加边过程中 用并查集维护一下连通性就可以了。
用的倍增，复杂度 \(O((n+q)\log n)\)。可以用 DFS 序求 LCA 做到 \(O(n\log n+q)\)。
点击查看代码
#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int N=1e5+5;
int n,m,q,ffa[N],fa[N][20],mx[N][20],dep[N];
struct Ed{int to,w;};
vector<Ed> G[N];
inline int find(int x){return x==ffa[x]?x:ffa[x]=find(ffa[x]);}
inline void add(int u,int v,int w){G[u].eb(Ed{v,w});}
inline void uadd(int u,int v,int w){add(u,v,w),add(v,u,w);}
inline void dfs(int u){dep[u]=dep[fa[u][0]]+1;for(int i=0;i<19;i++)fa[u][i+1]=fa[fa[u][i]][i],mx[u][i+1]=max(mx[u][i],mx[fa[u][i]][i]);for(Ed i:G[u]){if(i.to^fa[u][0]) fa[i.to][0]=u,mx[i.to][0]=i.w,dfs(i.to);}
}
inline int calc(int u,int v){int a=0;if(dep[u]<dep[v]) swap(u,v);for(int i=19;~i;i--) if(dep[fa[u][i]]>=dep[v]) a=max(a,mx[u][i]),u=fa[u][i];if(u==v) return a;for(int i=19;~i;i--) if(fa[u][i]^fa[v][i]){a=max(a,mx[u][i]),u=fa[u][i];a=max(a,mx[v][i]),v=fa[v][i];}return max({a,mx[u][0],mx[v][0]});
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m>>q;for(int i=1;i<=n;i++) ffa[i]=i;for(int i=m;i;i--){for(int j=(i<<1);j<=n;j+=i){if(find(j)^find(i)) ffa[ffa[j]]=ffa[i],uadd(i,j,m-i+1);}}dfs(1);int a,b;while(q--){cin>>a>>b;cout<<calc(a,b)<<"\n";}return 0;
}