POJ 1984 Navigation Nightmare(持续创新)动态树(LCT(Link-cut-tree)&Toptree(施工遭))总结+模板题+各种题材。

并查集,给n个点和m条边,每条边有方向和长,再于q个询问,第i只询问查询两独点间以Ti时刻时的曼哈顿距离(能接则输出曼哈顿离,否则输出-1)

同样、理解LCT的劳作规律

事先看无异鸣例题:

style=”font-family: Microsoft YaHei; font-size: 16px”>让您维护一株给一定的养,需要支持下两种植操作:

Change x
val:  令x点的点权变为val

Query x
y:  计算x,y之间的唯一的不过缺少路径的点权的xor和

当下是平志树剖裸题。我们明白,当问题中起了维护及树上最差路程相关的距离操作时,基本得以确定要用树剖来做了。

 

更来拘禁一下立即道题的升级版本:

style=”font-family: Microsoft YaHei; font-size: 16px”>让您维护一蔸给得的养,需要支持下四种植操作:

Change x
val:  令x点的点权变为val

Query x
y:  计算x,y之间的唯一的无限缺少路径的点权xor和

Cut x y: 
如果x,y间有边相连,则去其。

Link x y: 
如果x,y不联通,则树立一条x,y之间的来向边。

于当时道题里,我们加了一定量只操作,Link和Cut。我们发现,这道题不得以就此树剖来做了——显然,树剖无法处理修改树的样子的相干操作的。

而今我们就是用LCT了。

 

  LCT,全称Link
Cut
Tree,中文名“动态树”。顾名思义,这种多少结构就是永葆连边和断边操作而像树剖那样维护有数码的树。由于要支持连边断边,LCT就未可知像树链剖分一样用线段树来保护了,而得用更灵敏的延展树(Splay)。

  因此,与树链剖分一样,LCT需要满足以下这些性:

  1.各个一个Splay维护的是均等条从上到下按在原树中深严格递增的路线,且备受程序不折不扣历Splay得到的每个点之深浅序列严格递增。

//只要将树剖和Splay搞懂了,这一点不难理解。

  2.每一个节点是且仅在吃一个Splay中

  3.限分为实边和虚边。实边包含在Splay树中负程序遍历的隔壁节点内,而虚边必须由同样棵Splay指向任何一个节点,也就算是中序遍历中极其倚重前之谁节点的爸。

//这里用小心的凡,一般LCT的虚边是为此Splay的绝望节点的father指针来实现的。

  辅助理解

当一棵树之虚实边是这般分配的当儿,它所对应的张树是者法:

图片 1
 图片 2

内,每一个虚线框起来的区域还是同蔸伸展开树;双向箭头指父节点存son,子节点存father的度;单项箭头指子节点存father,而父节点未存son的界限(虚边)。


立即题和Corporative Network
有点像,只不过那题是保护及干净节点的离,这书还要顺便维护与根本节点的x,y方向的偏移量。findset时,每次搜寻完father就假设增长father的x、y坐标偏移量,这样findset完之后便获得了与清的偏移量。然后合并时,
(注意,这里是 fa[x] = y)

其次、具体操作函数

dr[x].x = r.x – dr[r.u].x + dr[r.v].x;  

1.access(int u) 具体职能:把节点u到根本节点的路子压入一个Splay中(即标记为重边)

这个没图的话语实际麻烦掌握。仍然选举一个例子:

一旦我们在上图的状下本着节点M执行就同样操作,那么就棵树就会生下图的变动:

图片 3 图片 4

冲样例我们得以看到,access的操作大概可以分点儿步:

第一,Splay(M),将M旋转至Splay的彻底节点;

下一场,使节点M替代她的父亲G的右子的职,即G->rs=M。

这,原本G的右子脱离了G所于的展开树,与G连接的边变为了虚边;而节点M对应的舒张树则和G所当的拓树合并,M和G之间的虚边变成了实边。

巡回执行这有限单操作,直到到根节点,access操作就好了。

这里需要留意的是,当好同样不成并实边操作之后,需要将它们的阿爸pushup,以确保其保障数据的不利。

诸如此类,我们虽取了access的代码:

图片 5图片 6

inline void access(int u) {
    for(int v=0;u;v=u,u=father[u]) 
        Splay(u), rs[u]=v, pushup(u);
}

access

2.makeroot(int u)
具体职能:令节点u成为其所在树的干净节点

当我们需要少单点里的门路信息之时段,应该怎么开?

要是中间一个点不是其他一个接触之上代的言语,它们是未容许当与一个Splay里面的。

这会儿,我们便得makeroot函数把中一个触及打出成根节点了。执行完access(u)操作之后,u会变成所在Splay深度最可怜的触及;然后就待把整棵树翻转,u就是整棵树的根了。

代码如下:

图片 7图片 8

