LCT感性瞎扯

xtx1092515503 · 2020-01-30 18:45:54 · 个人记录

大家好，感谢那万恶的冠状病毒，我现在无事可做，只好跑过来瞎扯LCT辣。

I.LCT可以干什么？

动态树问题，
是近几年在OI中兴起的一种新型问题，
是一类要求维护一个有根树森林，
支持对树的分割，合并等操作的问题。

由Robert E Tarjan为首的科学家们
提出解决算法Link-Cut Tree，简称LCT。
                                    ——《百度百科》

算了，看看就行。

我们唯一知道的就是，你们的大毒瘤，那个发明强连通分量算法、HLPP、splay、离线LCA算法的Tarjan，他又跑来祸害咱们了！

附上高清大图

通俗点说，它支持你将一棵树一刀两断，也支持你把两棵树嫁接在一起（无性生殖？），还支持你从树上扯下来一条路径在上面搞事情。

或者换句话说，它就是（动态树剖+并查集+平衡树），再加上一堆奇妙的特性。

这么酷炫的吗！！！

好的那我们就开始吧。

II.前置芝士

splay：必修，特别是区间操作（fhq treap亦可）

树剖：选修

并查集：必修

线段树：必修

III.思想

我们常说的树链剖分，实际上是重链剖分。它还有两个兄弟，长链剖分与实链剖分。

这仨家伙有一个共同点：毒瘤可以把一棵树按照一些规则剁成几条不相交的路径。并且，这些路径上的点按照深度递增，不存在两个相同深度的点处在同一条路径上。

例如重链剖分，就是每个点和它所有子节点中size最大的点在同一条链上。

而长链剖分，我没学过，咱也不敢瞎说

LCT运用的就是里面最灵活的实链剖分。我们常见的重链剖分，一旦剖分完成，是不可以再改变链的构成的，除非你暴力重构树。

但是，实链剖分，你就可以任意指定一个点的实边和实儿子。当然咯，这么方便也不是没有坏处，在极端情况下，实链剖分是O(n)的，不像重链剖分是严格的O(\log n)。

因此，我们就将实链剖分和灵活的splay结合在一起，得到了均摊O(\log)的LCT。

我们将每一条实链，扔进一颗splay中维护。这棵splay以深度为键值，深度越大排名越靠后。

当然咯，因为splay的结构，我们没有必要建出一棵一棵的splay出来。它还是可以保有一个完整的结构的。只不过，对于某棵splay的树根，它有一个父亲，那是原树中它的父亲；但是它的父亲尽管有这个儿子，但它却不认！

例如这个剖分：

在以E为根的那棵splay中，E认了一个父亲，D。但是，D却不认E这个儿子。它唯一承认的儿子，是F，它splay中的右儿子。当然，F也承认D这个父亲。

但是，splay不一定只有一种构造。也有可能，F是splay的根，而D是它的左儿子。这个时候，D和F仍然互相承认，D还是不承认E，但是E承认D。

因此，我们可以看出，不管哪个儿子，都是承认与父亲的关系的。但是，父亲只承认与实儿子的关系（尽管这个实儿子有可能在splay中成为了它的父亲甚至有可能离他很远很远）。

因此我们便解锁了LCT中一个最重要的性质：实边认父也认子，虚边认父不认子。

IV.约定

效果：将节点x到ROOT这条路径上的所有边设成实边（并自动把其他边设成虚边），并且扔到一个splay里面。

例：

怎么实现呢？

这个时候，我们就要回想起splay的经典操作splay：将一个x旋转到它所在的splay的root。

这个时候，我们就可以向fa转移了（因为x是root，它的父亲一定处在不同的splay中）。

因为x的深度一定大于fa的深度，所以如果我们将fa也splay到它所属的splay的根，则x可以直接设成fa的右儿子（在设的同时，fa原本的右儿子，原来是实儿子，被直接断成了虚儿子，认父不认子，成了家庭餐具了；反而，原来认子不认父的x，现在fa重新承认了x这个儿子，当然x也一直承认着fa，因此这便成为了新的实边）。

看一下代码：

inline void access(int x){
    for(register int y=0;x;x=t[y=x].fa)
        splay(x),rson=y,pushup(x);
}

就是将x转到根；将x的右儿子设成y；将x变成新的y（在x的父亲splay时继续更新）。

至于这个pushup，是更新的函数，类似于线段树的pushup。

效果：将x设为这棵树的ROOT（注意不是splay的root）！

先上代码：

inline void makeroot(int x){
    access(x),splay(x),REV(x);
}

效果：将x到ROOT的路径打包成一个splay，找到x的ROOT，并将ROOT转到root。

先上代码：

inline int findroot(int x){
    access(x),splay(x);
    while(lson)pushdown(x),x=lson;
    splay(x);
    return x;
}

可以类比冰茶姬的找父亲操作。

效果：将x到y路径上的所有点打包成一个splay，并令y为root。

代码：

inline bool split(int x,int y){
    if(findroot(x)!=findroot(y))return false;
    makeroot(x),access(y),splay(y);
    return true;
}

如果x和y不在同一颗树中，显然操作不合法，直接退出；

否则，把x设成新ROOT，这样子再access一下就抽出了ROOT-y的路径。由于x就是ROOT，这就是x到y的路径。然后再将y splay到root，保证深度。

效果：在节点x,y间连一条边。

代码：

inline bool link(int x,int y){
    makeroot(x);
    if(findroot(y)==x)return false;
    t[x].fa=y;
    return true;
}

把x转到ROOT；如果发现x,y已经连通（在同一棵子树中），忽略之；否则，将x的父亲设成y，相当于连一条虚边。

效果：断掉节点x,y间的边。

代码：

inline bool cut(int x,int y){
    makeroot(x);
    if(findroot(y)!=x||t[y].fa!=x||t[y].ch[0])return false;
    t[x].ch[1]=t[y].fa=0;
    pushup(x);
    return true;
}

这是仅次于access最重点的一个，也是仅次于access最难的那个。

先让x为ROOT；如果findroot(y)\neq x，即它们不在同一棵树中，忽略之；如果t[y].fa\neq x，则显然它们之间不可能有边，因为findroot后，x和y处于同一棵splay中，且x是根（不明白的马上转回去看findroot），则深度差为1的点对(x,y)必然紧贴；就算这两点都满足，如果y有左儿子，则x和y仍然没有真正地紧贴，它们之间也不可能有边；这些都是需要忽略的。

之后，就是断边了。因为这时x为根，且x的深度小于y，因此x的右儿子一定就是y。

VI.汇总

struct LCT{
    int fa,ch[2],val,sum;
    bool rev;
}t[100100];
inline int identify(int x){
    if(x==t[t[x].fa].ch[0])return 0;
    if(x==t[t[x].fa].ch[1])return 1;
    return -1;
}
inline void pushup(int x){
    t[x].sum=t[lson].sum^t[rson].sum^t[x].val;
}
inline void REV(int x){
    t[x].rev^=1,swap(t[x].ch[0],t[x].ch[1]);
}
inline void pushdown(int x){
    if(!t[x].rev)return;
    if(lson)REV(lson);
    if(rson)REV(rson); 
    t[x].rev=0;
}
inline void rotate(int x){
    register int y=t[x].fa;
    register int z=t[y].fa;
    register int dirx=identify(x);
    register int diry=identify(y);
    register int b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[y].fa=x,t[x].ch[!dirx]=y;
    pushup(y),pushup(x);
}
inline void pushall(int x){//pushdown the nodes in the route from x to root
    if(identify(x)!=-1)pushall(t[x].fa);
    pushdown(x);
}
inline void splay(int x){//splay x to the root
    pushall(x);
    while(identify(x)!=-1){
        register int fa=t[x].fa;
        if(identify(fa)==-1)rotate(x);
        else if(identify(x)==identify(fa))rotate(fa),rotate(x);
        else rotate(x),rotate(x);
    }
}
inline void access(int x){//pull out all the nodes in the route from x to the ROOT, and form a splay
    for(register int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}
inline void makeroot(int x){//make x the new ROOT
    access(x),splay(x),REV(x);
}
inline int findroot(int x){//find the ROOT of x, and make ROOT the root
    access(x),splay(x);
    while(lson)pushdown(x),x=lson;
    splay(x);
    return x;
}
inline bool split(int x,int y){//pull out the route from x to y and form a splay rooted y; if there isn't such route,return false
    if(findroot(x)!=findroot(y))return false;
    makeroot(x),access(y),splay(y);
    return true;
}
inline bool link(int x,int y){//link an edge between x and y; if they have already connected before, return false.
    makeroot(x);
    if(findroot(y)==x)return false;
    t[x].fa=y;
    return true;
}
inline bool cut(int x,int y){//cut the edge between x and y; if there isn't such edge, return false
    makeroot(x);
    if(findroot(y)!=x||t[y].fa!=x||t[y].ch[0])return false;
    t[x].ch[1]=t[y].fa=0;
    pushup(x);
    return true;
}

注意到几处与普通splay的不同：

1.在identify函数判断左儿子还是右儿子时，如果return -1，则说明x是root。

2.在splay时调用pushall函数，从上到下递归地pushdown。

3.在rotate时，在多个可能为root或者该节点不存在的地方进行特判。

VII.例题

I.【模板】Link Cut Tree （动态树）

直接把那份模板加个头尾就能过。

II.[SDOI2008]洞穴勘测

也是近似的模板题，甚至比模板还要简单，连维护pushup都不需要。

主要是为了多敲几遍熟悉代码。

代码：

#include<bits/stdc++.h>
using namespace std;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
int n,m;
struct LCT{
    int ch[2],fa,rev;
}t[100100];
int identify(int x){
    if(t[t[x].fa].ch[0]==x)return 0;
    if(t[t[x].fa].ch[1]==x)return 1;
    return -1;
}
void REV(int x){
    swap(lson,rson),t[x].rev^=1;
}
void pushdown(int x){
    if(!t[x].rev)return;
    if(lson)REV(lson);
    if(rson)REV(rson);
    t[x].rev=0;
}
void rotate(int x){
    int y=t[x].fa;
    int z=t[y].fa;
    int dirx=identify(x);
    int diry=identify(y);
    int b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[x].ch[!dirx]=y,t[y].fa=x;
}
void pushall(int x){
    if(identify(x)!=-1)pushall(t[x].fa);
    pushdown(x);
}
void splay(int x){
    pushall(x);
    while(identify(x)!=-1){
        int fa=t[x].fa;
        if(identify(fa)==-1)rotate(x);
        else if(identify(x)==identify(fa))rotate(fa),rotate(x);
        else rotate(x),rotate(x);
    }
}
void access(int x){
    for(int y=0;x;x=t[y=x].fa)splay(x),rson=y;
}
void makeroot(int x){
    access(x),splay(x),REV(x);
}
int findroot(int x){
    access(x),splay(x);
    while(lson)pushdown(x),x=lson;
    splay(x);
    return x;
}
void split(int x,int y){
    makeroot(x),access(y),splay(y);
}
void link(int x,int y){
    makeroot(x);
    t[x].fa=y;
}
void cut(int x,int y){
    split(x,y);
    t[x].fa=t[y].ch[0]=0;
}
bool connected(int x,int y){
    return findroot(x)==findroot(y);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;i++){
        char s[10];
        scanf("%s%d%d",s,&x,&y);
        if(s[0]=='Q')puts(connected(x,y)?"Yes":"No");
        if(s[0]=='C')link(x,y);
        if(s[0]=='D')cut(x,y);
    }
    return 0;
}

III.[HNOI2010]弹飞绵羊

首先，可以发现，如果从一个装置的目标向这个装置连一条边，并且建立虚拟节点n+1，向所有可以弹飞的装置连边的话，这肯定构成一颗树。

理解就行。然后我们就可以在每个节点统计一个size，并用LCT在改变弹力系数时修改这棵树。则最终答案为：

int ask(int x){
    makeroot(n+1),access(x),splay(x);
    return t[x].sz;
}

显然，答案为当前节点的深度。我们可以打通从x到n+1的路径，然后答案即为这个splay的大小。另，最后答案还要减去1，因为有n+1这个虚拟节点。

代码:

#include<bits/stdc++.h>
using namespace std;
#define lson t[x].ch[0]
#define rson t[x].ch[1] 
int n,m,fa[200100];
struct LCT{
    int ch[2],sz,fa,rev;
}t[200100];
void pushup(int x){
    t[x].sz=t[lson].sz+t[rson].sz+1;
}
void REV(int x){
    t[x].rev^=1,swap(t[x].ch[0],t[x].ch[1]);
}
void pushdown(int x){
    if(!t[x].rev)return;
    if(lson)REV(lson);
    if(rson)REV(rson);
    t[x].rev=0;
}
int identify(int x){
    if(t[t[x].fa].ch[0]==x)return 0;
    if(t[t[x].fa].ch[1]==x)return 1;
    return -1;
}
void rotate(int x){
    int y=t[x].fa;
    int z=t[y].fa;
    int dirx=identify(x);
    int diry=identify(y);
    int b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[x].ch[!dirx]=y,t[y].fa=x;
    pushup(y),pushup(x);
}
void pushall(int x){
    if(identify(x)!=-1)pushall(t[x].fa);
    pushdown(x);
}
void splay(int x){
    pushall(x);
    while(identify(x)!=-1){
        int fa=t[x].fa;
        if(identify(fa)==-1)rotate(x);
        else if(identify(fa)==identify(x))rotate(fa),rotate(x);
        else rotate(x),rotate(x);
    }
}
void access(int x){
    for(int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}
void makeroot(int x){
    access(x),splay(x),REV(x);
}
void split(int x,int y){
    makeroot(x),access(y),splay(y);
}
int findroot(int x){
    access(x),splay(x);
    pushdown(x);
    while(lson)x=lson,pushdown(x);
    splay(x);
    return x;
}
void link(int x,int y){
    makeroot(x),t[x].fa=y;
}
void cut(int x,int y){
    split(x,y),t[x].fa=t[y].ch[0]=0,pushup(y);
}
void change(int x,int y){
    cut(x,fa[x]),link(x,fa[x]=y);
}
int ask(int x){
    makeroot(n+1),access(x),splay(x);
    return t[x].sz;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&fa[i]),fa[i]+=i,fa[i]=min(fa[i],n+1),link(i,fa[i]),t[i].sz=1;
    scanf("%d",&m);
    for(int i=1,t1,t2,t3;i<=m;i++){
        scanf("%d%d",&t1,&t2),t2++;
        if(t1==1)printf("%d\n",ask(t2)-1);
        else scanf("%d",&t3),change(t2,min(t2+t3,n+1));
    }
    return 0;
}

