admin 管理员组

文章数量: 1087139

城市猎人

城市猎人

手玩样例发现其实如果当两个点已经联通了，那么再连一条边其实没什么用，所以可以不连这条边，然后就构造出了一棵树,然后就不会了

事 实 上 ， 很 容 易 ？ ？ ？ 想 到 这 时 候 要 找 L C A ， （ 好 吧 ， 我 不 太 熟 ） ， 算 出 路 径 上 最 大 的 天 数 ， 就 是 答 案 事实上，很容易？？？想到这时候要找LCA，（好吧，我不太熟），算出路径上最大的天数，就是答案 事实上，很容易？？？想到这时候要找LCA，（好吧，我不太熟），算出路径上最大的天数，就是答案

#include<bits/stdc++.h>
using namespace std;const int N=1e5+5;
int n,m,Q,cnt=0,fa[N],head[N],dep[N],f[N][22],l[N][22],lg[N],rt=0;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);
}
struct edge{int link,u,v,len;
}q[N<<2];
void put(int x,int y,int len){q[++cnt].v=y;q[cnt].u=x;q[cnt].link=head[x];q[cnt].len=len;head[x]=cnt;
}
bool Union(int x,int y){int fx=find(x),fy=find(y);if(fx!=fy){fa[fx]=fy;return false;}return true;
}
void dfs(int s,int fath){if(s!=rt) {f[s][0]=fath;}int t=lg[dep[s]];for(int i=1;i<=t;i++){f[s][i]=f[f[s][i-1]][i-1];l[s][i]=max(l[f[s][i-1]][i-1],l[s][i-1]);}for(int i=head[s];i;i=q[i].link){int v=q[i].v;if(v==fath) continue;dep[v]=dep[s]+1;l[v][0]=q[i].len;dfs(v,s);}
}
int lon;
int Lca(int x,int y){if(dep[x]<dep[y]) swap(x,y); lon=0;if(x==y) return 0;while(dep[x]>dep[y]){lon=max(lon,l[x][lg[dep[x]-dep[y]]]);x=f[x][lg[dep[x]-dep[y]]];}if(x==y){return lon;}for(int i=lg[dep[y]-1];i>=0;i--)if(f[x][i]!=f[y][i])lon=max(lon,l[x][i]),lon=max(lon,l[y][i]),x=f[x][i],y=f[y][i]; lon=max(l[x][0],lon),lon=max(l[y][0],lon),x=f[x][0],y=f[y][0];return lon;
}
int main(){scanf("%d%d%d",&n,&m,&Q);for(int i=1;i<=n;i++){fa[i]=i;}f[1][0]=1,lg[1]=0;for(int i=2;i<=n;i++){lg[i]=lg[i>>1]+1;}rt=0;for(int i=1;i<=m;i++){int now=m-i+1,td=2*now;while(td<=n) {if(!rt) rt=now;if(!Union(td,now)){put(now,td,i);put(td,now,i);}td+=now;}}dep[rt]=0;f[rt][0]=rt;l[rt][0]=N;dfs(rt,0);for(int i=1;i<=Q;i++){int u,v;scanf("%d%d",&u,&v);int k=Lca(u,v);printf("%d\n",k);}
}

本文标签： 城市猎人

版权声明：本文标题：城市猎人 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/b/1687973473a163899.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。