inline void makeroot(int u) {
    access(u); Splay(u); reverse(u);
}

makeroot

 3.split(int u,int
v) 具体效果:把节点u到节点v间的门路压入到一个Splay中

 有矣makeroot之后,split变得最佳简单:

图片 9图片 10

inline void split(int u,int v) {
    makeroot(u); access(v); Splay(v);
}

split

4.findroot(int u)
具体职能:查询该节点所在树的清节点编号

 主要以为判断连通性。

图片 11图片 12

inline int findroot(int u) {
    access(u); Splay(u); pushdown(u);
    while(ls[u]) pushdown(u),u=ls[u];
    return u;
}

findroot

 5.link(int u,int
v)

 当u-v不连过渡时,连一条u到v的轻边。

图片 13图片 14

inline void link(int u,int v) {
    makeroot(u);
    if(findroot(v)!=u) 
        father[u]=v;
}

link

 6.cut(int
u,int v)

 根据LCT的习性,我们可窥见,当makeroot(u),access(v)之后,如果在边u-v,必须满足以下规则:

(1)u-v联通

(2)u-v在一如既往条Splay里发父子关系

(3)u-v在Splay的中序遍历中互相邻

这样判断是否来u-v的逻辑语句就到位了,直接删除即可。

代码如下:

图片 15图片 16

inline void cut(int u,int v) {
    makeroot(u);
    if(findroot(v)==u && father[u]==v && rs[u]==0)
        father[u]=ls[v]=0,pushup(v);
}

cut

dr[x].y = r.y – dr[r.u].y + dr[r.v].y;      即 x->y <==>
u->v – u->x + v->y 如下图:

7. 伸展树

这个伸展树比一般Splay特殊一些。它的判根、rotate操作以及Splay操作前的pushall函数需要留意一下。

图片 17图片 18

int val[MAXN],ls[MAXN],rs[MAXN],father[MAXN],orsum[MAXN],size[MAXN],rev[MAXN];
inline bool isroot(int u) {
    return ls[father[u]]!=u && rs[father[u]]!=u;
}
inline void pushup(int u) {
    orsum[u]=val[u]^orsum[ls[u]]^orsum[rs[u]];
    size[u]=1+size[ls[u]]+size[rs[u]];
}
inline void reverse(int u) {
    if(u) {
        swap(ls[u],rs[u]);
        rev[u]^=1;
    }
}
inline void pushdown(int u) {
    if(rev[u]) {
        reverse(ls[u]);
        reverse(rs[u]);
        rev[u]^=1;
    }
}
inline void rotate(int S) { //风格比较清奇,凑活看吧qaq
    int u=father[S]; if(father[u]) { if(ls[father[u]]==u) ls[father[u]]=S; else if(rs[father[u]]==u) rs[father[u]]=S; } 
    father[S]=father[u]; father[u]=S;
    if(ls[u]==S) {
        if(rs[S]) father[rs[S]]=u; ls[u]=rs[S]; rs[S]=u;
    }
    else {
        if(ls[S]) father[ls[S]]=u; rs[u]=ls[S]; ls[S]=u;
    }
    pushup(u); pushup(S);
}
void pushall(int u) {
    if(!isroot(u)) {
        pushall(father[u]);
        pushdown(father[u]);
    }
}
inline void Splay(int u) {
    pushall(u); pushdown(u); //执行操作之前先pushdown.当然也可以手写栈替代系统栈 
    while(!isroot(u)) {
        if(isroot(father[u]))
            rotate(u);
        else if((ls[father[u]]==u) == (ls[father[father[u]]]==father[u])) 
            rotate(father[u]), rotate(u);
        else 
            rotate(u), rotate(u);
    }
}

View Code

图片 19

 


立刻书还要小心数据可能未是按时间顺序输入的,要举行一个排序,然后又遵照原的各个输出。

老三、模板题目

style=”font-family: Microsoft YaHei; font-size: 16px”>洛谷3690
【模板】Link Cut
Tree

style=”font-family: Microsoft YaHei; font-size: 16px”>给定n个点及每个点之权值,要而处理接下去的m个操作。操作发生4种植。操作从0到3编号。点起1交n编号。

style=”font-family: Microsoft YaHei; font-size: 16px”>0:后接少只整数(x,y),代表了解从x到y的路上之触发的权值的xor和。保证x到y是联通的。

style=”font-family: Microsoft YaHei; font-size: 16px”>1:后连少单整数(x,y),代表连接x到y,若x到y已经联通虽然任需连续。

style=”font-family: Microsoft YaHei; font-size: 16px”>2:后接少只整数(x,y),代表去边(x,y),不保险证边(x,y)存在。

style=”font-family: Microsoft YaHei; font-size: 16px”>3:后搭少独整数(x,y),代表将点x上的权值变成y。

