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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

最短的Link-Cut-Tree模板(原创普通Splay版非指针)  

2015-03-01 10:22:03|  分类: 算法学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

const int N=30010;
int n,fa[N],son[N][2],val[N],siz[N],stmp,rev[N];
#define swap(a,b) (stmp=a,a=b,b=stmp)
void pu(int t){siz[t]=siz[son[t][0]]+siz[son[t][1]]+1;}
void pd(int t){rev[t]?rev[t]=0,rev[son[t][0]]^=1,rev[son[t][1]]^=1,swap(son[t][0],son[t][1]),1:1;}
bool nr(int t){return son[fa[t]][0]==t||son[fa[t]][1]==t;}
void rtt(int t,int f=0,bool p=0){
    p=son[f=fa[t]][1]==t,
    fa[t]=fa[f],nr(f)?son[fa[f]][son[fa[f]][1]==f]=t:1,
    (son[f][p]=son[t][!p])?fa[son[f][p]]=f:1,
    pu(son[fa[f]=t][!p]=f);
}
void pv(int t){if(nr(t))pv(fa[t]);pd(t);}
void splay(int t,int f=0){
    for(pv(t);nr(t);rtt(t))nr(f=fa[t])?
    rtt(son[f][1]==t^son[fa[f]][1]==f?t:f),1:1;pu(t);
}
void access(int t,int la=0){for(;t;splay(t),son[t][1]=la,la=t,t=fa[t]);}
void makeroot(int t){access(t),splay(t),rev[t]^=1;}
void link(int u,int v){makeroot(u),fa[u]=v;}
void cut(int u,int v){makeroot(u),access(v),splay(v),son[v][0]=fa[u]=0;}

正常版:

//template of Link-Cut-Tree
const int N=30010;
int rev[N],far[N],son[N][2],val[N],siz[N],swap_tmp;
bool not_root(int t)
{
    return son[far[t]][0]==t||son[far[t]][1]==t;
}
void push_up(int t)
{
    siz[t]=siz[son[t][0]]+siz[son[t][1]]+1;
}
void push_down(int t)
{
    rev[t]?rev[t]=0,rev[son[t][0]]^=1,rev[son[t][1]]^=1,
    swap_tmp=son[t][0],son[t][0]=son[t][1],son[t][1]=swap_tmp:1;
}
void rotate(int t)
{
    int f=far[t],p=son[f][1]==t;
    far[t]=far[f],not_root(f)?son[far[f]][son[far[f]][1]==f]=t:1,
    (son[f][p]=son[t][!p])?far[son[f][p]]=f:1,push_up(son[far[f]=t][!p]=f);
}
void preview(int t)
{
    if(not_root(t))preview(far[t]);
    push_down(t);
}
void splay(int t,int f=0)
{
    for(preview(t);not_root(t);rotate(t))
    if(not_root(f=far[t]))rotate((son[f][1]==t^son[far[f]][1]==f?t:f));
    push_up(t);
}
void access(int t)
{
    for(int las=0;t;splay(t),son[t][1]=las,las=t,t=far[t]);
}
void makeroot(int t)
{
    access(t),splay(t),rev[t]^=1;
}
void link(int u,int v)
{
    makeroot(u),far[u]=v;
}
void cut(int u,int v)
{
    makeroot(u),access(v),splay(v),son[v][0]=far[u]=0;
}

  评论这张
 
阅读(225)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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