IV.[NOI2014]魔法森林

前三题都是模板，是为了让我们练手的。

这题才是真正的挑战。

首先，一看这题既不加边也不删边，甚至连树都不是，还是道静态题，并且长得还贼像最小生成树，我就纳闷了，这是LCT？

还真是。

我们可以将边按照a排序。之后，我们维护一个关于b权值的动态最小生成树。

具体做法是，建立一个LCT，这个LCT维护的是最大值的下标。之后，按照a递增的顺序遍历所有的边。如果这条边连接了两块尚未被连接的区域，那不要废话直接连；否则，这肯定构成一个环。我们在LCT中split出来这个环在当前MST上的部分，并找到这里面的最大值的位置。如果最大值比当前这条边的b还要大，那么断掉最大值的边并用当前边代替肯定更优。因此我们就这么做。在每加完一条边后，如果当前节点1和节点n是连通的，那么split(1,n)，并将（当前的a+[1-n链上的最大值]）与当前答案取\min。

哦，另外，为了将边权转成点权，我们将每条边视作一个点

核心代码：

for(int i=1;i<=n+m;i++)t[i].val=0,t[i].mx=dsu[i]=i;
for(int i=n+1;i<=n+m;i++)t[i].val=e[i-n].b;
for(int i=1;i<=m;i++){
    if(merge(e[i].x,e[i].y))link(e[i].x,n+i),link(n+i,e[i].y);
    else{
        int pos=split(e[i].x,e[i].y);
        if(t[pos].val<e[i].b)continue;
        cut(pos,e[pos-n].x),cut(pos,e[pos-n].y);
        link(e[i].x,n+i),link(n+i,e[i].y);
    }
    if(find(1)==find(n))res=min(res,e[i].a+t[split(1,n)].val);
}

应该比较好理解不然我怎么能1A

总代码：

#include<bits/stdc++.h>
using namespace std;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
int n,m,dsu[500100],res=0x3f3f3f3f;
int find(int x){
    return dsu[x]==x?x:dsu[x]=find(dsu[x]);
}
bool merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return false;
    dsu[x]=y;
    return true;
}
struct edge{
    int x,y,a,b;
    friend bool operator <(const edge &u,const edge &v){
        return u.a<v.a;
    }
}e[100100];
struct LCT{
    int ch[2],fa,val,mx;
    bool rev;
}t[500100];
void pushup(int x){
    t[x].mx=x;
    if(t[t[x].mx].val<t[t[lson].mx].val)t[x].mx=t[lson].mx;
    if(t[t[x].mx].val<t[t[rson].mx].val)t[x].mx=t[rson].mx;
}
void REV(int x){
    t[x].rev^=1,swap(lson,rson);
}
void pushdown(int x){
    if(!t[x].rev)return;
    if(lson)REV(lson);
    if(rson)REV(rson);
    t[x].rev=false;
}
int identify(int x){
    if(t[t[x].fa].ch[0]==x)return 0;
    if(t[t[x].fa].ch[1]==x)return 1;
    return -1;
}
void rotate(int x){
    int y=t[x].fa;
    int z=t[y].fa;
    int dirx=identify(x);
    int diry=identify(y);
    int b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[x].ch[!dirx]=y,t[y].fa=x;
    pushup(y),pushup(x);
}
void pushall(int x){
    if(identify(x)!=-1)pushall(t[x].fa);
    pushdown(x);
}
void splay(int x){
    pushall(x);
    while(identify(x)!=-1){
        int fa=t[x].fa;
        if(identify(fa)==-1)rotate(x);
        else if(identify(fa)==identify(x))rotate(fa),rotate(x);
        else rotate(x),rotate(x);
    }
}
void access(int x){
    for(int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}
void makeroot(int x){
    access(x),splay(x),REV(x);
}
int findroot(int x){
    access(x),splay(x);
    pushdown(x);
    while(lson)x=lson,pushdown(x);
    splay(x);
    return x;
}
int split(int x,int y){
    makeroot(x),access(y),splay(y);
    return t[y].mx;
}
void link(int x,int y){
    makeroot(x),t[x].fa=y;
}
void cut(int x,int y){
    split(x,y),t[x].fa=t[y].ch[0]=0,pushup(y);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].a,&e[i].b);
    sort(e+1,e+m+1);
    for(int i=1;i<=n+m;i++)t[i].val=0,t[i].mx=dsu[i]=i;
    for(int i=n+1;i<=n+m;i++)t[i].val=e[i-n].b;
    for(int i=1;i<=m;i++){
        if(merge(e[i].x,e[i].y))link(e[i].x,n+i),link(n+i,e[i].y);
        else{
            int pos=split(e[i].x,e[i].y);
            if(t[pos].val<e[i].b)continue;
            cut(pos,e[pos-n].x),cut(pos,e[pos-n].y);
            link(e[i].x,n+i),link(n+i,e[i].y);
        }
        if(find(1)==find(n))res=min(res,e[i].a+t[split(1,n)].val);
    }
    if(res==0x3f3f3f3f)puts("-1");
    else printf("%d\n",res);
    return 0;
}

V.[国家集训队]Tree II

LCT维护这种东西是要比线段树要恶心的多的……毕竟线段树的区间大小是可以直接通过区间左右端点算出的，但是LCT就不行，必须手动维护。并且，线段树的维护是（左儿子+右儿子），但是LCT的维护是（左儿子+自己+右儿子）！

请务必先把线段树模板做掉，关于运算的优先级什么的实在不应该放到这道题里讲吧……

注意细节，比如修改时，乘法tag，加法tag，本身的值，区间的和，都要修改，并且每个修改的方式都还不一样。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=51061;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
int n,q;
struct LCT{
    int ch[2],fa,plu,mul,rev,sum,val,sz;
}t[100100];
int identify(int x){
    if(t[t[x].fa].ch[0]==x)return 0;
    if(t[t[x].fa].ch[1]==x)return 1;
    return -1;
}
void REV(int x){
    t[x].rev^=1,swap(lson,rson);
}
void pushdown(int x){
    if(t[x].rev){
        if(lson)REV(lson);
        if(rson)REV(rson);
        t[x].rev=0;
    }
    if(lson)t[lson].val=(1ll*t[lson].val*t[x].mul+t[x].plu)%mod,t[lson].plu=(1ll*t[lson].plu*t[x].mul+t[x].plu)%mod,t[lson].mul=(1ll*t[lson].mul*t[x].mul)%mod,t[lson].sum=(1ll*t[lson].sum*t[x].mul+1ll*t[x].plu*t[lson].sz)%mod;
    if(rson)t[rson].val=(1ll*t[rson].val*t[x].mul+t[x].plu)%mod,t[rson].plu=(1ll*t[rson].plu*t[x].mul+t[x].plu)%mod,t[rson].mul=(1ll*t[rson].mul*t[x].mul)%mod,t[rson].sum=(1ll*t[rson].sum*t[x].mul+1ll*t[x].plu*t[rson].sz)%mod;
    t[x].plu=0,t[x].mul=1;
}
void pushup(int x){
    t[x].sum=(t[lson].sum+t[rson].sum+t[x].val)%mod;
    t[x].sz=t[lson].sz+t[rson].sz+1;
}
void rotate(int x){
    int y=t[x].fa;
    int z=t[y].fa;
    int dirx=identify(x);
    int diry=identify(y);
    int b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[x].ch[!dirx]=y,t[y].fa=x;
    pushup(y),pushup(x);
}
void pushall(int x){
    if(identify(x)!=-1)pushall(t[x].fa);
    pushdown(x);
}
void splay(int x){
    pushall(x);
    while(identify(x)!=-1){
        int fa=t[x].fa;
        if(identify(fa)==-1)rotate(x);
        else if(identify(fa)==identify(x))rotate(fa),rotate(x);
        else rotate(x),rotate(x);
    }
}
void access(int x){
    for(int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}
void makeroot(int x){
    access(x),splay(x),REV(x);
}
int findroot(int x){
    access(x),splay(x);
    pushdown(x);
    while(lson)x=lson,pushdown(x);
    splay(x);
    return x;
}
void link(int x,int y){
    makeroot(x),t[x].fa=y;
}
int split(int x,int y){
    makeroot(x),access(y),splay(y);
    return t[y].sum;
}
void cut(int x,int y){
    split(x,y),t[x].fa=t[y].ch[0]=0,pushup(y);
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)t[i].val=t[i].mul=t[i].sum=1;
    for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),link(x,y);
    for(int i=1,t1,t2,t3,t4;i<=q;i++){
        char s[10];
        scanf("%s",s);
        if(s[0]=='+')scanf("%d%d%d",&t1,&t2,&t3),split(t1,t2),t[t2].plu=(t[t2].plu+t3)%mod,t[t2].val=(t[t2].val+t3)%mod,t[t2].sum=(1ll*t[t2].sz*t3+t[t2].sum)%mod,pushup(t2);
        if(s[0]=='-')scanf("%d%d%d%d",&t1,&t2,&t3,&t4),cut(t1,t2),link(t3,t4);
        if(s[0]=='*')scanf("%d%d%d",&t1,&t2,&t3),split(t1,t2),t[t2].mul=(1ll*t[t2].mul*t3)%mod,t[t2].val=(1ll*t[t2].val*t3)%mod,t[t2].sum=(1ll*t[t2].sum*t3)%mod,pushup(t2);
        if(s[0]=='/')scanf("%d%d",&t1,&t2),printf("%d\n",split(t1,t2));
    }
    return 0;
}

VI.[SDOI2011]染色

你们知道吗？LCT考的就两个，一个pushup，一个pushdown。

这里就是经典的维护颜色段。在每个节点，我们维护四个值：lc，左端颜色；rc：右端颜色；sc：区间颜色段数；col：当前点的颜色。

然后就是经典的老套路了。

注意！！！在splay翻转时，要同时交换lc和rc！！！如果你做过经典大毒瘤题，应该就没问题了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
int n,m;
struct LCT{
    int ch[2],fa,col,lc,rc,sc,rev,tag;
}t[100100];
int identify(int x){
    if(t[t[x].fa].ch[0]==x)return 0;
    if(t[t[x].fa].ch[1]==x)return 1;
    return -1;
}
void REV(int x){
    t[x].rev^=1,swap(lson,rson),swap(t[x].lc,t[x].rc);
}
void CHANGE(int x,int y){
    t[x].lc=t[x].rc=t[x].col=t[x].tag=y,t[x].sc=1;
}
void pushdown(int x){
    if(t[x].rev){
        if(lson)REV(lson);
        if(rson)REV(rson);
        t[x].rev=0;
    }
    if(t[x].tag){
        if(lson)CHANGE(lson,t[x].tag);
        if(rson)CHANGE(rson,t[x].tag);
        t[x].tag=0;
    }
}
void pushup(int x){
    t[x].sc=1,t[x].lc=t[x].rc=t[x].col;
    if(lson){
        t[x].sc+=t[lson].sc;
        t[x].lc=t[lson].lc;
        if(t[lson].rc==t[x].col)t[x].sc--;
    }
    if(rson){
        t[x].sc+=t[rson].sc;
        t[x].rc=t[rson].rc;
        if(t[rson].lc==t[x].col)t[x].sc--;
    }
}
void rotate(int x){
    int y=t[x].fa;
    int z=t[y].fa;
    int dirx=identify(x);
    int diry=identify(y);
    int b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[x].ch[!dirx]=y,t[y].fa=x;
    pushup(y),pushup(x);
}
void pushall(int x){
    if(identify(x)!=-1)pushall(t[x].fa);
    pushdown(x);
}
void splay(int x){
    pushall(x);
    while(identify(x)!=-1){
        int fa=t[x].fa;
        if(identify(fa)==-1)rotate(x);
        else if(identify(x)==identify(fa))rotate(fa),rotate(x);
        else rotate(x),rotate(x);
    }
}
void access(int x){
    for(int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}
void makeroot(int x){
    access(x),splay(x),REV(x);
}
void link(int x,int y){
    makeroot(x),t[x].fa=y;
}
void split(int x,int y){
    makeroot(x),access(y),splay(y);
}
void change(int x,int y,int z){
    split(x,y),CHANGE(y,z);
}
int query(int x,int y){
    split(x,y);
    return t[y].sc;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x;i<=n;i++)scanf("%d",&x),CHANGE(i,x);
    for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),link(x,y);
    for(int i=1,x,y,z;i<=m;i++){
        char s[10];
        scanf("%s",s);
        if(s[0]=='Q')scanf("%d%d",&x,&y),printf("%d\n",query(x,y));
        else scanf("%d%d%d",&x,&y,&z),change(x,y,z);
    }
    return 0;
}

VII.[SHOI2014]三叉神经树

LCT相较于树剖，最大的优势就是可以把一条链上的东西全整到一个splay里面，不像树剖在多个重链进行合并时会有很大麻烦。更好的是，LCT复杂度是O(n\log n)的，树剖不仅码量大，思路复杂，复杂度还是恶心的O(n\log^2n)。

这题就是典型的树剖被LCT全方面完爆。