即时是同样道裸模板题(其实为尚无呀还扑朔迷离的操作了,大概就是是这么回事)

图片 20图片 21

/*
716ms/4835K
多维护了一个size
*/ 
#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN=300006;
int val[MAXN],ls[MAXN],rs[MAXN],father[MAXN],orsum[MAXN],size[MAXN],rev[MAXN];
inline bool isroot(int u) {
    return ls[father[u]]!=u && rs[father[u]]!=u;
}
inline void pushup(int u) {
    orsum[u]=val[u]^orsum[ls[u]]^orsum[rs[u]];
    size[u]=1+size[ls[u]]+size[rs[u]];
}
inline void reverse(int u) {
    if(u) {
        swap(ls[u],rs[u]);
        rev[u]^=1;
    }
}
inline void pushdown(int u) {
    if(rev[u]) {
        reverse(ls[u]);
        reverse(rs[u]);
        rev[u]^=1;
    }
}
inline void rotate(int S) {
    int u=father[S]; if(father[u]) { if(ls[father[u]]==u) ls[father[u]]=S; else if(rs[father[u]]==u) rs[father[u]]=S; } 
    father[S]=father[u]; father[u]=S;
    if(ls[u]==S) {
        if(rs[S]) father[rs[S]]=u; ls[u]=rs[S]; rs[S]=u;
    }
    else {
        if(ls[S]) father[ls[S]]=u; rs[u]=ls[S]; ls[S]=u;
    }
    pushup(u); pushup(S);
}
void pushall(int u) {
    if(!isroot(u)) {
        pushall(father[u]);
        pushdown(father[u]);
    }
}
inline void Splay(int u) {
    pushall(u); pushdown(u);
    while(!isroot(u)) {
        if(isroot(father[u]))
            rotate(u);
        else if((ls[father[u]]==u) == (ls[father[father[u]]]==father[u])) 
            rotate(father[u]), rotate(u);
        else 
            rotate(u), rotate(u);
    }
}
inline void access(int u) {
    for(int v=0;u;v=u,u=father[u]) 
        Splay(u), rs[u]=v, pushup(u);
}
inline void makeroot(int u) {
    access(u); Splay(u); reverse(u);
}
inline int findroot(int u) {
    access(u); Splay(u); pushdown(u);
    while(ls[u]) pushdown(u),u=ls[u];
    return u;
}
inline void split(int u,int v) {
    makeroot(u); access(v); Splay(v);
}
inline void link(int u,int v) {
    makeroot(u);
    if(findroot(v)!=u) 
        father[u]=v;
}
inline void cut(int u,int v) {
    makeroot(u);
    if(findroot(v)==u && father[u]==v && rs[u]==0)
        father[u]=ls[v]=0,pushup(v);
}
inline int read() {
    char ch=getchar(); int ret=0; while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') ret=ret*10+(ch-'0'), ch=getchar(); return ret;
}
int main() {
    int n=read(),m=read(),opt,x,y;
    for(int i=1;i<=n;i++)
        val[i]=orsum[i]=read(),size[i]=1;
    while(m--) {
        opt=read(); x=read(); y=read();
        if(opt==0)
            split(x,y), printf("%d %d\n",orsum[y],size[y]);
        else if(opt==1)
            link(x,y);
        else if(opt==2)
            cut(x,y);
        else access(x), Splay(x), val[x]=y, pushup(x);
    }
}

View Code

 

style=”font-family: Microsoft YaHei; font-size: 16px”>洛谷3203
BZOJ2002
[HNOI2010]弹飞绵羊

style=”font-family: Microsoft YaHei; font-size: 16px”>某天,Lostmonkey发明了平栽最佳弹力装置,为了在外的绵羊朋友面前显摆,他约小绵羊一起玩耍个戏。游戏一样发端,Lostmonkey在地上沿着一长直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装时,它见面于后弹ki步,达到第i+ki个装,若未设有第i+ki个装,则绵羊被弹飞。绵羊想知道当它打第i单装起步时,被弹几次于后会见给弹飞。为了使得游戏还好玩,Lostmonkey可以修改某弹力装置的弹力系数,任何时候弹力系数均为刚刚整数。

style=”font-family: Microsoft YaHei; font-size: 16px”>第一执行包含一个平头n,表示地上发n个装置,装置的号码从0到n-1。

style=”font-family: Microsoft YaHei; font-size: 16px”>接下来一行来n个正整数,依次为那n个装的开始弹力系数。

style=”font-family: Microsoft YaHei; font-size: 16px”>第三实施有一个正整数m, style=”font-family: Microsoft YaHei; font-size: 16px”>接下来m行每行至少发生少单数i、j,若i=1,你而出口从j出发被弹几破后让弹飞,若i=2则还见面还输入一个正整数k,表示第j只弹力装置的系数为改成k。

