Each of the following ?Q lines contains two distinct positive integers ?A and ?B(1 ≤ ?A, ?B ≤ ?N)that denote the cities of the mathematicians who want to find out the minimal number of daysbefore they can play pictionary together.
输出格式The \(i^{th}\) line must contain the minimal number of days before the mathematicians from the \(i^{th}\) query can play pictionary together.
样例 #1样例输入 #18 3 32 53 64 8样例输出 #1312样例 #2样例输入 #225 6 120 9样例输出 #24样例 #3样例输入 #39999 2222 21025 24053154 8949样例输出 #319802160提示In test cases worth 40% of total points, it will hold ?N≤ 1000, ?Q≤ 100 000.
Clarification of the first test case:
On the first day, road (3, 6) is built. Therefore the answer to the second query is 1.
On the second day, roads (2, 4), (2, 6), (2, 8), (4, 6) and (6, 8) are built. Cities 4 and 8 are nowconnected (it is possible to get from the first to the second using city 6).
On the third day, roads between relatively prime cities are built, so cities 2 and 5 are connected.
Clarification of the second test case:
On the second day, road (20, 15) is built, whereas on the fourth day, road (15, 9) is built. After thefourth day, cities 20 and 9 are connected via city 15.
审题题意转化：
有\(n\)座城市；有\(m\)个时刻 ， 在第\(i\)个时刻 ， 所有\(m-i+1\)的倍数之间连边；有\(q\)个询问 ， 询问第\(x_i\)座城市和第\(y_i\)座城市什么时候连通 。
连边（合并）连通城市的过程 ， 其实就是对多个点建立集合 ， 并进行合并的过程 ， 所以考虑使用并查集 。
在对两个城市进行连边（即合并两个点）时 ， 钦定第一个城市是第二个城市的父亲节点 ， 并记录这两个点合并时的时间戳 。
查询现询问两个点\((x,y)\)的最早连通时间 。\((x,y)\)的最早连通时间就是\(x\)到\(lca(x,y)\)中的最大时间戳加上\(lca(x,y)\)到\(y\)中的最大时间戳 。
为什么是最大值？两个城市要想连通 ， 就必须要等到路径上最后一条边建好才行 。
为什么是\(lca\)？题目中城市\(x\)和城市\(y\)的连通抽象到图上就是\(x\)到\(y\)的一条树上路径（同一条边不能重复走） ， 也就是\(x\)->\(lca(x,y)\)->\(y\).这里不能包含\(lca(x,y)\) ， 因为这个点储存的时间戳是和另一个点击合并的时间 。
考虑\(lca\)的求法 。在处理并查集的时候 ， 其实就处理出的图上的每一个父子关系 ， 我们可以将其利用起来：根据这些父子关系 ， \(x\)和\(y\)往上跳 ， 从而找到\(lca(x,y)\).
但要想保存父子关系就不能使用路径压缩 ， 所以采用启发式合并：将小集合合并到大集合 ， 以起到优化的作用 。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=100010;int n,m,q;int f[N],siz[N],dfn[N],dep[N];struct Edge//链式前向星存图{ int u,v,nex;}e[N<<1];int head[N],tot;void add(int u,int v){ tot++; e[tot].u=u; e[tot].v=v; e[tot].nex=head[u]; head[u]=tot;}int maxx(int a,int b){ return a>b?a:b;}int find(int x)//并查集查找（不能用路径压缩）{ if(x==f[x]) return x; return find(f[x]);}void dfs(int u)//dfs求每个点相对于超级祖先的深度{ for(int i=head[u];i;i=e[i].nex) {int v=e[i].v;dep[v]=dep[u]+1;dfs(v); }}int main(){ scanf("%d%d%d",&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)//对所有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;add(dx,dy);rt=dx;//rt最终会记录所有点的公共祖先 ， 钦定这个“超级祖先”为根节点if(siz[dx]==siz[dy]){siz[dx]++;}dfn[dy]=m-i+1;//dfn记录合并时的时间戳} } 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=maxx(ans,dfn[x]);x=f[x];}while(x!=y){ans=maxx(maxx(dfn[x],dfn[y]),ans);x=f[x],y=f[y];}printf("%d\n",ans); }}