首先，这道题要考阅读理解。翻译一下，就是给你一棵树，树上的每个节点要么有三个儿子，要么是叶子。每个叶子初始时有一个或0或1的权值。每个非叶子节点的权值由它三个儿子的权值决定，0和1在它儿子中占比更多的那一个即是它的权值。现在我们每次修改一个叶子的权值，要你输出修改后根的输出。

我们可以发现，在修改一个叶子时，只有叶子到根的这条路径上点会受到影响。并且，影响必定是连续的一段，一旦有一个点没有被修改，那这次修改就到头了。

设一个节点三个儿子的权值和为sum，则如果sum>1，这个节点输出为1；否则，为0。

则每次修改，假设是0改1，只有从叶子到根的一段连续的sum为1的点才会被修改。sum为0的，多一个1的儿子只会让sum变成1，输出还是0；sum为2或3的，更不用说了，sum增加它的权值还是1。只有sum为1的会受到影响。

则我们只需要维护路径上深度最大的非1节点。这样，比它深的所有节点都有修改。

对于我们修改一个叶子节点x时：

令它的父亲为y。则我们access(y)，打通从y到ROOT的路径。

等等，为什么是y？不应该是x吗？

因为x的输入不由sum_x决定，你要是这么access(x)会让x变成普通节点，由它的sum_x决定，而sum_x始终为0。

并且，如果这样的话，我们就不能直接找到x的父亲，因为同一splay中的父亲不一定是真父亲。

我们access(y)后，splay(y)，并找到维护的非1节点的位置，设为id_1。

如果id_1不存在，说明从叶子到根这一整条路径上所有的点都得改，直接在y上打tag。

否则，设z=id_1。则splay(z)后，z的右儿子即是我们修改的目标。我们直接在z的右儿子上打tag，同时更新z的sum。

现在我们来讨论一下怎么维护id。

先上函数：

void pushup(int x){
    if(t[rson].id[1])t[x].id[1]=t[rson].id[1];
    else if(t[x].sum!=1)t[x].id[1]=x;
    else t[x].id[1]=t[lson].id[1];
    if(t[rson].id[2])t[x].id[2]=t[rson].id[2];
    else if(t[x].sum!=2)t[x].id[2]=x;
    else t[x].id[2]=t[lson].id[2];
}

因为深度越大越靠右，我们转移时优先选择右儿子，其次自己，最次左儿子。

至于这个id_2，则是在叶子节点的输入由1转0时用的，因为由1转0只会影响到sum=2的节点。

代码：

#include<bits/stdc++.h>
using namespace std;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
int n,m,in[1501000],ans;
struct LCT{
    int ch[2],id[3],fa,sum,tag,val;
}t[1501000];
int identify(int x){
    if(t[t[x].fa].ch[0]==x)return 0;
    if(t[t[x].fa].ch[1]==x)return 1;
    return -1;
}
void pushup(int x){
    if(t[rson].id[1])t[x].id[1]=t[rson].id[1];
    else if(t[x].sum!=1)t[x].id[1]=x;
    else t[x].id[1]=t[lson].id[1];
    if(t[rson].id[2])t[x].id[2]=t[rson].id[2];
    else if(t[x].sum!=2)t[x].id[2]=x;
    else t[x].id[2]=t[lson].id[2];
}
void modi(int x,int tag){
    t[x].sum+=tag,t[x].val=(t[x].sum>1);
    swap(t[x].id[1],t[x].id[2]);
    t[x].tag+=tag;
}
void pushdown(int x){
    if(!t[x].tag)return;
    if(lson)modi(lson,t[x].tag);
    if(rson)modi(rson,t[x].tag);
    t[x].tag=0;
}
void rotate(int x){
    int y=t[x].fa;
    int z=t[y].fa;
    int dirx=identify(x);
    int diry=identify(y);
    int b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[x].ch[!dirx]=y,t[y].fa=x;
    pushup(y),pushup(x);
}
void pushall(int x){
    if(identify(x)!=-1)pushall(t[x].fa);
    pushdown(x);
}
void splay(int x){
    pushall(x);
    while(identify(x)!=-1){
        int fa=t[x].fa;
        if(identify(fa)==-1)rotate(x);
        else if(identify(fa)==identify(x))rotate(fa),rotate(x);
        else rotate(x),rotate(x);
    }
    pushup(x);
}
void access(int x){
    for(int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}
queue<int>q;
int main(){
    scanf("%d",&n);
    for(int i=1,t1,t2,t3;i<=n;i++)scanf("%d%d%d",&t1,&t2,&t3),t[t1].fa=t[t2].fa=t[t3].fa=i,in[i]=3;
    for(int i=n+1;i<=3*n+1;i++)scanf("%d",&t[i].val),q.push(i);
    while(!q.empty()){
        int x=q.front();q.pop();
        if(!t[x].fa)continue;
        if(x<=n)pushup(x); 
        t[t[x].fa].sum+=t[x].val,in[t[x].fa]--;
        if(!in[t[x].fa])t[t[x].fa].val=(t[t[x].fa].sum>1),q.push(t[x].fa);
    }
    ans=t[1].val;
    scanf("%d",&m);
    for(int i=1,x,y,z;i<=m;i++){
        scanf("%d",&x),y=t[x].fa;
        access(y),splay(y);
        int dir=t[x].val?2:1,val=t[x].val?-1:1;
        if(t[y].id[dir]){
            z=t[y].id[dir];
            splay(z);
            modi(t[z].ch[1],val),pushup(t[z].ch[1]);
            t[z].sum+=val,t[z].val=(t[z].sum>1),pushup(z);
        }else modi(y,val),ans^=1,pushup(y);
        t[x].val^=1;
        printf("%d\n",ans);
    }
    return 0;
}

VIII.[BZOJ2959]长跑

我想把出这么毒瘤的题的人拖出来揍一顿

这题稍微想想，就是动态维护点双连通分量并缩点，然后在缩出来的树上求两点距离。

思想简单但代码极其复杂。

首先，我们可以使用冰茶姬维护点双，所有的点全都并到一个冰茶姬中，除了冰茶姬的象征节点，其它的点一律全都删去，不保留任何信息。这样的话，比如说在rotate和splay时，不能直接跳到父亲，而是必须跳到父亲的冰茶姬的象征节点。准确地说，代码中所有的节点变量，都最好习惯性地在冰茶姬里面find一下，虽然码量大了点，常数大了点，但是十分靠谱。

当我们连一条边时：

如果两个端点在不同的连通块中，LCT中直接link。

否则，将两个端点之间的路径split出来，然后把这里面所有东西打包到一个冰茶姬中（因为这肯定构成一个点双）。放一下打包的shrink函数：

（merge：冰茶姬合并操作）

inline void shrink(int x,int y){
    merge(x,y);
    if(x!=y)t[y].val+=t[x].val,t[x].fa=0;
    pushdown(x);
    if(lson)shrink(lson,y);
    if(rson)shrink(rson,y);
    lson=rson=0;
}

注意到我们代码中实际调用这个函数的格式是shrink(y,y)，并且y是split出的splay的根。因此，必须要特判x\neq y，不然就会产生奇奇怪怪的错误。

另外，这个出题人居然非常毒瘤的卡了常（或者只是我代码常数过大），不得不inline,register和快读一股脑全上才卡过去。

代码（LCT真的最好压个行，不然代码显得太长太长了）：

#include<bits/stdc++.h>
using namespace std;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
int n,m,dsu[151000],val[151000];
int read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
inline int find(int x){
    return dsu[x]==x?x:dsu[x]=find(dsu[x]);
}
inline void merge(int x,int y){
    x=find(x),y=find(y);
    if(x!=y)dsu[x]=y;
}
struct LCT{
    int ch[2],fa,val,sum;
    bool rev;
}t[151000];
inline int identify(int x){
    if(t[find(t[x].fa)].ch[0]==x)return 0;
    if(t[find(t[x].fa)].ch[1]==x)return 1;
    return -1;
}
inline void REV(int x){
    t[x].rev^=1,swap(lson,rson);
}
inline void pushup(int x){
    t[x].sum=t[x].val;
    if(lson)t[x].sum+=t[lson].sum;
    if(rson)t[x].sum+=t[rson].sum;
}
inline void pushdown(int x){
    if(!t[x].rev)return;
    if(lson)REV(lson);
    if(rson)REV(rson);
    t[x].rev=false;
} 
inline void rotate(int x){
    register int y=find(t[x].fa);
    register int z=find(t[y].fa);
    register int dirx=identify(x);
    register int diry=identify(y);
    register int b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[x].ch[!dirx]=y,t[y].fa=x;
    pushup(y),pushup(x);
}
inline void pushall(int x){
    if(identify(x)!=-1)pushall(t[x].fa=find(t[x].fa));
    pushdown(x);
}
inline void splay(int x){
    pushall(x);
    while(identify(x)!=-1){
        register int fa=t[x].fa;
        if(identify(fa)==-1)rotate(x);
        else if(identify(fa)==identify(x))rotate(fa),rotate(x);
        else rotate(x),rotate(x);
    }
}
inline void access(int x){
    for(register int y=0;x;x=find(t[y=x].fa))splay(x),rson=y,pushup(x);
}
inline void makeroot(int x){
    access(x),splay(x),REV(x);
}
inline int findroot(int x){
    access(x),splay(x);
    pushdown(x);
    while(lson)x=lson,pushdown(x);
    splay(x);
    return x;
}
inline void split(int x,int y){
    makeroot(x),access(y),splay(y);
}
inline void shrink(int x,int y){
    merge(x,y);
    if(x!=y)t[y].val+=t[x].val,t[x].fa=0;
    pushdown(x);
    if(lson)shrink(lson,y);
    if(rson)shrink(rson,y);
    lson=rson=0;
}
inline void link(int x,int y){
    if(findroot(x)==findroot(y))split(x,y),shrink(y,y);
    else makeroot(x),t[x].fa=y;
}
int main(){
    n=read(),m=read();
    for(register int i=1;i<=n;i++)val[i]=t[i].sum=t[i].val=read(),dsu[i]=i;
    for(register int i=1,t1,t2,t3,t4;i<=m;i++){
        t1=read(),t2=read(),t3=read();
        if(t1==1)t2=find(t2),t3=find(t3),link(t2,t3);
        if(t1==2)t4=t2,t4=find(t4),splay(t4),t[t4].val+=t3-val[t2],val[t2]=t3,pushup(t4);
        if(t1==3){
            t2=find(t2),t3=find(t3);
            if(findroot(t2)==findroot(t3))split(t2,t3),printf("%d\n",t[t3].sum);
            else puts("-1");
        }
    }
    return 0;
}

IX.[BZOJ4998]星球联盟

这题就比较套路了（虽然我的程序还好好让我debug了一会），比上一题还要简单，直接暴力维护点双即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
int n,m,p,dsu[200100],sz[200100];
int find(int x){
    return dsu[x]==x?x:dsu[x]=find(dsu[x]); 
}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return;
    if(sz[x]<sz[y])dsu[x]=y,sz[y]+=sz[x];
    else dsu[y]=x,sz[x]+=sz[y];
}
struct LCT{
    int ch[2],fa,val,sum;
    bool rev;
}t[200100];
int identify(int x){
    if(t[find(t[x].fa)].ch[0]==x)return 0;
    if(t[find(t[x].fa)].ch[1]==x)return 1;
    return -1;
}
void REV(int x){
    t[x].rev^=1,swap(lson,rson);
}
void pushup(int x){
    t[x].sum=t[x].val;
    if(lson)t[x].sum+=t[lson].sum;
    if(rson)t[x].sum+=t[rson].sum;
}
void pushdown(int x){
    if(!t[x].rev)return;
    if(lson)REV(lson);
    if(rson)REV(rson);
    t[x].rev=0;
}
void rotate(int x){
    int y=find(t[x].fa);
    int z=find(t[y].fa);
    int dirx=identify(x);
    int diry=identify(y);
    int b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[x].ch[!dirx]=y,t[y].fa=x;
    pushup(y),pushup(x);
}
void pushall(int x){
    if(identify(x)!=-1)pushall(t[x].fa=find(t[x].fa));
    pushdown(x);
}
void splay(int x){
    pushall(x);
    while(identify(x)!=-1){
        int fa=t[x].fa;
        if(identify(fa)==-1)rotate(x);
        else if(identify(fa)==identify(x))rotate(fa),rotate(x);
        else rotate(x),rotate(x);
    }
}
void access(int x){
    for(int y=0;x;x=find(t[y=x].fa))splay(x),rson=y,pushup(x);
}
void makeroot(int x){
    access(x),splay(x),REV(x);
}
void split(int x,int y){
    makeroot(x),access(y),splay(y);
}
int findroot(int x){
    access(x),splay(x);
    pushdown(x);
    while(lson)x=lson,pushdown(x);
    splay(x);
    return x;
}
void shrink(int x,int y){
    merge(x,y);
    if(x!=y)t[y].val+=t[x].val,t[x].fa=0;
    pushdown(x);
    if(lson)shrink(lson,y);
    if(rson)shrink(rson,y);
    lson=rson=0;
}
int link(int x,int y){
    if(findroot(x)==findroot(y)){split(x,y),shrink(y,y);return sz[find(y)];}
    else{makeroot(x),t[x].fa=y;return -1;}
}
int main(){
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++)sz[i]=t[i].val=t[i].sum=1,dsu[i]=i;
    for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),x=find(x),y=find(y),link(x,y);
    for(int i=1,x,y,z;i<=p;i++){
        scanf("%d%d",&x,&y),x=find(x),y=find(y),z=link(x,y);
        if(z==-1)puts("No");else printf("%d\n",z);
    }
    return 0;
}

X.[WC2006]水管局长

或许我这题应该放到V.[NOI2014]魔法森林前面的QaQ？