style=”font-family: Microsoft YaHei; font-size: 16px”>数据范围:n<=200000,m<=100000。

顿时道题非常容易转化成LCT的花样。第i个点以及第i+k个点之间连边,每一样涂鸦修改才待cut&link一总体,被弹的次数可为此size来保障;

建筑一个码吧n+1的节点代表为弹飞的区域,把持有i+k>n的无尽连到这里,每次查询size[j~n+1]-1即可。

图片 22图片 23

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN=300006;
int val[MAXN],ls[MAXN],rs[MAXN],father[MAXN],size[MAXN],rev[MAXN];
inline bool isroot(int u) {
    return ls[father[u]]!=u && rs[father[u]]!=u;
}
inline void pushup(int u) {
    size[u]=1+size[ls[u]]+size[rs[u]];
}
inline void reverse(int u) {
    if(u) {
        swap(ls[u],rs[u]);
        rev[u]^=1;
    }
}
inline void pushdown(int u) {
    if(rev[u]) {
        reverse(ls[u]);
        reverse(rs[u]);
        rev[u]^=1;
    }
}
inline void rotate(int S) {
    int u=father[S]; if(father[u]) { if(ls[father[u]]==u) ls[father[u]]=S; else if(rs[father[u]]==u) rs[father[u]]=S; } 
    father[S]=father[u]; father[u]=S;
    if(ls[u]==S) {
        if(rs[S]) father[rs[S]]=u; ls[u]=rs[S]; rs[S]=u;
    }
    else {
        if(ls[S]) father[ls[S]]=u; rs[u]=ls[S]; ls[S]=u;
    }
    pushup(u); pushup(S);
}
void pushall(int u) {
    if(!isroot(u)) {
        pushall(father[u]);
        pushdown(father[u]);
    }
}
inline void Splay(int u) {
    pushall(u); pushdown(u);
    while(!isroot(u)) {
        if(isroot(father[u]))
            rotate(u);
        else if((ls[father[u]]==u) == (ls[father[father[u]]]==father[u])) 
            rotate(father[u]), rotate(u);
        else 
            rotate(u), rotate(u);
    }
}
inline void access(int u) {
    for(int v=0;u;v=u,u=father[u]) 
        Splay(u), rs[u]=v, pushup(u);
}
inline void makeroot(int u) {
    access(u); Splay(u); reverse(u);
}
inline int findroot(int u) {
    access(u); Splay(u); pushdown(u);
    while(ls[u]) pushdown(u),u=ls[u];
    return u;
}
inline void split(int u,int v) {
    makeroot(u); access(v); Splay(v);
}
inline void link(int u,int v) {
    makeroot(u);
    if(findroot(v)!=u) 
        father[u]=v;
}
inline void cut(int u,int v) {
    makeroot(u);
    if(findroot(v)==u && father[u]==v && rs[u]==0)
        father[u]=ls[v]=0,pushup(v);
}
inline int read() {
    char ch=getchar(); int ret=0; while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') ret=ret*10+(ch-'0'), ch=getchar(); return ret;
}
int kk[MAXN];
int main() {
    int n=read(),m,opt,x,y;
    for(int i=1;i<=1+n;i++)
        size[i]=1;
    for(int i=1;i<=n;i++) {
        kk[i]=read();
        if(i+kk[i]<=n)
            link(i,i+kk[i]);
        else link(i,n+1);
    }
    m=read();
    while(m--) {
        opt=read(); x=read(); x++;
        if(opt==1)
            split(x,n+1), printf("%d\n",size[n+1]-1);
        else {
            y=read();
            if(y!=kk[x]) 
                cut(x,(x+kk[x]>n?n+1:x+kk[x])), kk[x]=y, link(x,(x+kk[x]>n?n+1:x+kk[x]));
        }
    }
}

View Code

 洛谷1501
[国家集训队] Tree
II

style=”font-family: Microsoft YaHei; font-size: 16px”>一棵n个点的扶植,每个点之初始权值为1。对于当下棵树生q个操作,每个操作为以下四种植操作有:

  • style=”font-family: Microsoft YaHei; font-size: 16px”>+ u v c:将u到v的门道上之触发之权值都添加自然数c;

  • style=”font-family: Microsoft YaHei; font-size: 16px”>- u1 v1 u2 v2:将树中原有的度(u1,v1)删除,加入一长新边(u2,v2),保证操作完以后还是千篇一律株树;

  • style=”font-family: Microsoft YaHei; font-size: 16px”>* u v c:将u到v的路上之触发之权值都趁着直达自数c;

  • style=”font-family: Microsoft YaHei; font-size: 16px”>/ u v:询问u到v的路线上的触及的权值和,求出答案于51061底余数。

    style=”font-family: Microsoft YaHei; font-size: 16px”>数据范围:1<=n,q<=10^5,0<=c<=10^4。

