注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

 
 
 

日志

 
 

bzoj 3319 黑白树 离线并查集做法  

2014-06-24 08:15:19|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
碰到一道可以不用那几种数据结构的方法做的数据结构题,于是便决定好好写下
首先 我们可以用fa记录父亲 fa2记录从该点往上走延伸到的最远点(满足两点之间的路径全黑)
然后逐渐维护到最终状态,并且记录一个时间戳(边的最早的染色时间) 
这一部分就是O(n)的
然后fa2重新利用(这点很坑的样子 大家可以新建一个数组) 
记录从该点往上走延伸到的最远点(满足两点之间的路径全白)
然后从后往前回答,并且进行维护
如果用基数排序的话,这一部分的复杂度为O(n)
大概就是这些了 细节可以看看代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define rep(i,n) for(int i=1;i<=n;++i)
#define imax(x,y) (x>y?x:y)
#define imin(x,y) (x<y?x:y)
using namespace std;
const int N=1000010;
int firste[N],nexte[N<<1],v[N<<1],num[N];
int fa[N],fa2[N],q[N],ti[N],ans[N],ceng[N],cnt[N],change[N];
int n,e=1,m;
void build_edge(int x,int y)
{
++e;
nexte[e]=firste[x];
firste[x]=e;
v[e]=y;
}
void bfs()
{
int ifront=0,itail=1;
q[1]=1;
while(ifront<itail)
{
int u=q[++ifront];
for(int p=firste[u];p;p=nexte[p])
if(v[p]!=fa[u])
{
q[++itail]=v[p];
fa[v[p]]=u;
num[v[p]]=p>>1;
ceng[v[p]]=ceng[u]+1;
}
}
}
int findf(int x)
{
if(fa2[x]!=x)
fa2[x]=findf(fa2[x]);
return fa2[x];
}
void color(int x,int y,int tt)
{
x=findf(x);
y=findf(y);
int tmp;
while(x!=y)
{
if(ceng[x]<ceng[y])tmp=x,x=y,y=tmp;
if(ti[x]<tt)x=fa2[x];
else fa2[x]=fa[x],ti[x]=tt,x=fa[x];
}
}
int main()
{
int x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
build_edge(x,y);
build_edge(y,x);
}
fa[1]=1;
bfs();
memset(ans,-1,sizeof(ans));
rep(i,n)
{
fa2[i]=i;
ti[i]=m+1;
}
rep(i,m)
{
scanf("%d",&x);
if(x&1)
scanf("%d",&ans[i]);
else
{
scanf("%d%d",&x,&y);
color(x,y,i);
}
}
rep(i,n)++cnt[ti[i]];
for(int i=1;i<=m+1;++i)cnt[i]+=cnt[i-1];
rep(i,n)change[cnt[ti[i]]--]=i;
rep(i,n)fa2[i]=i;
int all=n,u;
for(int i=m+1;i;--i)
{
if(ans[i]!=-1)
ans[i]=num[findf(ans[i])];
else
for(;all&&ti[u=change[all]]==i;--all)
fa2[u]=fa2[fa[u]];
}
rep(i,m)
if(ans[i]!=-1)
printf("%d\n",ans[i]);
return 0;
}



  评论这张
 
阅读(359)| 评论(4)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017