这题首先一眼看出翻转加边顺序。然后，动态维护最小生成森林，这样保证最小生成森林上的路径上的最大值就是原图中路径的最大值的可能的最小值。反正随便写写就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
int n,m,q;
struct LCT{
    int ch[2],fa,val,mx,rev;
}t[1001000];
int identify(int x){
    if(t[t[x].fa].ch[0]==x)return 0;
    if(t[t[x].fa].ch[1]==x)return 1;
    return -1;
}
void pushup(int x){
    t[x].mx=x;
    if(lson&&t[t[lson].mx].val>t[t[x].mx].val)t[x].mx=t[lson].mx;
    if(rson&&t[t[rson].mx].val>t[t[x].mx].val)t[x].mx=t[rson].mx;
}
void REV(int x){
    t[x].rev^=1,swap(lson,rson);
}
void pushdown(int x){
    if(!t[x].rev)return;
    if(lson)REV(lson);
    if(rson)REV(rson);
    t[x].rev=false;
}
void rotate(int x){
    int y=t[x].fa;
    int z=t[y].fa;
    int dirx=identify(x);
    int diry=identify(y);
    int b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[y].fa=x,t[x].ch[!dirx]=y;
    pushup(y),pushup(x);
}
void pushall(int x){
    if(identify(x)!=-1)pushall(t[x].fa);
    pushdown(x);
}
void splay(int x){
    pushall(x);
    while(identify(x)!=-1){
        int fa=t[x].fa;
        if(identify(fa)==-1)rotate(x);
        else if(identify(fa)==identify(x))rotate(fa),rotate(x);
        else rotate(x),rotate(x);
    }
}
void access(int x){
    for(int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}
void makeroot(int x){
    access(x),splay(x),REV(x);
}
int findroot(int x){
    access(x),splay(x);
    pushdown(x);
    while(lson)x=lson,pushdown(x);
    splay(x);
    return x;
}
void split(int x,int y){
    makeroot(x),access(y),splay(y);
}
void link(int x,int y){
    makeroot(x),t[x].fa=y;
}
void cut(int x,int y){
    split(x,y),t[x].fa=t[y].ch[0]=0,pushup(y);
}
pair<int,int>p[100100];
struct query{
    int tp,x,y;
}r[100100];
bool des[100100];
map<pair<int,int>,int>mp;
void LINK(int id){
    if(findroot(p[id].first)!=findroot(p[id].second))link(p[id].first,id+n),link(p[id].second,id+n);
    else{
        split(p[id].first,p[id].second);
        int tmp=t[p[id].second].mx;
        if(t[tmp].val<=t[id+n].val)return;
        cut(tmp,p[tmp-n].first),cut(tmp,p[tmp-n].second);
        link(p[id].first,id+n),link(p[id].second,id+n);
    }
}
stack<int>S;
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&p[i].first,&p[i].second,&t[i+n].val);
        if(p[i].first>p[i].second)swap(p[i].first,p[i].second);
        mp[p[i]]=i;
    }
    for(int i=1;i<=q;i++){
        scanf("%d%d%d",&r[i].tp,&r[i].x,&r[i].y);
        if(r[i].x>r[i].y)swap(r[i].x,r[i].y);
        if(r[i].tp==2)des[mp[make_pair(r[i].x,r[i].y)]]=true;
    }
    for(int i=1;i<=m;i++)if(!des[i])LINK(i);
    for(int i=q;i;i--)if(r[i].tp==2)LINK(mp[make_pair(r[i].x,r[i].y)]);else split(r[i].x,r[i].y),S.push(t[t[r[i].y].mx].val);
    while(!S.empty())printf("%d\n",S.top()),S.pop();
    return 0;
} 

XI.[BJOI2014]大融合

终于来了……我们终于要用LCT来维护子树信息了。

因为我们看到，LCT是通过将原树拆成一堆链而起效的。在树链剖分中，我们通过dfs序来访问一棵子树；但是因为LCT的链是动态变化的，因此并没有一组固定的访问顺序。

那怎么办呢？

我们考虑最原始的想法：对于每个节点，再额外维护所有虚子节点的状态。比如说，本题我们维护的就是虚子节点的子树大小之和。

我们设 t[x].s1 表示一个节点所有子节点（不管虚实）的子树大小之和，即在原树中，它自己的子树大小。再设 t[x].s2 为所有虚子节点的大小之和。

那么，pushup 函数将会长成这样：

void pushup(int x){
    t[x].s1=t[x].s2+t[lson].s1+t[rson].s1+1;
}

我们再考虑其它函数会有什么变化。显然，只有当节点间的虚实关系（边由实转序、连边、断边等）发生变化时，s2 才会发生变化。

splay 函数：在同一棵实splay中操作，没有虚实关系变化。

access 函数：有变化！

我们拎出来 access 函数：

void access(int x){
    for(int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}

可以看到，我们有 rson=y ，虚实关系产生了变化！！！

对于rson，这是实转虚，s2 应该加上rson的 s1 ；对于y，这是虚转实，s2 应该减去y的 s1 。

因此我们最终有：

void access(int x){
    for(int y=0;x;x=t[y=x].fa)splay(x),t[x].s2+=t[rson].s1-t[y].s1,rson=y,pushup(x);
}

makeroot ， findroot， split 函数：并没有虚实变化（变化全在函数内调用的 access 函数，已经在 access 时改过了），没有变化。

link ：情况有变！我们这时必须要将y的 s2 加上x的 s1 ，因为x成为了y的虚儿子！

但是，y一变，y的父亲也要跟着变，y的爷爷也是……

我们有办法。直接将y access 后移到root（注意是splay的root，不是整棵树的ROOT），这样y就没有父亲了！

因此我们的 link 函数就变成了这样：

void link(int x,int y){
    split(x,y);
    t[y].s2+=t[x].s1;
    t[x].fa=y;
    pushup(y);
}

等等，哪来的 split ？

偷懒一下，我们只是把 makeroot(x),access(y),splay(y) 三合一。实际上x和y并不连通。

至于 cut ，这题并不需要。不过代码还是放出来：

void cut(int x,int y){
    split(x,y);
    t[x].fa=t[y].ch[0]=0;
    pushup(y);
}

然后，当我们要求出一个节点x的子树大小时：

int query(int x,int y){
    split(x,y);
    return t[x].s1;
}

其中y就是指定的x的父亲（不然不知道是哪颗子树），在这题中就是给定询问的边的另一端点。

完整版放出：

#include<bits/stdc++.h>
using namespace std;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
int n,m;
struct node{
    int ch[2],s1,s2,fa;
    bool rev;
}t[100100];
int identify(int x){
    if(t[t[x].fa].ch[0]==x)return 0;
    if(t[t[x].fa].ch[1]==x)return 1;
    return -1;
}
void pushup(int x){
    t[x].s1=t[x].s2+t[lson].s1+t[rson].s1+1;
}
void REV(int x){
    t[x].rev^=1,swap(lson,rson);
}
void pushdown(int x){
    if(!t[x].rev)return;
    if(lson)REV(lson);
    if(rson)REV(rson);
    t[x].rev=0;
}
void rotate(int x){
    int y=t[x].fa;
    int z=t[y].fa;
    int dirx=identify(x);
    int diry=identify(y);
    int b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[x].ch[!dirx]=y,t[y].fa=x;
    pushup(y),pushup(x);
}
void pushall(int x){
    if(identify(x)!=-1)pushall(t[x].fa);
    pushdown(x);
}
void splay(int x){
    pushall(x);
    while(identify(x)!=-1){
        int fa=t[x].fa;
        if(identify(fa)==-1)rotate(x);
        else if(identify(fa)==identify(x))rotate(fa),rotate(x);
        else rotate(x),rotate(x);
    }
}
void access(int x){
    for(int y=0;x;x=t[y=x].fa)splay(x),t[x].s2+=t[rson].s1-t[y].s1,rson=y,pushup(x);
}
void makeroot(int x){
    access(x),splay(x),REV(x);
}
int findroot(int x){
    access(x),splay(x);
    pushdown(x);
    while(lson)x=lson,pushdown(x);
    splay(x);
    return x;
}
void split(int x,int y){
    makeroot(x),access(y),splay(y);
}
void link(int x,int y){
    split(x,y);
    t[y].s2+=t[x].s1;
    t[x].fa=y;
}
int query(int x,int y){
    split(x,y);
    return t[x].s1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;i++){
        char s[10];
        scanf("%s%d%d",s,&x,&y);
        if(s[0]=='A')link(x,y);
        else printf("%lld\n",1ll*query(x,y)*query(y,x));
    }
    return 0;
}

XII.[ZJOI2012]网络

这题还以为有什么高端做法呢，一看C\leq 10，这题就算结束了。

它的那个限制翻译成人话就是“无论何时，任何颜色的边总是构成一条条链”。然后换颜色就暴力连边断边即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,c,q,col[100100],val[10010];
map<pair<int,int>,int>mp;
struct Link_Cut_Tree{
    #define lson t[x].ch[0]
    #define rson t[x].ch[1]
    int deg[100100];
    struct node{
        int ch[2],fa,val,mx;
        bool rev;
    }t[10010];
    int identify(int x){
        if(t[t[x].fa].ch[0]==x)return 0;
        if(t[t[x].fa].ch[1]==x)return 1;
        return -1;
    }
    void pushup(int x){
        t[x].mx=t[x].val;
        if(lson)t[x].mx=max(t[x].mx,t[lson].mx);
        if(rson)t[x].mx=max(t[x].mx,t[rson].mx);
    }
    void REV(int x){
        t[x].rev^=1,swap(lson,rson);
    }
    void pushdown(int x){
        if(!t[x].rev)return;
        if(lson)REV(lson);
        if(rson)REV(rson);
        t[x].rev=false;
    }
    void rotate(int x){
        int y=t[x].fa;
        int z=t[y].fa;
        int dirx=identify(x);
        int diry=identify(y);
        int b=t[x].ch[!dirx];
        if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
        if(b)t[b].fa=y;t[y].ch[dirx]=b;
        t[y].fa=x,t[x].ch[!dirx]=y;
        pushup(y),pushup(x);
    }
    void pushall(int x){
        if(identify(x)!=-1)pushall(t[x].fa);
        pushdown(x);
    }
    void splay(int x){
        pushall(x);
        while(identify(x)!=-1){
            int fa=t[x].fa;
            if(identify(fa)==-1)rotate(x);
            else if(identify(fa)==identify(x))rotate(fa),rotate(x);
            else rotate(x),rotate(x);
        }
    }
    void access(int x){
        for(int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
    }
    void makeroot(int x){
        access(x),splay(x),REV(x);
    }
    int findroot(int x){
        access(x),splay(x);
        pushdown(x);
        while(lson)x=lson,pushdown(x);
        splay(x);
        return x;
    }
    int split(int x,int y){
        if(findroot(x)!=findroot(y))return -1;
        makeroot(x),access(y),splay(y);
        return t[y].mx;
    }
    bool link(int x,int y){
        if(findroot(x)==findroot(y))return false;
        makeroot(x),t[x].fa=y;
        return true;
    }
    void cut(int x,int y){
        split(x,y),t[x].fa=t[y].ch[0]=0,pushup(y);
    }
}LCT[10];
int main(){
    scanf("%d%d%d%d",&n,&m,&c,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&val[i]);
        for(int j=0;j<c;j++)LCT[j].t[i].val=LCT[j].t[i].mx=val[i];
    }
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d%d",&x,&y,&col[i]);
        if(x>y)swap(x,y);
        mp[make_pair(x,y)]=i;
        LCT[col[i]].link(x,y);
        LCT[col[i]].deg[x]++,LCT[col[i]].deg[y]++;
    }
    for(int i=1,t1,t2,t3,t4;i<=q;i++){
        scanf("%d",&t1);
        if(t1==0){
            scanf("%d%d",&t2,&t3),val[t2]=t3;
            for(int j=0;j<c;j++)LCT[j].makeroot(t2),LCT[j].splay(t2),LCT[j].t[t2].val=t3,LCT[j].pushup(t2);
        }
        if(t1==1){
            scanf("%d%d%d",&t2,&t3,&t4);
            if(t2>t3)swap(t2,t3);
            map<pair<int,int>,int>::iterator it=mp.find(make_pair(t2,t3));
            if(it==mp.end()){puts("No such edge.");continue;}
            if(col[it->second]==t4){puts("Success.");continue;}
            if(LCT[t4].deg[t2]==2||LCT[t4].deg[t3]==2){puts("Error 1.");continue;}
            if(!LCT[t4].link(t2,t3)){puts("Error 2.");continue;}
            LCT[col[it->second]].cut(t2,t3);
            LCT[col[it->second]].deg[t2]--,LCT[col[it->second]].deg[t3]--;
            col[it->second]=t4;
            LCT[t4].deg[t2]++,LCT[t4].deg[t3]++;
            puts("Success.");
        }
        if(t1==2)scanf("%d%d%d",&t2,&t3,&t4),printf("%d\n",LCT[t2].split(t3,t4));
    }
    return 0;
}

XIII.[TJOI2015]旅游

我至今还记得做毒瘤树剖题和毒瘤线段树题时那一坨坨触目惊心的 pushup 和 pushdown ……

这题是可以用树剖做的。但是，我还是选择了LCT。

在每个节点，我们维护如下值：

mx ：子树最大值

mn ：子树最小值

lmx ：从左往右走，最大收益（即要求的东西）

rmx ：从右往左走，最大收益（在翻转区间时要与lmx std::swap掉）。

然后这是那毒瘤的压行的 pushup：