LCT本身非常简短,甚至还不需判连通性

及时道题的难题就在于pushdown的处理。

细节:需要注意51657^2会爆int,需要因此unsigned

还有:断注意区间乘操作可以乘0!血之训诫qaq

图片 24图片 25

#include <iostream>
#include <cstdio>

using namespace std;

const unsigned int MAXN=300035;
const unsigned int PYZ=51061;

unsigned int val[MAXN],father[MAXN],ls[MAXN],rs[MAXN],rev[MAXN],sum[MAXN];
unsigned int taga[MAXN],tagc[MAXN],size[MAXN];

inline bool isroot(int u) {
    return ls[father[u]]!=u && rs[father[u]]!=u;
}
inline void pushup(int u) {
    sum[u]=val[u]+sum[ls[u]]+sum[rs[u]]; sum[u]%=PYZ;
    size[u]=1+size[ls[u]]+size[rs[u]];
}
inline void reverse(int u) {
    if(u) {
        rev[u]^=1;
        swap(ls[u],rs[u]);
    }
}
inline void pusha(int u,int c) {
    taga[u]+=c, taga[u]%=PYZ;
    val[u]+=c, val[u]%=PYZ;
    sum[u]+=(c*size[u])%PYZ, sum[u]%=PYZ;
}
inline void pushc(int u,int c) {
    taga[u]*=c, taga[u]%=PYZ;
    val[u]*=c, val[u]%=PYZ;
    sum[u]*=c, sum[u]%=PYZ;
    tagc[u]*=c, tagc[u]%=PYZ;
}
inline void pushdown(int u) {
    if(rev[u]) {
        reverse(ls[u]);
        reverse(rs[u]);
        rev[u]=0;
    }
    if(tagc[u]!=1) 
        pushc(ls[u],tagc[u]), pushc(rs[u],tagc[u]), tagc[u]=1;
    if(taga[u])
        pusha(ls[u],taga[u]), pusha(rs[u],taga[u]), taga[u]=0;
}
inline void rotate(int S) {
    int u=father[S]; if(father[u]) { if(ls[father[u]]==u) ls[father[u]]=S; else if(rs[father[u]]==u) rs[father[u]]=S; }
    father[S]=father[u]; father[u]=S;
    if(ls[u]==S) {
        if(rs[S]) father[rs[S]]=u; ls[u]=rs[S]; rs[S]=u;
    }
    else {
        if(ls[S]) father[ls[S]]=u; rs[u]=ls[S]; ls[S]=u;
    }
    pushup(u); pushup(S);
}
void pushall(int u) {
    if(!isroot(u)) {
        pushall(father[u]);
        pushdown(father[u]);
    }
}
inline void Splay(int u) {
    pushall(u); pushdown(u);
    while(!isroot(u)) {
        if(isroot(father[u]))
            rotate(u);
        else if((ls[father[u]]==u) == (ls[father[father[u]]]==father[u]))
            rotate(father[u]), rotate(u);
        else rotate(u), rotate(u);
    }
    pushup(u);
}
inline int kth(int u,int k) {
    if(k<=size[ls[k]])
        return kth(ls[u],k);
    else if(k==size[ls[k]]+1)
        return u;
    else return kth(rs[u],k-size[ls[k]]-1);
}
inline void access(int u) {
    for(int v=0;u;v=u,u=father[u]) 
        Splay(u), rs[u]=v, pushup(u);
}
inline void makeroot(int u) {
    access(u); Splay(u); reverse(u);
}
inline int findroot(int u) {
    access(u); Splay(u); while(ls[u]) pushdown(u), u=ls[u]; return u;
}
inline void split(int u,int v) {
    makeroot(u); access(v); Splay(v);
}
inline void link(int u,int v) {
    makeroot(u); father[u]=v;
}
inline void cut(int u,int v) {
    split(u,v); ls[v]=father[u]=0, pushup(v);
}
inline int read() {
    char ch=getchar(); while(ch!='+' && ch!='-' && ch!='*' && ch!='/') ch=getchar();
    getchar(); if(ch=='+') return 1;  if(ch=='-') return 2;  if(ch=='*') return 3; return 4;
}
int main() {
    int n,q,op,x,y,z; scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) {
        size[i]=tagc[i]=val[i]=sum[i]=1;
        taga[i]=0; 
    }
    for(int i=1;i<n;i++)
        scanf("%d%d",&x,&y) ,link(x,y);
    while(q--) {
        op=read();
        if(op==1) {
            scanf("%d%d%d",&x,&y,&z);
            split(x,y); pusha(y,z);
        }
        else if(op==2) {
            scanf("%d%d",&x,&y); cut(x,y);
            scanf("%d%d",&x,&y); link(x,y);
        }
        else if(op==3) {
            scanf("%d%d%d",&x,&y,&z);
            split(x,y); pushc(y,z);
        }
        else {
            scanf("%d%d",&x,&y);
            split(x,y); printf("%d\n",(int)sum[y]%51061);
        }
    }
}

