题解 P5622 【[DBOI2019]巫女的职责】

· · 题解

emmm 这里是萌新的第一篇题解

首先想想没有加边怎么做：

由于维护的是必经点，也就是割点的信息。
很容易想到构建圆方树，对于每个点双连通分量建一个方点，点双中的点都连过去，其它边都去掉。

既然还有动态加边，首先当然是用 \text{Link-Cut Tree} 啦。

对于 2 操作，就直接把 x 点 splay 上去，直接修改点权；对于 3 操作，就是路径求和 + 路径权值变 0，也没什么好说的。

主要说一下 1 操作的做法：

首先两点不连通，当然是直接连上去；如果已连通，就把路径上的边都断掉，所有点都连向一个方点。
这样看起来非常暴力，但实际上时间复杂度是对的：用势能分析容易证明，复杂度为 \text O(q\log n)。

ps：有一个小优化，就是当一条路径上除了两端全是方点时，就直接忽略连边操作，对答案没有影响。

代码如下：

#pragma GCC optimize (2)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 1000003
#define ll long long
using namespace std;

ll sum[N],a[N];
int son[N][2],fa[N],size[N],st[N];
bool tag[N],rev[N],real[N];

inline void pushup(int u){
    size[u] = size[son[u][0]]+size[son[u][1]]+real[u];
    sum[u] = sum[son[u][0]]+sum[son[u][1]]+a[u];
}

inline bool notrt(int u){
    return son[fa[u]][0]==u||son[fa[u]][1]==u;
}

inline void push_tag(int u){
    sum[u] = a[u] = 0;
    tag[u] = true;
}

inline void push_rev(int u){
    swap(son[u][0],son[u][1]);
    rev[u] ^= 1;
}

inline void pushdown(int u){
    if(tag[u]){
        if(son[u][0]) push_tag(son[u][0]);
        if(son[u][1]) push_tag(son[u][1]);
        tag[u] = 0;
    }
    if(rev[u]){
        if(son[u][0]) push_rev(son[u][0]);
        if(son[u][1]) push_rev(son[u][1]);
        rev[u] = 0;
    }
}

inline bool check(int u){
    return son[fa[u]][1]==u;
}

inline void rotate(int x){
    int y = fa[x],z = fa[y];
    int k = son[y][1]==x,w = son[x][k^1];
    if(notrt(y)) son[z][check(y)] = x;
    son[x][k^1] = y;
    son[y][k] = w;
    if(w) fa[w] = y;
    fa[y] = x,fa[x] = z;
    pushup(y);
}

inline void splay(int x){
    int y = x,z = 1;
    st[1] = y;
    while(notrt(y)) st[++z] = y = fa[y];
    while(z) pushdown(st[z--]);
    while(notrt(x)){
        y = fa[x],z = fa[y];
        if(notrt(y)) rotate(check(x)==check(y)?y:x);
        rotate(x);
    }
    pushup(x);
}

inline void access(int u){
    for(int v=0;u;u=fa[v=u])
        splay(u),son[u][1] = v,pushup(u);
}

inline void makeroot(int u){
    access(u),splay(u);
    push_rev(u);
}

inline void link(int u,int v){
    makeroot(u);
    fa[u] = v;
}

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

inline void cut(int u,int v){
    split(u,v);
    son[v][0] = fa[u] = 0;
    pushup(v);
}

inline ll clear(int u,int v){
    split(u,v);
    ll res = sum[v];
    push_tag(v);
    return res;
}

int n,q,top,qaq;
ll ans;
int fk[N],stk[N];

inline int find(int x){
    while(x!=fk[x]) x = fk[x] = fk[fk[x]];
    return x;
}

inline void fuckyou(ll &x){
    x ^= ans%n;
    if(x>n) x %= n;
    if(!x) x = 1;
}

void dfs(int u){
    if(!u) return;
    pushdown(u);
    dfs(son[u][0]);
    stk[++top] = u;
    dfs(son[u][1]);
}

int main(){
    int op;
    ll x,y;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i){
        fk[i] = i;
        real[i] = true;
    }
    qaq = n;
    while(q--){
        scanf("%d%lld%lld",&op,&x,&y);
        fuckyou(x),fuckyou(y);
        if(op==1){
            if(find(x)==find(y)){
                split(x,y);
                if(size[y]<=2) continue;
                top = 0;
                dfs(y);
                ++qaq;
                for(int i=1;i<top;++i) cut(stk[i],stk[i+1]);
                for(int i=1;i<=top;++i) link(stk[i],qaq);
            }else{
                link(x,y);
                fk[find(x)] = find(y);
            }
        }else if(op==2){
            splay(x);
            a[x] += y;
        }else{
            ans = find(x)==find(y)?clear(x,y):0ll;
            printf("%lld\n",ans);
        }
    }
}

因为之前有一道 P5489 所以这题就显得比较模板（