续命题 (#@*^Y!&

sol

  • 如果同时维护n棵树形态并不可取.

  • 发现所有\text{opt: 2}操作放在加点操作结束后询问答案相同.

故考虑离线维护每棵树的形态, 确切来说, 就是维护当前树与前一棵树的区别.

题目性质

  1. 对于\text{opt: 0}操作生长出的节点, 考虑它在第x棵树对应接到那个节点:

    不难发现, 所连节点就是离这次操作最近的(时间在其之前的)

    且在x处生效的\text{opt: 1}操作的生长节点.

  2. 显然如果我们暴力对所有节点linkcut肯定会TLE

  3. 可以利用“虚点”来解决 2 的问题:

  • 将所有 生长出的点 连向该 生长节点 对应的 虚点 ,

    那么如果更换了生长节点就可以直接对该虚点做O(1)次操作(linkcut)

    即可转移所有的点.

  • 对于题目询问路径(u,v)长度只要记录路径上的实点个数即可.

具体怎么做呢?

我们离线构造完一个虚点序列, 构造如下

  1. 将每一个\text{opt: 1}操作的生长节点对应的虚点按照时间排好序

  2. 将每个虚点连向时间早于它的前一个虚点

  3. 根据前文的性质1, 将每个\text{opt: 0}操作生长出的节点(实点)

    连在时间最接近它的那个\text{opt: 1}操作对应虚点上.

大致长这样的:

那么这序列什么用

首先, 我们对每个\text{opt: 1}操作的虚点定义:

  1. 生效, 即no.x棵树位于\text{opt: 1}对应的区间上
  2. 失效, 不在所对应的区间上.

那么如果虚点生效我们就将它连向对应的实点, 如果它失效就连向前一个虚点.

这样一来, 观察no.1\to n的树的形态是否正确:

  • case1:

如果b’,c’均失效, 也就是上图形成的局面.

那么还是根据性质1, 红圈圈出的点在树上对应着会连在操作时间最接近它且生效的生长点上, 也就是a’.

显然, 图中是满足的(考虑红色箭头对应的路径, 相当于红圈点连在了a’上)

  • case2:

c’ 依旧失效, b’生效.

那么我们会将b’a’的边cut掉, 并将其连在对应实点b

那么还是根据性质1, 红圈点会连在b’上, 由此连向b, 同样符合题意.

故这样可以维护n棵树形态

只要利用Lct维护每次的添删边操作即可, 但需要注意:

我们对于操作[l,r]移动生长节点至x的操作–也就是对应到虚点序列的link

与cut操作: 可以拆成2个独立操作, 即在l处标记该虚点生效, 在r+1处标记为失效.

那么就可以按照pos为第一关键字排序, time为第二关键字排序

从左向右依次处理每个操作即可.

同样的, 由于是有根树, 那么求路径时不可以make_root操作, 否则会影响lcaroot信息

那么我们可以考虑:
f(u, v) = f(u, rt) + f(v, rt) – 2\cdot f(lca, rt)
f(a, b)表示(a,b)路径上的实点个数.

可以证明, 无论lca是实点还是虚点都不会影响答案.

然后就没了, 注意代码细节!!!

Code

须声明这里Lct函数中的link操作:

  void link(int u, int v) {
      splay(u);
      fa(u) = v;
  }

一般是不会这么写的, 因为显然不对.

但是此题中不可以make_root, 而且题目有特殊性质, 故可以这么写

  • 它实质就是将u对应的重边上深度最浅的点连向v

那么观察代码中每次的link操作会发现必然存在一个点为该树的根

所以可以将它当成这里的u, 另一个点当成v, 这样link就没问题了

%:pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 50;

# define pb push_back

namespace {
    inline void read(int &x) {
        x = 0; char c = getchar();
        for(; !isdigit(c); c = getchar());
        for(;  isdigit(c); c = getchar())
            x = (x << 3) + (x << 1) + (c ^ '0');
    }
}

int n, m, opt, x, u, v;
int lasvir, realp, L, R, cnt, l[N], r[N], ans[N];
/*
lasvir 表示上一个虚点的编号
realp 表示上一个实点编号
l[x], r[x] 表示编号为x的点会出现在那些树中
*/
struct Opt {
    int pos, key, x, y;
    Opt() {}
    Opt(int pos, int key, int x, int y) : 
        pos(pos), key(key), x(x), y(y) {}
    bool operator <(Opt const &a) const {
        return (a.pos != pos) ? pos < a.pos : key < a.key;
    }
} a[N];

namespace Lct {
# define fa(x) t[x].fa
# define ls(x) t[x].ch[0]
# define rs(x) t[x].ch[1]
    struct node {
        int val, sum, ch[2], fa;
        node() {}
        node(int val) : val(val) {
            sum = val;
            ch[0] = ch[1] = fa = 0;
        }    
    } t[N]; 

    inline int ch(int x) { return rs(fa(x)) == x; }
    inline int isroot(int x) { return ls(fa(x)) != x && rs(fa(x)) != x; } 
    inline void connect(int u, int v, int c) { t[fa(u) = v].ch[c] = u; }
    inline int S(int x) { return x ? t[x].sum : 0; }
    inline void upd(int x) { t[x].sum = t[x].val + S(ls(x)) + S(rs(x)); }
    void rotate(int x) {
        int y = fa(x), z = fa(y), d = ch(x);
        if(!isroot(y)) connect(x, z, ch(y));
        fa(x) = z;
        connect(t[x].ch[!d], y, d);
        connect(y, x, !d);
        upd(y), upd(x);
    }
    void splay(int x) {
        while(!isroot(x)) {
            int y = fa(x);
            if(!isroot(y)) (ch(x) ^ ch(y)) ? rotate(x) : rotate(y);
            rotate(x);
        }
    }
    int access(int x) {
        int y = 0;
        for(; x; y = x, x = fa(x)) 
            splay(x), rs(x) = y, upd(x);
        return y;
    }
    int lca(int u, int v) {
        return access(u), access(v);
    }
    int path(int x) {
        access(x), splay(x);
        return S(x);
    }
    void link(int u, int v) {
        splay(u);
        fa(u) = v;
    }
    void cut(int u) {
        access(u), splay(u);
        fa(ls(u)) = 0, ls(u) = 0, upd(u);
    }
    int query(int u, int v) {
        int uv = lca(u, v), ans;
        ans = path(u) + path(v) - path(uv) * 2;
        return ans + 1;
    }
# undef ls
# undef rs
}
using Lct :: node;
using Lct :: t;

int main() {
    read(n), read(m);
    l[1] = 1, r[1] = n; // 注意这里, 表示1号生长节点对应区间为[1, n]
    lasvir = m;
    t[++realp] = node(1); // create node 1
    t[++lasvir] = node(0);
    Lct :: link(lasvir, realp); // create virtual node 1'
    for(int i = 1; i <= m; ++i) {
        read(opt);
        if(!opt) {
            read(L), read(R);
            t[++realp] = node(1);
            l[realp] = L, r[realp] = R;
            Lct :: link(realp, lasvir); // 实点连向最近的虚点
        } else if(opt == 1) {
            read(L), read(R), read(x);
            L = max(L, l[x]), R = min(R, r[x]);
            if(L > R) continue;
            t[++lasvir] = node(0);
            Lct :: link(lasvir, lasvir - 1); // 当前虚点与上一个虚点相连, 构成"虚点序列".
            {
                a[++cnt] = Opt(L, i - m, lasvir, x);
                a[++cnt] = Opt(R + 1, i - m, lasvir, lasvir - 1);
            }
        } else {
            read(x), read(u), read(v);
            a[++cnt] = Opt(x, i, u, v);
        }
    }
    sort(a + 1, a + 1 + cnt);
    for(int i = 1; i <= cnt; ++i) {
       if(a[i].key < 0) {
            Lct :: cut(a[i].x);
            Lct :: link(a[i].x, a[i].y);
        } else 
            ans[a[i].key] = Lct :: query(a[i].x, a[i].y);
    }
    for(int i = 1; i <= m; ++i)
        if(ans[i]) printf("%d\n", ans[i] - 1);
    return 0;
}