View Code

 

style=”font-family: Microsoft YaHei; font-size: 16px”>洛谷2173
BZOJ2816
[ZJOI2012] 网络

style=”font-family: Microsoft YaHei; font-size: 16px”>有一个凭为图G,每个点有个权值,每条边有一个颜料。这个无往图满足以下简单只尺码:

  1. style=”font-family: Microsoft YaHei; font-size: 16px”>对于随意节点连出的限度中,相同颜色之限不超两条。

  2. style=”font-family: Microsoft YaHei; font-size: 16px”>图中不在同色的缠绕,同色的环指相同颜色的无尽做的环抱。

    style=”font-family: Microsoft YaHei; font-size: 16px”>在是图及,你要是支持以下三种植操作:

  3. style=”font-family: Microsoft YaHei; font-size: 16px”>修改一个节点的权值。

  4. style=”font-family: Microsoft YaHei; font-size: 16px”>修改一长长的边的水彩。

  5. style=”font-family: Microsoft YaHei; font-size: 16px”>查询由颜色c的度做的图中,所有或当节点u到节点v之间的简易路径上的节点的权值的绝可怜价值。

style=”font-family: Microsoft YaHei; font-size: 16px”>输出格式

  1. style=”font-family: Microsoft YaHei; font-size: 16px”>对于修改节点权值操作,不欲输出信息。

  2. style=”font-family: Microsoft YaHei; font-size: 16px”>对于修改边的水彩操作,按以下几像样输出:

a)
若无设有连接节点u和节点v的限,输出“No such edge.”。

b)
若修改后未满足条件1,不改边的水彩,并出口“Error 1.”。

c)
若修改后未满足条件2,不改边的水彩,并出口“Error 2.”。

d)
其他情形,成功修改边的水彩,并出口“Success.”。

style=”font-family: Microsoft YaHei; font-size: 16px”>输出满足条件的首先修消息即可,即只要以满足b和c,则只是需要输出“Error
1.”。

  1. style=”font-family: Microsoft YaHei; font-size: 16px”>对于查询操作,直接出口一个平头。

    style=”font-family: Microsoft YaHei; font-size: 16px”>数据范围:N ≤
    10000,M ≤ 100000,C ≤ 10,K ≤ 100000。

C最可怜才出10。容易看到,只要把各级一个颜料对应一棵LCT,对于改颜色操作多判一论断有无发生连边,剩下的操作就同裸题差不多了。

管全体数据结构封装一下,搞定。

P.S.记得特判,新边颜色或会见和旧边颜色等!

图片 26图片 27

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN=16384;
const int INF=10000004;

struct tree {
    int father[MAXN],ls[MAXN],rs[MAXN];
    int val[MAXN],sum[MAXN],rev[MAXN],du[MAXN];
    inline bool isroot(int u) { 
        return ls[father[u]]!=u && rs[father[u]]!=u;
    }
    inline void pushup(int u) { 
        sum[u]=max(max(val[u],ls[u]?sum[ls[u]]:-INF),rs[u]?sum[rs[u]]:-INF);
    }
    inline void reverse(int u) { 
        if(u)
            rev[u]^=1, swap(ls[u],rs[u]);
    }
    inline void pushdown(int u) { 
        if(rev[u])
            reverse(ls[u]), reverse(rs[u]),
            rev[u]=0;
    }
    inline void rotate(int S) { 
        int u=father[S];
        if(father[u]) {
            if(ls[father[u]]==u)
                ls[father[u]]=S;
            else if(rs[father[u]]==u)
                rs[father[u]]=S;
        }
        father[S]=father[u]; father[u]=S;
        if(ls[u]==S) {
            if(rs[S]) father[rs[S]]=u; ls[u]=rs[S]; rs[S]=u;
        }
        else {
            if(ls[S]) father[ls[S]]=u; rs[u]=ls[S]; ls[S]=u;
        }
        pushup(u); pushup(S);
    }
    void pushall(int u) {
        if(!isroot(u))
            pushall(father[u]), pushdown(father[u]);
    }
    inline void Splay(int u) {
        pushall(u); pushdown(u); 
        while(!isroot(u)) {
            if(isroot(father[u]))
                rotate(u);
            else if((ls[father[u]]==u) == (ls[father[father[u]]]==father[u]))
                rotate(father[u]), rotate(u);
            else rotate(u), rotate(u);
        }
    }
    inline void access(int u) {
        for(int v=0;u;v=u,u=father[u])
            Splay(u), rs[u]=v, pushup(u);
    }
    inline void makeroot(int u) {
        access(u); Splay(u); reverse(u);
    }
    inline void split(int u,int v) {
        makeroot(u); access(v); Splay(v);
    }
    inline int findroot(int u) {
        access(u); Splay(u); 
        while(ls[u]) u=ls[u], pushdown(u); return u;
    }
    inline bool link(int u,int v) {
        if(du[u]>1 || du[v]>1) {
            printf("Error 1.\n");
            return false;
        }
        makeroot(u);
        if(findroot(v)!=u) {
            father[u]=v;
            du[u]++, du[v]++;
            return true;
        }
        printf("Error 2.\n");
        return false;
    }
    inline void cut(int u,int v) {
        makeroot(u);
        if(findroot(v)==u && ls[v]==u && rs[u]==0) {
            father[u]=ls[v]=0, pushup(v);
            du[u]--, du[v]--;
        }
    }
}lct[11];