inline void pushup(int x){
    t[x].mx=t[x].mn=t[x].val;
    t[x].lmx=t[x].rmx=0;
    if(lson)t[x].mx=max(t[x].mx,t[lson].mx),t[x].mn=min(t[x].mn,t[lson].mn),t[x].lmx=max(t[x].lmx,max(t[lson].lmx,t[x].val-t[lson].mn)),t[x].rmx=max(t[x].rmx,max(t[lson].rmx,t[lson].mx-t[x].val));
    if(rson)t[x].mx=max(t[x].mx,t[rson].mx),t[x].mn=min(t[x].mn,t[rson].mn),t[x].lmx=max(t[x].lmx,max(t[rson].lmx,t[rson].mx-t[x].val)),t[x].rmx=max(t[x].rmx,max(t[rson].rmx,t[x].val-t[rson].mn));
    if(lson&&rson)t[x].lmx=max(t[x].lmx,t[rson].mx-t[lson].mn),t[x].rmx=max(t[x].rmx,t[lson].mx-t[rson].mn);
}

在 lmx 中，只有右边的较大值能减去左边的较小值；在 rmx 中，只有左边的较大值能减去右边的较小值。

完整代码放出：

#include<bits/stdc++.h>
using namespace std;
int n,m;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
struct LCT{
    int fa,ch[2],val,mx,mn,lmx,rmx,tag;
    bool rev;
}t[100100];
inline void read(int &x){
    x=0;
    register char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline int identify(int x){
    if(x==t[t[x].fa].ch[0])return 0;
    if(x==t[t[x].fa].ch[1])return 1;
    return -1;
}
inline void REV(int x){
    t[x].rev^=1,swap(lson,rson),swap(t[x].lmx,t[x].rmx);
}
inline void ADD(int x,int y){
    t[x].val+=y,t[x].mx+=y,t[x].mn+=y,t[x].tag+=y;
}
inline void pushup(int x){
    t[x].mx=t[x].mn=t[x].val;
    t[x].lmx=t[x].rmx=0;
    if(lson)t[x].mx=max(t[x].mx,t[lson].mx),t[x].mn=min(t[x].mn,t[lson].mn),t[x].lmx=max(t[x].lmx,max(t[lson].lmx,t[x].val-t[lson].mn)),t[x].rmx=max(t[x].rmx,max(t[lson].rmx,t[lson].mx-t[x].val));
    if(rson)t[x].mx=max(t[x].mx,t[rson].mx),t[x].mn=min(t[x].mn,t[rson].mn),t[x].lmx=max(t[x].lmx,max(t[rson].lmx,t[rson].mx-t[x].val)),t[x].rmx=max(t[x].rmx,max(t[rson].rmx,t[x].val-t[rson].mn));
    if(lson&&rson)t[x].lmx=max(t[x].lmx,t[rson].mx-t[lson].mn),t[x].rmx=max(t[x].rmx,t[lson].mx-t[rson].mn);
}
inline void pushdown(int x){
    if(t[x].rev){
        if(lson)REV(lson);
        if(rson)REV(rson);
        t[x].rev=0;     
    }
    if(lson)ADD(lson,t[x].tag);
    if(rson)ADD(rson,t[x].tag);
    t[x].tag=0;
}
inline void rotate(int x){
    register int y=t[x].fa;
    register int z=t[y].fa;
    register int dirx=identify(x);
    register int diry=identify(y);
    register int b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[y].fa=x,t[x].ch[!dirx]=y;
    pushup(y),pushup(x);
}
inline void pushall(int x){
    if(identify(x)!=-1)pushall(t[x].fa);
    pushdown(x);
}
inline void splay(int x){
    pushall(x);
    while(identify(x)!=-1){
        register int fa=t[x].fa;
        if(identify(fa)==-1)rotate(x);
        else if(identify(x)==identify(fa))rotate(fa),rotate(x);
        else rotate(x),rotate(x);
    }
}
inline void access(int x){
    for(register int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}
inline void makeroot(int x){
    access(x),splay(x),REV(x);
}
inline void split(int x,int y){
    makeroot(x),access(y),splay(y);
}
inline void link(int x,int y){
    makeroot(x),t[x].fa=y;
}
int main(){
    read(n);
    for(register int i=1;i<=n;i++)read(t[i].val),t[i].mn=t[i].mx=t[i].val;
    for(register int i=1,x,y;i<n;i++)read(x),read(y),link(x,y);
    read(m);
    for(register int i=1,x,y,z;i<=m;i++){
        read(x),read(y),read(z);
        split(x,y);
        printf("%d\n",t[y].lmx);
        ADD(y,z);
    }
    return 0;
}

然后，为了复习树剖，我还写了一篇树剖的代码。然后发现，LCT比树剖可爱一百万倍！！！树剖要用重链拼出原本的路径，但是这题拼合两条链的运算不具有交换律！！！这就意味着这个拼接的东西将会非常繁琐，因为你要保证所有加上去的东西是严格按照路径顺序加上去的！并且，最后，树剖比LCT还要多敲300B！

LCT我花了1h敲完，但是树剖我整整研究了2h……（虽然有很大原因是因为我两个月没写过树剖了）

奉上树剖代码：

#include<bits/stdc++.h>
using namespace std;
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
int n,m,head[50010],cnt,dep[50010],fa[50010],son[50010],sz[50010],dfn[50010],rev[50010],top[50010],val[50010],tot;
struct node{
    int to,next;
}edge[100100];
void ae(int u,int v){
    edge[cnt].next=head[u],edge[cnt].to=v,head[u]=cnt++;
    edge[cnt].next=head[v],edge[cnt].to=u,head[v]=cnt++;
}
void dfs1(int x,int Fa){
    fa[x]=Fa,dep[x]=dep[Fa]+1,sz[x]=1;
    for(int i=head[x],y;i!=-1;i=edge[i].next){
        if((y=edge[i].to)==fa[x])continue;
        dfs1(y,x),sz[x]+=sz[y];
        if(sz[son[x]]<sz[y])son[x]=y;
    }
}
void dfs2(int x){
    if(son[x])top[son[x]]=top[x],dfn[son[x]]=++tot,rev[tot]=son[x],dfs2(son[x]);
    for(int i=head[x],y;i!=-1;i=edge[i].next){
        y=edge[i].to;
        if(y==fa[x]||y==son[x])continue;
        top[y]=y,dfn[y]=++tot,rev[tot]=y,dfs2(y);
    }
}
struct SegTree{
    int mx,mn,lmx,rmx,tag;
    SegTree(){
        mx=lmx=rmx=tag=0;
        mn=0x3f3f3f3f;
    }
    friend SegTree operator +(const SegTree &l,const SegTree &r){
        SegTree x;
        x.mx=max(l.mx,r.mx);
        x.mn=min(l.mn,r.mn);
        x.lmx=max(max(l.lmx,r.lmx),r.mx-l.mn);
        x.rmx=max(max(l.rmx,r.rmx),l.mx-r.mn);
        return x;
    }
}seg[200100];
void build(int x,int l,int r){
    if(l==r){seg[x].mn=seg[x].mx=val[rev[l]];return;}
    build(lson,l,mid),build(rson,mid+1,r),seg[x]=seg[lson]+seg[rson];
}
void pushdown(int x){
    seg[lson].mn+=seg[x].tag,seg[lson].mx+=seg[x].tag,seg[lson].tag+=seg[x].tag;
    seg[rson].mn+=seg[x].tag,seg[rson].mx+=seg[x].tag,seg[rson].tag+=seg[x].tag;
    seg[x].tag=0;
}
void modify(int x,int l,int r,int L,int R,int val){
    if(l>R||r<L)return;
    if(L<=l&&r<=R){seg[x].mn+=val,seg[x].mx+=val,seg[x].tag+=val;return;}
    pushdown(x),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val),seg[x]=seg[lson]+seg[rson];
}
SegTree query(int x,int l,int r,int L,int R){
    if(l>R||r<L)return SegTree();
    if(L<=l&&r<=R)return seg[x];
    pushdown(x);
    return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);
}
int ask(int x,int y,int z){
    SegTree l,r;
    while(top[x]!=top[y]){
        if(dep[top[x]]>dep[top[y]]){
            SegTree tmp=query(1,1,n,dfn[top[x]],dfn[x]);
            swap(tmp.lmx,tmp.rmx);
            l=l+tmp;
            modify(1,1,n,dfn[top[x]],dfn[x],z),x=fa[top[x]];
        }
        else r=query(1,1,n,dfn[top[y]],dfn[y])+r,modify(1,1,n,dfn[top[y]],dfn[y],z),y=fa[top[y]];
    }
    if(dep[x]<=dep[y])r=query(1,1,n,dfn[x],dfn[y])+r,modify(1,1,n,dfn[x],dfn[y],z);
    else{
        SegTree tmp=query(1,1,n,dfn[y],dfn[x]);
        swap(tmp.lmx,tmp.rmx);
        l=l+tmp;
        modify(1,1,n,dfn[y],dfn[x],z);
    }
    return (l+r).lmx;
}
int main(){
    scanf("%d",&n),memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++)scanf("%d",&val[i]);
    for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),ae(x,y);
    dfs1(1,0),dfn[1]=rev[1]=top[1]=tot=1,dfs2(1);
    build(1,1,n),scanf("%d",&m);
    for(int i=1,x,y,z;i<=m;i++)scanf("%d%d%d",&x,&y,&z),printf("%d\n",ask(x,y,z));
    return 0;
}

XIV.[BZOJ3159]决战

你们知道吗！把一行 #define int long long 写在了一行 int 的后面然后 debug 了一整天的崩溃你知道吗！！！

我恨不得罢免了自己！

言归正传。

从某种角度来说，这是我写的第一棵树套树！虽然是邪教般的LCT套splay

首先，除了翻转操作以外的其它操作，都是LCT甚至是树剖的常规操作。关键是这个 翻转 操作。

或许你会决定这很简单，直接把链 split 出来然后打上翻转的 tag 即可。如果你真这么认为的话，可就错了。LCT中的翻转，是针对链的翻转，翻转的时候不仅翻转值，连儿子也一起给你翻了去！我们要实现的，是针对值的翻转。LCT维护的是树的形态，我们还需要再开一棵splay维护值域。

为了方便，我们不如让新的splay一样以深度为键值排序，并维护所有节点的值。为了区别，我们把这棵新splay叫做SPLAY。考虑将同一条链中的所有节点染成同一个颜色（这里的颜色可以是链中任意一个节点的值），并将这一条链中的所有东西打包到一棵SPLAY中。

我们考虑当LCT中进行某种操作时，对应的SPLAY会进行何种变化：

splay 操作：没有改变任何一个节点的染色，SPLAY无变化。

access 操作：我们看看它的具体代码：