int main() {
    int n,m,c,k,dat,opt,x,y,z;
    scanf("%d%d%d%d",&n,&m,&c,&k);
    for(int i=1;i<=n;i++) {
        scanf("%d",&dat);
        for(int o=0;o<=c;o++)
            lct[o].val[i]=lct[o].sum[i]=dat;
    }
    for(int i=1;i<=m;i++) {
        scanf("%d%d%d",&x,&y,&z);
        lct[z].link(x,y);
    }
    while(k--) {
        scanf("%d",&opt);
        if(opt==0) {
            scanf("%d%d",&x,&y);
            for(int o=0;o<=c;o++) {
                lct[o].access(x), lct[o].Splay(x);
                lct[o].val[x]=y, lct[o].pushup(x);
            }
        }
        else if(opt==1) {
            bool _f,flag=false; int des;
            scanf("%d%d%d",&x,&y,&z);
            lct[z].makeroot(x);
            if(x==lct[z].findroot(y) && lct[z].ls[y]==x && lct[z].rs[x]==0) {
                printf("Success.\n");
                continue;
            }
            for(int o=0;o<=c;o++) {
                if(o==z)
                    continue;
                lct[o].makeroot(x);
                if(x==lct[o].findroot(y) && lct[o].ls[y]==x && lct[o].rs[x]==0)
                    flag=true, des=o;
            }
            if(flag==false) {
                printf("No such edge.\n");
                continue;
            }
            if(lct[z].link(x,y)) {
                lct[des].cut(x,y);
                printf("Success.\n");
            }
        }
        else {
            scanf("%d%d%d",&x,&y,&z);
            lct[x].makeroot(y);
            if(lct[x].findroot(z)==y) {
                lct[x].split(y,z);
                printf("%d\n",lct[x].sum[z]);
            }
            else printf("-1\n");
        }
    }
}

View Code

 


 

 

季、维护子树信息——LCT扩展

LCT的基本以都详尽地阐述清楚了。

但当遇一些特别的和培养系的题目时,我们发现未可知因此LCT来缓解问题。

斯时就需要部分更加高档的技能了。

style=”font-family: Microsoft YaHei; font-size: 16px”>洛谷4219
BZOJ4530
[BJOI2014]大融合

style=”font-family: Microsoft YaHei; font-size: 16px”>给定n个点,进行Q次操作,操作发生些许种植:

A x y
:在x,y之间并一漫长边,保证x,y不接

Q x y
:求通过边(x,y)的概括路径数量,保证有边(x,y)

style=”font-family: Microsoft YaHei; font-size: 16px”>N,Q<=10^5

当下是LCT最精的一个力量:对子树信息的维护。

咱俩可窥见,事实上LCT臃肿的代码里,真正涉及到轻重边切换的地方很少,事实上只有access和link两单地方。

因为这个开吗条例,我们得以起来一个sizex数组表示该虚子树的分寸之和,我们即便得轻松和了及时道题。

图片 28图片 29

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN=100006;

int size[MAXN],sizex[MAXN],ls[MAXN],rs[MAXN],father[MAXN],rev[MAXN];

inline bool isroot(int u) {
    return ls[father[u]]!=u && rs[father[u]]!=u;
}
inline void reverse(int u) {
    if(u)
        swap(ls[u],rs[u]), rev[u]^=1;
}
inline void pushdown(int u) {
    if(rev[u])
        reverse(ls[u]), reverse(rs[u]), rev[u]=0;
}
inline void pushup(int u) {
    size[u]=1+size[ls[u]]+sizex[ls[u]]+size[rs[u]]+sizex[rs[u]];
}
inline void rotate(int S) {
    int u=father[S]; if(father[u]) {
        if(ls[father[u]]==u) ls[father[u]]=S;
        else if(rs[father[u]]==u) rs[father[u]]=S;
    }
    father[S]=father[u]; father[u]=S;
    if(ls[u]==S) {
        if(rs[S]) father[rs[S]]=u; ls[u]=rs[S]; rs[S]=u;
    }
    else {
        if(ls[S]) father[ls[S]]=u; rs[u]=ls[S]; ls[S]=u;
    }
    pushup(u); pushup(S);
}
void pushall(int u) {
    if(!isroot(u)) 
        pushall(father[u]), pushdown(father[u]);
}
inline void Splay(int u) {
    pushall(u); pushdown(u);
    while(!isroot(u)) {
        if(isroot(father[u]))
            rotate(u);
        else if((ls[father[u]]==u) == (ls[father[father[u]]]==father[u]))
            rotate(father[u]), rotate(u);
        else rotate(u), rotate(u);
    }
}
inline void access(int u) {
    for(int v=0;u;v=u,u=father[u]) {
        Splay(u);
        if(rs[u])
            sizex[u]+=size[rs[u]]+sizex[rs[u]];
        rs[u]=v;
        if(v)
            sizex[u]-=size[v]+sizex[v];
        pushup(u);
    }
}
inline void makeroot(int u) {
    access(u); Splay(u); reverse(u);
}
inline void split(int u,int v) {
    makeroot(u); access(v); Splay(v);
}
inline void link(int u,int v) {
    split(u,v); father[u]=v; sizex[v]+=size[u]+sizex[u];
}
inline char read() {
    char ch=getchar(); while(ch!='A' && ch!='Q') ch=getchar(); return ch;
}
int main() {
    int n,q,x,y; char ch; scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        size[i]=1;
    while(q--) {
        ch=read();
        if(ch=='A') {
            scanf("%d%d",&x,&y);
            link(x,y);
        }
        else {
            scanf("%d%d",&x,&y);
            split(x,y);
            printf("%lld\n",1ll*(size[x]+sizex[x])*(size[y]+sizex[y]-size[x]-sizex[x]));
        }
    }
}

View Code


代码:

图片 30图片 31

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 40100

int fa[N],q;

struct DR
{
    int x,y;
}dr[N],to[27];

struct ROAD
{
    int u,v;
    int x,y;
}road[N];

struct QUERY
{
    int a,b,time;
    int id,res;
}query[N];

void makeset(int n)
{
    for(int i=1;i<=n;i++)
    {
        fa[i] = i;
        dr[i].x = dr[i].y = 0;
    }
}

int findset(int x)
{
    if(x != fa[x])
    {
        int tmp = fa[x];
        fa[x] = findset(fa[x]);
        dr[x].x += dr[tmp].x;
        dr[x].y += dr[tmp].y;
    }
    return fa[x];
}

void unionset(int index)  //合并第index条边
{
    ROAD r = road[index];
    int x = findset(r.u);
    int y = findset(r.v);
    if(x == y)
        return;
    fa[x] = y;
    dr[x].x = r.x - dr[r.u].x + dr[r.v].x;   // x->y <==> u->v - u->x + v->y
    dr[x].y = r.y - dr[r.u].y + dr[r.v].y;   
}

int cmp1(QUERY ka,QUERY kb)
{
    return ka.time<kb.time;
}

int cmp2(QUERY ka,QUERY kb)
{
    return ka.id<kb.id;
}

void InitDirection()
{
    to['E'-'A'].x = 1;
    to['E'-'A'].y = 0;
    to['W'-'A'].x = -1;
    to['W'-'A'].y = 0;
    to['N'-'A'].x = 0;
    to['N'-'A'].y = 1;
    to['S'-'A'].x = 0;
    to['S'-'A'].y = -1;
}

void read()
{
    int n,m,i,dis;
    char ss[4];
    InitDirection();
    scanf("%d%d",&n,&m);
    makeset(n);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d %s",&road[i].u,&road[i].v,&dis,ss);
        road[i].x = dis*(to[ss[0]-'A'].x);
        road[i].y = dis*(to[ss[0]-'A'].y);
    }
    scanf("%d",&q);
    for(i=1;i<=q;i++)
    {
        scanf("%d%d%d",&query[i].a,&query[i].b,&query[i].time);
        query[i].id = i;
    }
    sort(query+1,query+q+1,cmp1);
}

void solve()
{
    int i,j;
    j=1;
    for(i=1;i<=q;i++)
    {
        for(;j<=query[i].time;j++)
        {
            unionset(j);
        }
        if(findset(query[i].a) != findset(query[i].b))
            query[i].res = -1;
        else
            query[i].res = abs(dr[query[i].a].x-dr[query[i].b].x) + abs(dr[query[i].a].y-dr[query[i].b].y);
    }
    sort(query+1,query+q+1,cmp2);
    for(i=1;i<=q;i++)
        cout<<query[i].res<<endl;
}

int main()
{
    read();
    solve();
    return 0;
}

View Code