inline void access(int x){
    for(register int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}

我们在这里面改变了节点的染色！

我们强制断开了 rson ，即将以 rson 为根的子树染成某种颜色；并将以 y 为根的子树染成和以 x 为根的子树的同一种颜色！

对应的SPLAY中的操作就是：挖掉深度大于等于 rson 的所有节点，并将以 y 为根的SPLAY接上去。

这个时候，我们便看出以深度为键值的好处了：只要记录一个 size 表示子树大小，我们就只需要找出SPLAY中排名为 lson_size+1 的点，断去它的右儿子，并将 y 赋成它新的右儿子即可。

说一下下文代码中各函数的含义：

lc ：LCT。

sp ：SPLAY。

rt[x] ：节点x被染上的颜色。

CHANGE(x,y)：把以x为根的子树全都染成y颜色。

fd(x,y)：找到以x为根的子树中排名为y的节点，并将其转到root。

inline void access(int x){
    for(register int y=0;x;x=lc.fa[y=x]){
        lc.splay(x);
        int xx=rt[x];
        sp.splay(xx);
        xx=sp.fd(xx,lc.sz[lc.ch[x][0]]+1);
        lc.CHANGE(lc.ch[x][1],sp.ch[xx][1]);
        lc.ch[x][1]=y;
        lc.CHANGE(x,xx);
        sp.fa[sp.ch[xx][1]]=0;
        sp.ch[xx][1]=rt[y];
        sp.fa[rt[y]]=xx;
        lc.pushup(x),sp.pushup(xx);
    }
}

access函数是最主要的函数。其它还有函数makeroot，split等。反正，就是splay怎样做，SPLAY就怎样做（至少大部分情况是这样，即影响SPLAY结构或染色的操作）。

inline void makeroot(int x){
    access(x),lc.splay(x),sp.splay(rt[x]),lc.REV(x),sp.REV(rt[x]);
}
inline void split(int x,int y){
    makeroot(x),access(y),lc.splay(y),sp.splay(rt[y]);
}
inline void link(int x,int y){
    makeroot(x),lc.fa[x]=y;
}

最终代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,mn[100100],mx[100100],val[100100],sum[100100],tag[100100],rt[100100],tr[100100];
struct SPLAY{
    #define lson ch[x][0]
    #define rson ch[x][1]
    int fa[100100],ch[100100][2],sz[100100];
    bool rev[100100],tp;
    inline int identify(int x){
        if(x==ch[fa[x]][0])return 0;
        if(x==ch[fa[x]][1])return 1;
        return -1;
    }
    inline void pushup(int x){
        if(tp==0){
            mn[x]=mx[x]=sum[x]=val[x],sz[x]=1;
            if(lson)mx[x]=max(mx[x],mx[lson]),mn[x]=min(mn[x],mn[lson]),sz[x]+=sz[lson],sum[x]+=sum[lson];
            if(rson)mx[x]=max(mx[x],mx[rson]),mn[x]=min(mn[x],mn[rson]),sz[x]+=sz[rson],sum[x]+=sum[rson];          
        }else{
            sz[x]=1;
            if(lson)sz[x]+=sz[lson];
            if(rson)sz[x]+=sz[rson];
        }
    }
    inline void ADD(int x,int vv){
        if(!x)return;
        sum[x]+=vv*sz[x],mn[x]+=vv,mx[x]+=vv,tag[x]+=vv,val[x]+=vv;
    }
    inline void CHANGE(int x,int y){
        if(!x)return;
        rt[x]=tr[x]=y;
    }
    inline void REV(int x){
        if(!x)return;
        swap(lson,rson),rev[x]^=1;
    }
    inline void pushdown(int x){
        if(!tp){
            if(rev[x]){
                if(lson)REV(lson);
                if(rson)REV(rson);
                rev[x]=0;
            }
            if(lson)ADD(lson,tag[x]);
            if(rson)ADD(rson,tag[x]);
            tag[x]=0;           
        }else{
            if(rev[x]){
                if(lson)REV(lson);
                if(rson)REV(rson);
                rev[x]=0;           
            }
            if(tr[x]){
                if(lson)CHANGE(lson,tr[x]);
                if(rson)CHANGE(rson,tr[x]);
                tr[x]=0;
            }
        }
    }
    inline void rotate(int x){
        register int y=fa[x];
        register int z=fa[y];
        register int dirx=identify(x);
        register int diry=identify(y);
        register int b=ch[x][!dirx];
        if(diry!=-1)ch[z][diry]=x;fa[x]=z;
        if(b)fa[b]=y;ch[y][dirx]=b;
        fa[y]=x,ch[x][!dirx]=y;
        pushup(y),pushup(x);
    }
    inline void pushall(int x){
        if(identify(x)!=-1)pushall(fa[x]);
        pushdown(x);
    }
    inline void splay(int x){
        pushall(x);
        while(identify(x)!=-1){
            register int Fa=fa[x];
            if(identify(Fa)==-1)rotate(x);
            else if(identify(x)==identify(Fa))rotate(Fa),rotate(x);
            else rotate(x),rotate(x);
        }
    }
    int fd(int x,int k){
        while(true){
            pushdown(x);
            if(k<=sz[lson])x=lson;
            else if(k>sz[lson]+1)k-=sz[lson]+1,x=rson;
            else{splay(x);return x;}
        }
    }
    #undef lson
    #undef rson 
}sp,lc;
inline void access(int x){
    for(register int y=0;x;x=lc.fa[y=x]){
        lc.splay(x);
        int xx=rt[x];
        sp.splay(xx);
        xx=sp.fd(xx,lc.sz[lc.ch[x][0]]+1);
        lc.CHANGE(lc.ch[x][1],sp.ch[xx][1]);
        lc.ch[x][1]=y;
        lc.CHANGE(x,xx);
        sp.fa[sp.ch[xx][1]]=0;
        sp.ch[xx][1]=rt[y];
        sp.fa[rt[y]]=xx;
        lc.pushup(x),sp.pushup(xx);
    }
}
inline void makeroot(int x){
    access(x),lc.splay(x),sp.splay(rt[x]),lc.REV(x),sp.REV(rt[x]);
}
inline void split(int x,int y){
    makeroot(x),access(y),lc.splay(y),sp.splay(rt[y]);
}
inline void link(int x,int y){
    makeroot(x),lc.fa[x]=y;
}
inline int read(){
    register int x=0;
    register char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
signed main(){
    n=read(),m=read(),read(),lc.tp=true;
    for(int i=1;i<=n;i++)rt[i]=i,lc.sz[i]=sp.sz[i]=1;
    for(int i=1,x,y;i<n;i++)x=read(),y=read(),link(x,y);
    for(int i=1,x,y,z;i<=m;i++){
        char s[10];
        scanf("%s",s),x=read(),y=read(),split(x,y);
        if(s[2]=='c')z=read(),sp.ADD(rt[y],z);
        if(s[2]=='m')printf("%lld\n",sum[rt[y]]);
        if(s[2]=='j')printf("%lld\n",mx[rt[y]]);
        if(s[2]=='n')printf("%lld\n",mn[rt[y]]);
        if(s[2]=='v')sp.REV(rt[y]);
    }
    return 0;
}

XV.[USACO18FEB]New Barns P

这种东西应该怎么维护呢？这是子树最大值呀。

一种方法是用平衡树（例如 std::multiset ）维护轻儿子长度集合。但是这种东西太麻烦，太恶心了。

考虑直径的性质。我们给出两条引理：

引理1：假如有一条直径(p,q)，那么树中任意一个点x到其它点的最远距离，一定为\max(dis(x,p),dis(x,q))。

引理2：假如树S有一条直径(p,q)，树T有一条直径为(r,s)，则若我们把S和T添加一条边连起来，新的直径的两个端点(u,v)，一定有u,v\in\{p,q,r,s\}。

有了这两个引理就OK了。我们需要用LCT动态查询树上两点距离，就是split后计算size-1。

然后，对于每颗树，维护直径(p,q)。当加入新点x后，计算\{p,q,s\}中最长的路径作为直径即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,dsu[100100],len[100100],cnt;
pair<int,int>p[100100];
#define lson t[x].ch[0]
#define rson t[x].ch[1]
struct LCT{
    int fa,ch[2],sz;
    bool rev;
}t[100100];
inline int identify(int x){
    if(x==t[t[x].fa].ch[0])return 0;
    if(x==t[t[x].fa].ch[1])return 1;
    return -1;
}
inline void pushup(int x){
    t[x].sz=1;
    if(lson)t[x].sz+=t[lson].sz;
    if(rson)t[x].sz+=t[rson].sz; 
}
inline void REV(int x){
    t[x].rev^=1,swap(lson,rson);
}
inline void pushdown(int x){
    if(!t[x].rev)return;
    if(lson)REV(lson);
    if(rson)REV(rson);
    t[x].rev=0;
}
inline void rotate(int x){
    register int y=t[x].fa;
    register int z=t[y].fa;
    register int dirx=identify(x);
    register int diry=identify(y);
    register int b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[y].fa=x,t[x].ch[!dirx]=y;
    pushup(y),pushup(x);
}
inline void pushall(int x){
    if(identify(x)!=-1)pushall(t[x].fa);
    pushdown(x);
}
inline void splay(int x){
    pushall(x);
    while(identify(x)!=-1){
        register int fa=t[x].fa;
        if(identify(fa)==-1)rotate(x);
        else if(identify(x)==identify(fa))rotate(fa),rotate(x);
        else rotate(x),rotate(x);
    }
}
inline void access(int x){
    for(register int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}
inline void makeroot(int x){
    access(x),splay(x),REV(x);
}
inline int split(int x,int y){
    makeroot(x),access(y),splay(y);
    return t[y].sz-1;
}
inline void link(int x,int y){
    makeroot(x),t[x].fa=y;
}
int main(){
    scanf("%d",&n);
    for(int i=1,x;i<=n;i++){
        char s[3];
        scanf("%s%d",s,&x);
        if(s[0]=='B'){
            ++cnt;
            t[cnt].sz=1;
            if(x==-1){dsu[cnt]=cnt,p[cnt]=make_pair(cnt,cnt);continue;}
            link(cnt,x),dsu[cnt]=dsu[x];
            int nl=split(cnt,p[dsu[cnt]].first);
            if(nl>len[dsu[cnt]]){p[dsu[cnt]]=make_pair(p[dsu[cnt]].first,cnt),len[dsu[cnt]]=nl;continue;}
            nl=split(cnt,p[dsu[cnt]].second);
            if(nl>len[dsu[cnt]]){p[dsu[cnt]]=make_pair(p[dsu[cnt]].second,cnt),len[dsu[cnt]]=nl;continue;}
        }else{
            int nl=split(x,p[dsu[x]].first);
            nl=max(nl,split(x,p[dsu[x]].second));
            printf("%d\n",nl);
        }
    }
    return 0;
}

XVI.二分图 /【模板】线段树分治

本题有两种做法。一是所谓的“正解”线段树分治，复杂度O(n\log n\log k)。思路比较简单，敲起来也简单，就是复杂度不太优秀。

代码：

#include<bits/stdc++.h>
using namespace std;
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
int n,m,lim,cnt,dsu[200100],sz[200100];
int find(int x){
    return dsu[x]==x?x:find(dsu[x]);
}
struct opt{
    int u,v,su,sv;
    opt(int a=0,int b=0,int c=0,int d=0){u=a,v=b,su=c,sv=d;}
};
stack<opt>s;
int merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return 0;
    s.push(opt(x,y,sz[x],sz[y]));
    if(sz[x]<sz[y])dsu[x]=y,sz[y]+=sz[x];
    else dsu[y]=x,sz[x]+=sz[y];
    return 1;
}
void Pop(){
    dsu[s.top().u]=s.top().u,dsu[s.top().v]=s.top().v,sz[s.top().u]=s.top().su,sz[s.top().v]=s.top().sv,s.pop();
}
bool link(int x,int y){
    int tot=merge(x+n,y)+merge(x,y+n);
    if(find(x)!=find(x+n)&&find(y)!=find(y+n))return true;
    while(tot--)Pop();
    return false;
}
vector<pair<int,int> >v[400100];
void modify(int x,int l,int r,int L,int R,int f,int g){
    if(l>R||r<L)return;
    if(L<=l&&r<=R){v[x].push_back(make_pair(f,g));return;}
    modify(lson,l,mid,L,R,f,g),modify(rson,mid+1,r,L,R,f,g);
}
void dfs(int x,int l,int r){
    int res=0,len=s.size();
    for(int i=0,tmp;i<v[x].size();i++){
        tmp=link(v[x][i].first,v[x][i].second);
        res+=!tmp;
    }
    cnt+=res;
    if(l==r){puts(cnt?"No":"Yes"),cnt-=res;return;}
    dfs(lson,l,mid),dfs(rson,mid+1,r);
    while(s.size()>len)Pop();
    cnt-=res;
}
int main(){
    scanf("%d%d%d",&n,&m,&lim);
    for(int i=1;i<=2*n;i++)dsu[i]=i,sz[i]=1;
    for(int i=1,x,y,l,r;i<=m;i++){
        scanf("%d%d%d%d",&x,&y,&l,&r),l++;
        if(l<=r)modify(1,1,lim,l,r,x,y);
    }
    dfs(1,1,lim);
    return 0;
}

二是所谓的“暴力解法”，但是复杂度反而更优，为O(n\log n)的LCT。

具体想法是，我们维护原图关于删除时间的最大生成森林。

当加入一条新边构成环时：

我们在LCT中提取出来新边的路径。如果这条新边构成奇环（即这条路径的size为奇）的话，则直到这个奇环的删除时间最小的那条边被删除为止，这张图都不会是二分图。

正因如此，我们才会贪心地维护最大生成树，因为最大生成树就意味着构成的奇环是正确的，保证直到环上第一条边删去前，它都不会是二分图。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,lim,res[100100];
#define lson t[x].ch[0]
#define rson t[x].ch[1]
struct LCT{
    int fa,ch[2],mn,val,sz;
    bool rev;
}t[300100];
inline int identify(int x){
    if(x==t[t[x].fa].ch[0])return 0;
    if(x==t[t[x].fa].ch[1])return 1;
    return -1;
}
inline void pushup(int x){
    t[x].mn=x;
    t[x].sz=(x<=n);
    if(lson){
        if(t[t[x].mn].val>t[t[lson].mn].val)t[x].mn=t[lson].mn;
        t[x].sz+=t[lson].sz;
    }
    if(rson){
        if(t[t[x].mn].val>t[t[rson].mn].val)t[x].mn=t[rson].mn;
        t[x].sz+=t[rson].sz;
    }
}
inline void REV(int x){
    t[x].rev^=1,swap(lson,rson);
}
inline void pushdown(int x){
    if(!t[x].rev)return;
    if(lson)REV(lson);
    if(rson)REV(rson);
    t[x].rev=0;
}
inline void rotate(int x){
    register int y=t[x].fa;
    register int z=t[y].fa;
    register int dirx=identify(x);
    register int diry=identify(y);
    register int b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[y].fa=x,t[x].ch[!dirx]=y;
    pushup(y),pushup(x);
}
inline void pushall(int x){
    if(identify(x)!=-1)pushall(t[x].fa);
    pushdown(x);
}
inline void splay(int x){
    pushall(x);
    while(identify(x)!=-1){
        register int fa=t[x].fa;
        if(identify(fa)==-1)rotate(x);
        else if(identify(x)==identify(fa))rotate(fa),rotate(x);
        else rotate(x),rotate(x);
    }
}
inline void access(int x){
    for(register int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}
inline void makeroot(int x){
    access(x),splay(x),REV(x);
}
inline int findroot(int x){
    access(x),splay(x);
    pushdown(x);
    while(lson)x=lson,pushdown(x);
    splay(x);
    return x;
}
inline void split(int x,int y){
    makeroot(x),access(y),splay(y);
}
inline void link(int x,int y){
    makeroot(x),t[x].fa=y;
}
inline void cut(int x,int y){
    split(x,y),t[y].ch[0]=t[x].fa=0,pushup(y);
}
pair<int,int>p[200100];
vector<int>stt[100100],fin[100100];
bool on[200100];
int main(){
    scanf("%d%d%d",&n,&m,&lim);
    for(int i=1;i<=n+m;i++)t[i].mn=i;
    for(int i=1;i<=n;i++)t[i].val=0x3f3f3f3f,t[i].sz=1;
    for(int i=1,a,b,c,d;i<=m;i++){
        scanf("%d%d%d%d",&a,&b,&c,&d),stt[c].push_back(i),fin[d].push_back(i);
        t[i+n].val=d;
        p[i]=make_pair(a,b);
    }
    for(int i=0;i<lim;i++){
        for(int j=0;j<stt[i].size();j++){
            int id=stt[i][j];
            if(findroot(p[id].first)!=findroot(p[id].second))link(p[id].first,id+n),link(p[id].second,id+n),on[id]=true;
            else{
                split(p[id].first,p[id].second);
                int tmp=t[p[id].second].mn;
                if(t[p[id].second].sz&1)res[i]++,res[min(t[tmp].val,t[id+n].val)]--;
                if(p[id].first==p[id].second)continue;
                if(t[tmp].val>=t[id+n].val)continue;
                on[tmp-n]=false,cut(p[tmp-n].first,tmp),cut(p[tmp-n].second,tmp);
                on[id]=true,link(p[id].first,id+n),link(p[id].second,id+n);
            }
        }
        for(int j=0;j<fin[i].size();j++){
            int id=fin[i][j];
            if(on[id])cut(p[id].first,id+n),cut(p[id].second,id+n);
        }
        if(i)res[i]+=res[i-1];
        puts(res[i]?"No":"Yes");
    }
    return 0;
}

XVII.[SDOI2017]树点涂色

树剖和LCT学到最后实际上是殊途同归的……就比如说这题，可以用树剖，但是在操作1中借鉴了LCT的跳链思想；LCT则因为不能子树修改，按照dfs序需要建出线段树出来，实际上也就是树剖的思想了。

首先讲一下LCT写法。观察到任意时刻，任意一种颜色一定是一条深度递增的链。那么刚好可以被存入LCT的一颗splay中。

因此操作1就是直接access(x)即可。

关于操作2，我们可以采用树上差分的思想。观察到答案具有可减性。我们设res_x表示节点x到根的路径上颜色段数，则路径(x,y)的答案即为res_x+res_y-res_{LCA_{x,y}}+1，其中+1是因为LCA_{x,y}所在的那段颜色被减了两遍。

操作3维护dfs序线段树直接求子树res最值即可（类似于树剖操作）。

至于如何维护res的值呢？我们思考一下，发现它就是你把它access时，所经过的splay的数量。老办法，考虑虚子树的信息。我们只有在access时才会更改虚子树的关系。

我们回忆一下access时我们干了点什么：

inline void access(int x){
    for(register int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}

我们断掉rson的实边，并增加了y的实边。

对于y，少了一个splay，应该整棵子树-1；对于rson，多了一个splay，应该整棵子树+1。

但是！！！别忘了，splay中一切父子关系都是不可靠的。我们必须找到真正的rson和真正的y。而真正的rson和真正的y，就是以它们为根的splay中，深度最浅的点。

然后我们写出了这样的找根函数：

inline int find(int x){
    pushdown(x);
    while(lson)pushdown(x),x=lson;
    return x;
}

使用这个就能找到正确的子节点。

正确的access：

inline void access(int x){
    for(register int y=0,z;x;x=t[y=x].fa){
        splay(x);
        if(rson)z=find(rson),modify(1,1,n,dfn[z],dfn[z]+sz[z]-1,1);
        rson=y;
        if(y)z=find(y),modify(1,1,n,dfn[z],dfn[z]+sz[z]-1,-1);
        pushup(x);
    }
}

总代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
//---------------------------------------------------------
struct Edge{
    int to,next;
}edge[200100];
struct SegTree{
    int tag,mx;
}seg[400100];
struct LCT{
    int fa,ch[2];
    bool rev;
}t[100100];
//---------------------------------------------------------
int head[100100],cnt,sz[100100];
void ae(int u,int v){
    edge[cnt].next=head[u],edge[cnt].to=v,head[u]=cnt++;
    edge[cnt].next=head[v],edge[cnt].to=u,head[v]=cnt++;
}
//---------------------------------------------------------
int dfn[100100],dep[100100],tot,rev[100100];
int anc[100100][18];
void dfs(int x,int fa){
    dep[x]=dep[fa]+1,dfn[x]=++tot,t[x].fa=fa,sz[x]=1,rev[tot]=x,anc[x][0]=fa;
    for(int i=1;(1<<i)<dep[x];i++)anc[x][i]=anc[anc[x][i-1]][i-1];
    for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa)dfs(edge[i].to,x),sz[x]+=sz[edge[i].to];
}
int LCA(int u,int v){
    if(dep[u]>dep[v])swap(u,v);
    for(int i=17;i>=0;i--)if(dep[u]<=dep[v]-(1<<i))v=anc[v][i];
    if(u==v)return u;
    for(int i=17;i>=0;i--)if(anc[u][i]!=anc[v][i])u=anc[u][i],v=anc[v][i];
    return anc[u][0];
}
//---------------------------------------------------------
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
void update(int x){seg[x].mx=max(seg[lson].mx,seg[rson].mx);}
void ADD(int x,int y){seg[x].tag+=y,seg[x].mx+=y;}
void downdate(int x){ADD(lson,seg[x].tag),ADD(rson,seg[x].tag),seg[x].tag=0;}
void build(int x,int l,int r){
    if(l==r){seg[x].mx=dep[rev[l]];return;}
    build(lson,l,mid),build(rson,mid+1,r),update(x);
}
void modify(int x,int l,int r,int L,int R,int val){
    if(l>R||r<L)return;
    if(L<=l&&r<=R){ADD(x,val);return;}
    downdate(x),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val),update(x);
}
int query(int x,int l,int r,int L,int R){
    if(l>R||r<L)return 0;
    if(L<=l&&r<=R)return seg[x].mx;
    downdate(x);
    return max(query(lson,l,mid,L,R),query(rson,mid+1,r,L,R));
}
#undef lson
#undef rson
//---------------------------------------------------------
#define lson t[x].ch[0]
#define rson t[x].ch[1]
inline int identify(int x){
    if(x==t[t[x].fa].ch[0])return 0;
    if(x==t[t[x].fa].ch[1])return 1;
    return -1;
}
inline void pushup(int x){}
inline void REV(int x){t[x].rev^=1,swap(lson,rson);}
inline void pushdown(int x){
    if(!t[x].rev)return;
    if(lson)REV(lson);
    if(rson)REV(rson);
    t[x].rev=0;
}
inline void rotate(int x){
    register int y=t[x].fa;
    register int z=t[y].fa;
    register int dirx=identify(x);
    register int diry=identify(y);
    register int b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[y].fa=x,t[x].ch[!dirx]=y;
    pushup(y),pushup(x);
}
inline void pushall(int x){if(identify(x)!=-1)pushall(t[x].fa);pushdown(x);}
inline void splay(int x){
    pushall(x);
    while(identify(x)!=-1){
        register int fa=t[x].fa;
        if(identify(fa)==-1)rotate(x);
        else if(identify(x)==identify(fa))rotate(fa),rotate(x);
        else rotate(x),rotate(x);
    }
}
inline int find(int x){
    pushdown(x);
    while(lson)pushdown(x),x=lson;
    return x;
}
inline void access(int x){
    for(register int y=0,z;x;x=t[y=x].fa){
        splay(x);
        if(rson)z=find(rson),modify(1,1,n,dfn[z],dfn[z]+sz[z]-1,1);
        rson=y;
        if(y)z=find(y),modify(1,1,n,dfn[z],dfn[z]+sz[z]-1,-1);
        pushup(x);
    }
}
#undef lson
#undef rson
//---------------------------------------------------------
int main(){
    scanf("%d%d",&n,&m),memset(head,-1,sizeof(head));
    for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),ae(x,y);
    dfs(1,0),build(1,1,n);
    for(int i=1,t1,t2,t3;i<=m;i++){
        scanf("%d%d",&t1,&t2);
        if(t1==1)access(t2);
        if(t1==2){
            scanf("%d",&t3);
            int lca=LCA(t2,t3);
            lca=query(1,1,n,dfn[lca],dfn[lca]);
            t2=query(1,1,n,dfn[t2],dfn[t2]);
            t3=query(1,1,n,dfn[t3],dfn[t3]);
            printf("%d\n",t2+t3-2*lca+1);
        }
        if(t1==3)printf("%d\n",query(1,1,n,dfn[t2],dfn[t2]+sz[t2]-1));
    }
    return 0;
}

XVIII.最小差值生成树

这题m^2暴力求最小生成树应该是过不去的……估计只有LCT能过去了。

然后就是同IV.[NOI2014]魔法森林一致的方法，排序之后暴力断边连边即可。

注意会有自环！！！虽然我也不知道为什么没判自环算我MLE……

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,res=0x3f3f3f3f;
struct EDGE{
    int u,v,w;
    friend bool operator <(const EDGE &x,const EDGE &y){
        return x.w<y.w;
    }
}e[200100];
multiset<int>s;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
struct LCT{
    int fa,ch[2],mn,val;
    bool rev;
}t[300100];
inline int identify(int x){
    if(x==t[t[x].fa].ch[0])return 0;
    if(x==t[t[x].fa].ch[1])return 1;
    return -1;
}
inline void pushup(int x){
    t[x].mn=x;
    if(lson&&t[t[x].mn].val>t[t[lson].mn].val)t[x].mn=t[lson].mn;
    if(rson&&t[t[x].mn].val>t[t[rson].mn].val)t[x].mn=t[rson].mn;
}
inline void REV(int x){t[x].rev^=1,swap(lson,rson);}
inline void pushdown(int x){
    if(!t[x].rev)return;
    if(lson)REV(lson);
    if(rson)REV(rson);
    t[x].rev=0;
}
inline void rotate(int x){
    register int y=t[x].fa,z=t[y].fa,dirx=identify(x),diry=identify(y),b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[y].fa=x,t[x].ch[!dirx]=y;
    pushup(y),pushup(x);
}
inline void pushall(int x){if(identify(x)!=-1)pushall(t[x].fa);pushdown(x);}
inline void splay(int x){for(pushall(x);identify(x)!=-1;rotate(x))if(identify(t[x].fa)!=-1)rotate(identify(x)==identify(t[x].fa)?t[x].fa:x);}
inline void access(int x){for(register int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);}
inline void makeroot(int x){access(x),splay(x),REV(x);}
inline int findroot(int x){access(x),splay(x),pushdown(x);while(lson)x=lson,pushdown(x);splay(x);return x;}
inline void split(int x,int y){makeroot(x),access(y),splay(y);}
inline void link(int x,int y){makeroot(x),t[x].fa=y;}
inline void cut(int x,int y){split(x,y),t[y].ch[0]=t[x].fa=0,pushup(y);}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)t[i].val=0x3f3f3f3f;
    for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    sort(e+1,e+m+1);
    for(int i=1;i<=m;i++){
        t[i+n].val=e[i].w;
        if(findroot(e[i].u)!=findroot(e[i].v))s.insert(e[i].w),link(e[i].u,i+n),link(e[i].v,i+n);
        else{
            if(e[i].u==e[i].v)continue;
            split(e[i].u,e[i].v);
            int tmp=t[e[i].v].mn;
            cut(e[tmp-n].u,tmp),cut(e[tmp-n].v,tmp),s.erase(s.find(t[tmp].val)),s.insert(e[i].w),link(e[i].u,i+n),link(e[i].v,i+n);
        }
        if(s.size()==n-1)res=min(res,e[i].w-*s.begin());
    }
    printf("%d\n",res);
    return 0;
}

XIX.首都

一句话题意：维护一棵森林，支持查询某棵树的重心以及所有树的重心的异或和。

众所周知，重心有如下性质：将两棵树之间连一条边后，新树的重心在原两棵树重心的连线上。

根据这一性质，我想了半天也没有想出来什么美妙的算法主要还是我splay没学好

首先，这道题正解有两个，一是LCT+启发式合并（最暴力的断边重连那种），复杂度O(m\log^2 n)；二是LCT+平衡树上二分，复杂度O(m\log n)。

第一种方法过于暴力，没有任何技术含量，但我仍然写不出来，这里就不具体介绍了。

然后第二种方法，就是维护子树大小。每当我们连一条边后，将原两棵树重心连线split出来。然后在splay上二分，保证复杂度是一个\log。

局部代码：

（cen：centroid，重心之义；find(x)即为找到x的重心）

inline void link(int u,int v){
    makeroot(u),makeroot(v),t[u].fa=v,t[v].si+=t[u].sr,pushup(v);
    u=find(u),v=find(v),split(u,v);
    int ls=0,rs=0,mn=0x3f3f3f3f,x=v,lim=t[x].sr>>1;//ls&rs:the size of the subtree outside lson and rson
    while(x){
        pushdown(x);
        int lsum=ls+t[lson].sr,rsum=rs+t[rson].sr;//the size of x's to sons
        if(lsum<=lim&&rsum<=lim)mn=min(mn,x);
        if(lsum<rsum)ls+=t[x].sr-t[rson].sr,x=rson;//add the size of the subtree of x minus the size of the subtree of rson
        else rs+=t[x].sr-t[lson].sr,x=lson;
    }
    cen[u]=cen[v]=cen[mn]=mn,res^=u^v^mn;
}

总代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,cen[100100],res;
int find(int x){return cen[x]==x?x:cen[x]=find(cen[x]);}
#define lson t[x].ch[0]
#define rson t[x].ch[1]
struct LCT{
    int fa,ch[2],si,sr;
    bool rev;
}t[100100];
inline int identify(int x){
    if(x==t[t[x].fa].ch[0])return 0;
    if(x==t[t[x].fa].ch[1])return 1;
    return -1;
}
inline void pushup(int x){
    t[x].sr=t[x].si+1;
    if(lson)t[x].sr+=t[lson].sr;
    if(rson)t[x].sr+=t[rson].sr;
}
inline void REV(int x){t[x].rev^=1,swap(lson,rson);}
inline void pushdown(int x){
    if(!t[x].rev)return;
    if(lson)REV(lson);
    if(rson)REV(rson);
    t[x].rev=0;
}
inline void rotate(int x){
    register int y=t[x].fa,z=t[y].fa,dirx=identify(x),diry=identify(y),b=t[x].ch[!dirx];
    if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
    if(b)t[b].fa=y;t[y].ch[dirx]=b;
    t[y].fa=x,t[x].ch[!dirx]=y;
    pushup(y),pushup(x);
}
inline void pushall(int x){if(identify(x)!=-1)pushall(t[x].fa);pushdown(x);}
inline void splay(int x){for(pushall(x);identify(x)!=-1;rotate(x))if(identify(t[x].fa)!=-1)rotate(identify(x)==identify(t[x].fa)?t[x].fa:x);}
inline void access(int x){for(register int y=0;x;x=t[y=x].fa)splay(x),t[x].si+=t[rson].sr-t[y].sr,rson=y,pushup(x);}
inline void makeroot(int x){access(x),splay(x),REV(x);}
inline int findroot(int x){access(x),splay(x),pushdown(x);while(lson)x=lson,pushdown(x);splay(x);return x;}
inline void split(int x,int y){makeroot(x),access(y),splay(y);}
inline void link(int u,int v){
    makeroot(u),makeroot(v),t[u].fa=v,t[v].si+=t[u].sr,pushup(v);
    u=find(u),v=find(v),split(u,v);
    int ls=0,rs=0,mn=0x3f3f3f3f,x=v,lim=t[x].sr>>1;
    while(x){
        pushdown(x);
        int lsum=ls+t[lson].sr,rsum=rs+t[rson].sr;
        if(lsum<=lim&&rsum<=lim)mn=min(mn,x);
        if(lsum<rsum)ls+=t[x].sr-t[rson].sr,x=rson;
        else rs+=t[x].sr-t[lson].sr,x=lson;
    }
    cen[u]=cen[v]=cen[mn]=mn,res^=u^v^mn;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)cen[i]=i,res^=i;
    for(int i=1,x,y;i<=m;i++){
        char s[5];
        scanf("%s",s);
        if(s[0]=='A')scanf("%d%d",&x,&y),link(x,y);
        if(s[0]=='Q')scanf("%d",&x),printf("%d\n",find(x));
        if(s[0]=='X')printf("%d\n",res);
    }
    return 0;
}

XX.SP16549 QTREE6 - Query on a tree VI

本题LCT全方面爆破树剖——无论是复杂度、码量、思维难度、代码难度，全都碾压树剖。并且，LCT容易模板化，但是树剖不容易——树剖搭配的线段树因题而异，而LCT只需要把pushup和pushdown稍微改改就可以直接粘模板了……

看一下对比吧。

所以，能写LCT，最好不要写树剖……

闲话少说，我们分析一下两种方法各应该怎么写。

LCT的话，我们照例可以跟XII.[ZJOI2012]网络一样，对每种颜色建一棵LCT，并且这题还只有两种颜色黑和白。然后LCT维护虚子树大小，每次就是查询某个点在对应图中的树的大小。看上去就是[ZJOI2012]网络+[BJOI2014]大融合，不至于到黑题呀！

等等，[ZJOI2012]网络是边带色，但这题是点带色！暴力断边的话，如果给你来一张菊花图分分钟爆炸。

怎么办呢？

在前几题中，我们有将LCT边转点的经历——因为LCT只能维护点权而不能维护边权。但是，因为LCT长于断边而短于断点，我们这次点转边。

操作很naive。从1号点开始出发爆搜，每个点的点权转到于它父亲连着的边上。如果一条边为黑，在0号LCT上连上这条边；否则，在1号LCT上连上这条边。为了维护1号点的点权，我们不妨设1的父亲为n+1。

之后，在一个点换颜色时，直接一断一连就行了。并且，因为操作的特殊性，我们这题甚至不需要makeroot，也就是说，不需要区间翻转！这使得就连LCT套treap这种稀奇古怪的东西也可以跑过这道题

当然，这么点边一转，直接输出连通块大小肯定出问题（不信手玩样例一下）。

在统计答案时，我们考虑findroot找出x的树的ROOT。如果ROOT和x颜色相同，那么这个连通块大小就没有问题，可以直接输出。

那么如果ROOT和x颜色不同呢？在findroot后，ROOT同时也是root，并且ROOT和x还在同一棵splay里面。因为ROOT的深度是最小的，因此它的右儿子的size即是x的连通块的大小。

代码（57行）：

#include<bits/stdc++.h>
using namespace std;
int n,m,head[100100],cnt,pa[100100],col[100100];
struct Link_Cut_Tree{
    #define lson ch[0][x]
    #define rson ch[1][x]
    int fa[100100],ch[2][100100],si[100100],sr[100100],self[100100];
    inline int identify(int x){
        if(x==ch[0][fa[x]])return 0;
        if(x==ch[1][fa[x]])return 1;
        return -1;
    }
    inline void pushup(int x){sr[x]=sr[lson]+sr[rson]+si[x]+1;}
    inline void rotate(int x){
        register int y=fa[x],z=fa[y],dirx=identify(x),diry=identify(y),b=ch[!dirx][x];
        if(diry!=-1)ch[diry][z]=x;fa[x]=z;
        if(b)fa[b]=y;ch[dirx][y]=b;
        fa[y]=x,ch[!dirx][x]=y;
        pushup(y),pushup(x);
    }
    inline void splay(int x){for(;identify(x)!=-1;rotate(x))if(identify(fa[x])!=-1)rotate(identify(x)==identify(fa[x])?fa[x]:x);pushup(x);}
    inline void access(int x){for(register int y=0;x;x=fa[y=x])splay(x),si[x]+=sr[rson]-sr[y],rson=y,pushup(x);}
    inline int findroot(int x){access(x),splay(x);while(lson)x=lson;splay(x);return x;}
    inline void link(int x){splay(x);int y=fa[x]=pa[x];access(y),splay(y),si[y]+=sr[x],pushup(y);}
    inline void cut(int x){access(x),splay(x),lson=fa[lson]=0,pushup(x);}
}lct[2];
struct Edge{
    int to,next;
}edge[200100];
void ae(int u,int v){
    edge[cnt].next=head[u],edge[cnt].to=v,head[u]=cnt++;
    edge[cnt].next=head[v],edge[cnt].to=u,head[v]=cnt++;
}
void dfs(int x,int fa){
    pa[x]=fa,lct[0].link(x);
    for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa)dfs(edge[i].to,x);
}
int A(int x){
    int y=lct[col[x]].findroot(x);
    return lct[col[x]].sr[col[y]==col[x]?y:lct[col[x]].ch[1][y]];
}
void R(int x){
    lct[col[x]].cut(x),lct[!col[x]].link(x),col[x]^=1;
}
int main(){
    scanf("%d",&n),memset(head,-1,sizeof(head));
    for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),ae(x,y);
    col[n+1]=2;
    dfs(1,n+1);
    scanf("%d",&m);
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        if(!x)printf("%d\n",A(y));
        else R(y);
    }
    return 0;
}

然后就是树剖了。

树剖这个idea十分诡异：设black_x表示：如果x是黑的（不管它真正的颜色是黑是白），在它的子树内黑色连通块的大小。再设white_x表示：如果x是白的（不管它真正的颜色是黑是白），在它的子树内白色连通块的大小。

则x的答案为：沿着x到1的路径一直往上爬，直到某个点的父亲的颜色和x的颜色不同（如果不存在这样的点，默认是1号节点），则答案就是这个点对应的black或white值。

那么如果一个点的颜色翻转一下，会怎么办呢？

我们假设是黑转白，因为白转黑也是同理。

我们找到fa_x到根的路径上第一个黑节点u，则路径(fa_x,u)上每一个点的black全都应该减去black_x。

我们找到fa_x到根的路径上第一个白节点v，则路径(fa_x,v)上每一个点的white全都应该加上white_x。

思想还比较容易，写起来非常恶心。

代码：

#include<bits/stdc++.h>
using namespace std;
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
int n,m,dfn[100100],rev[100100],fa[100100],dep[100100],son[100100],top[100100],sz[100100],head[100100],cnt,tot,col[100100];
struct node{
    int to,next;
}edge[200100];
void ae(int u,int v){
    edge[cnt].next=head[u],edge[cnt].to=v,head[u]=cnt++;
    edge[cnt].next=head[v],edge[cnt].to=u,head[v]=cnt++;
}
void dfs1(int x,int Fa){
    fa[x]=Fa,dep[x]=dep[Fa]+1,sz[x]=1;
    for(int i=head[x],y;i!=-1;i=edge[i].next){
        if((y=edge[i].to)==fa[x])continue;
        dfs1(y,x),sz[x]+=sz[y];
        if(sz[son[x]]<sz[y])son[x]=y;
    }
}
void dfs2(int x){
    if(son[x])top[son[x]]=top[x],dfn[son[x]]=++tot,rev[tot]=son[x],dfs2(son[x]);
    for(int i=head[x],y;i!=-1;i=edge[i].next){
        y=edge[i].to;
        if(y==fa[x]||y==son[x])continue;
        top[y]=y,dfn[y]=++tot,rev[tot]=y,dfs2(y);
    }
}
struct STA{
    int mx[2][400100];
    void pushup(int x){
        mx[0][x]=max(mx[0][lson],mx[0][rson]);
        mx[1][x]=max(mx[1][lson],mx[1][rson]);
    }
    void build(int x,int l,int r){
        if(l==r){mx[0][x]=l,mx[1][x]=0;return;}
        build(lson,l,mid),build(rson,mid+1,r),pushup(x);
    }
    void rever(int x,int l,int r,int P){
        if(l>P||r<P)return;
        if(l==r){swap(mx[0][x],mx[1][x]);return;}
        rever(lson,l,mid,P),rever(rson,mid+1,r,P),pushup(x);
    }
    int query(int x,int l,int r,int L,int R,int tp){
        if(l>R||r<L)return 0;
        if(L<=l&&r<=R)return mx[tp][x];
        return max(query(lson,l,mid,L,R,tp),query(rson,mid+1,r,L,R,tp));
    }
}sa;
struct STB{
    int val[100100],tag[400100];
    void ADD(int x,int l,int r,int w){
        if(l==r)val[l]+=w;
        else tag[x]+=w;
    }
    void pushdown(int x,int l,int r){
        ADD(lson,l,mid,tag[x]);
        ADD(rson,mid+1,r,tag[x]);
        tag[x]=0;
    }
    void modify(int x,int l,int r,int L,int R,int w){
        if(l>R||r<L)return;
        if(L<=l&&r<=R){ADD(x,l,r,w);return;}
        pushdown(x,l,r),modify(lson,l,mid,L,R,w),modify(rson,mid+1,r,L,R,w);
    }
    int query(int x,int l,int r,int P){
        if(l>P||r<P)return 0;
        if(l==r)return val[P];
        pushdown(x,l,r);
        return query(lson,l,mid,P)+query(rson,mid+1,r,P);
    }
}sb[2];
int gettop(int x,int tp){
    int res=0;
    while(x)res=max(res,sa.query(1,1,n,dfn[top[x]],dfn[x],tp)),x=fa[top[x]];
    return res;
}
int GETTOP(int x,int tp){
    int res=0;
    while(x){
        res=max(res,sa.query(1,1,n,dfn[top[x]],dfn[x],tp));
//      printf("(%d,%d):%d\n",x,top[x],res);
        if(res)return res+1;
        if(col[fa[top[x]]]==tp)return dfn[top[x]];
        x=fa[top[x]];
    }
    return 1;
}
int calc(int x){
    int tmp=GETTOP(x,!col[x]);
//  printf("%d\n",rev[tmp]);
    return sb[col[x]].query(1,1,n,tmp);
}
void modiline(int x,int y,int z,int tp){
    while(top[x]!=top[y]){
        if(dep[x]<dep[y])swap(x,y);
        sb[tp].modify(1,1,n,dfn[top[x]],dfn[x],z);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    sb[tp].modify(1,1,n,dfn[x],dfn[y],z);
}
void REVER(int x){
    if(x==1){sa.rever(1,1,n,dfn[x]),col[x]^=1;return;}
    int tmp1,tmp2;

    tmp1=gettop(fa[x],col[x]),tmp2=sb[!col[x]].query(1,1,n,dfn[x]);
    if(!tmp1)tmp1++;
    tmp1=rev[tmp1];
    modiline(fa[x],tmp1,tmp2,!col[x]);

    tmp1=gettop(fa[x],!col[x]),tmp2=sb[col[x]].query(1,1,n,dfn[x]);
    if(!tmp1)tmp1++;
    tmp1=rev[tmp1];
    modiline(fa[x],tmp1,-tmp2,col[x]);

    sa.rever(1,1,n,dfn[x]),col[x]^=1;
}
int main(){
    scanf("%d",&n),memset(head,-1,sizeof(head));
    for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),ae(x,y);
    dfs1(1,0),rev[1]=top[1]=dfn[1]=tot=1,dfs2(1),sa.build(1,1,n);
    col[0]=2;
//  for(int i=1;i<=n;i++)printf("%d ",dfn[i]);puts("");
    for(int i=1;i<=n;i++)sb[0].val[dfn[i]]=sz[i],sb[1].val[dfn[i]]=1;
    scanf("%d",&m);
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        if(!x)printf("%d\n",calc(y));
        else REVER(y);
    }
    return 0;
}

XXI.[ZJOI2016]大森林

论LCT的百种用法系列

这题有几个性质：

1.询问与时间无关。因为只是添加新点，原来点之间的位置关系不变。因此只要询问的两个点都被建出来了，何时进行询问并无影响。

2.操作重叠的部分很多。因为我们不管怎么加点，即使是加原树中没有的点，仍然有原来点之间的位置关系不变。因此，我们每次加点操作都可以默认是所有树全都加点，不需要管原本l,r的限制。这样的话，某些相似的部分可能在很多树上都出现了。我们是否可以把相似的部分提取出来呢？

我们考虑差分对于生长节点的修改。

对于每次修改，我们都新建一个虚点。在下一次修改之前，所有的生长效果都是在这个虚点上再挂上一个点。这样的话，就在更改生长节点时，就可以直接虚点一断一连即可。

生长操作就是这段代码：

if(t1==0)insnewreal(t2,t3),link(cntofall,lastvir);//a new real node, linked to the previous virtual

对于修改操作：

首先，关注到原题中的一段话：