「v3」D - 数据结构

    「v3」D - 数据结构

    一些技巧与思想也会归类于数据结构。

    D - 数据结构 序列结构

    树状数组

    lowbit(x)\mathrm{lowbit}(x) 函数:表示 xx 的二进制表示中,最低位的 11 的数值大小,lowbit(x) = x & -x。

    cic_i 的管辖区间:[i−lowbit(i)+1,i][i - \mathrm{lowbit}(i) + 1, i]。

    O(n)\mathcal{O}(n) 建树:

    • 方法一:每一个节点的值是由所有与自己直接相连的儿子的值求和得到的,因此可以倒着考虑贡献。每次确定完 cic_i 的值后,用 cic_i 的值更新 ci+lowbit(i)c_{i + \mathrm{lowbit}(i)}。
    • 方法二:预处理前缀和数组,则 ci=prei−prei−lowbitic_i = \mathrm{pre}_i - \mathrm{pre}_{i - \mathrm{lowbit}_i}。

    O(log⁡n)\mathcal{O}(\log n) 查询第 kk 小:树状数组维护每个数的出现次数,倍增求解。

    线段树

    • 任意区间 [l,r][l, r] 在线段树上,至少需要 O(log⁡n)\mathcal{O}(\log n) 个节点覆盖。

    动态开点线段树 & 线段树合并 & 线段树分裂

    • 动态开点线段树,单次插入新建节点个数 O(log⁡A)\mathcal{O}(\log A)。其中 AA 表示值域大小。
    • 动态开点线段树可以使用懒标记,下传标记时需要新建结点(若标记对空节点无影响则不必新建节点)。
    • 遇到仅针对某个权值的修改和询问时,可以考虑对每个权值开一个动态开点线段树。
    • 线段树合并单次复杂度,取决于两棵线段树的交集大小;线段树合并总复杂度,取决于所有线段树的节点总数。
    • 线段树合并支持持久化,需要在合并时新建节点。
    • 在线段树合并的过程中,可以统计来自不同线段树且具有相对顺序关系的信息。例如逆序对。
    • 在线段树合并的过程中,在处理复杂的问题时,可以尝试分成以下几类讨论(其中 2, 3 是讨论重点):
      1. p,qp, q 均为空节点:返回空节点。
      2. p,qp, q 中分别有一个空节点和一个非空节点:特殊讨论。
      3. 线段树递归到叶子节点(即 l=rl = r):特殊讨论。
      4. p,qp, q 均为非空节点:分别合并 p,qp, q 的左儿子与 p,qp, q 的右儿子,最后 update。
    • 线段树分裂单次复杂度 O(log⁡A)\mathcal{O}(\log A),新建节点个数 O(log⁡A)\mathcal{O}(\log A)。
    namespace SGT {
        const int pond = ...;
    
        int nClock, root[N];
        struct node {
            int lc, rc;
            int cnt;
        } t[pond];
    
        int create() {
            int p = ++ nClock;
            t[p].lc = t[p].rc = t[p].cnt = 0;
            return p;
        }
    
        void upd(int p) {
            t[p].cnt = t[t[p].lc].cnt + t[t[p].rc].cnt;
        }
    
        void insert(int &p, int l, int r, int x, int val) {
            if (!p) p = create();
            t[p].cnt += val;
            if (l == r) return;
    
            int mid = (l + r) >> 1;
    
            if (x <= mid)
                insert(t[p].lc, l, mid, x, val);
            else
                insert(t[p].rc, mid + 1, r, x, val);
        }
    
        int merge(int p, int q) {
            if (!p || !q) return p ^ q;
            t[p].cnt += t[q].cnt;
            t[p].lc = merge(t[p].lc, t[q].lc);
            t[p].rc = merge(t[p].rc, t[q].rc);
            return p;
        }
    
    /* 可持久化线段树合并 
        int merge(int p, int q) {
            if (!p || !q) return p ^ q;
            int u = ++ nClock;
            t[u].cnt = t[p].cnt + t[q].cnt;
            t[u].lc = merge(t[p].lc, t[q].lc);
            t[u].rc = merge(t[p].rc, t[q].rc);
            return u; 
        }
    */
    
        void split_v(int p, int l, int r, int val, int &x, int &y) {
            if (!p)
                x = y = 0;
            else {
                int mid = (l + r) >> 1;
                if (mid < val)
                    x = p, y = create(), split_v(t[p].rc, mid + 1, r, val, t[x].rc, t[y].rc);
                else if (mid == val)
                    x = create(), y = create(), t[x].lc = t[p].lc, t[y].rc = t[p].rc;
                else
                    x = create(), y = p, split_v(t[p].lc, l, mid, val, t[x].lc, t[y].lc);
                upd(x), upd(y);
            }
        }
    
        void split_s(int p, int sze, int &x, int &y) {
            if (!p)
                x = y = 0;
            else {
                if (t[t[p].lc].cnt < sze)
                    x = p, y = create(), split_s(t[p].rc, sze - t[t[p].lc].cnt, t[x].rc, t[y].rc);
                else if (t[t[p].lc].cnt == sze)
                    x = create(), y = create(), t[x].lc = t[p].lc, t[y].rc = t[p].rc;
                else
                    x = create(), y = p, split_s(t[p].lc, sze, t[x].lc, t[y].lc);
                upd(x), upd(y);
            }
        }
    }

    主席树

    • 主席树可以作为线段树的前缀和来使用。
    • 主席树区间修改,可以标记永久化。
    • 主席树可以将其他版本树的某段区间,嫁接到当前版本树的该段区间上。但要注意将公共部分的标记永久化下放。
    namespace SGT {
        int pond = ...;
    
        int nClock, root[N]; 
        struct node {
            int lc, rc;
            int cnt;
        } t[pond];
    
        void insert(int &p, int q, int l, int r, int x, int val) {
            p = ++ nClock, t[p] = t[q];
            t[p].cnt += val;
            if (l == r) return;
    
            int mid = (l + r) >> 1;
    
            if (x <= mid)
                insert(t[p].lc, t[q].lc, l, mid, x, val);
            else
                insert(t[p].rc, t[q].rc, mid + 1, r, x, val);
        }
    }
    namespace SGT {
        const int pond = ...;
    
        int nClock, root[N];
        struct node {
            int lc, rc;
            int sum;
            int add;
        } t[pond];
    
        void change(int &p, int q, int l, int r, int s, int e, int val) {
            p = ++ nClock, t[p] = t[q];
            if (s <= l && r <= e) { t[p].add += val; return; }
            t[p].sum += (std::min(r, e) - std::max(l, s) + 1) * val;
    
            int mid = (l + r) >> 1;
    
            if (s <= mid)
                change(t[p].lc, t[q].lc, l, mid, s, e, val);
            if (mid < e)
                change(t[p].rc, t[q].rc, mid + 1, r, s, e, val);
        }
    
        int ask(int p, int l, int r, int s, int e) {
            if (s <= l && r <= e)
                return t[p].sum + (r - l + 1) * t[p].add;
    
            int mid = (l + r) >> 1;
            int cur = (std::min(r, e) - std::max(l, s) + 1) * t[p].add;
    
            if (s <= mid)
                cur += ask(t[p].lc, l, mid, s, e);
            if (mid < e)
                cur += ask(t[p].rc, mid + 1, r, s, e);
    
            return cur;
        }
    }

    势能线段树

    • 势能线段树,用于维护修改操作使得被修改元素的势能迅速向零势能逼近的信息。
    • 在区间修改时,暴力往叶子节点递归。若递归途中遇到某个节点,该节点的对应区间内每个元素都不能进行有效修改,则在该节点 return。
    • 在无修改操作时,时间复杂度为 O(nαlog⁡n)\mathcal{O}(n\alpha\log n)。其中 α\alpha 为有效修改次数上限。

    区间开平方:一个正整数 xx 被开方 O(log⁡log⁡x)\mathcal{O}(\log \log x) 次后会变成 11。若区间最大值 =1= 1,则 return。

    区间取模:一个整数 xx 对 pp 取模,若 x≥px \geq p,则 xx 至少变小一半。若区间最大值 <p< p,则 return。

    区间除法、区间加:整除一个数 pp,会使区间最大值与最小值的差至少变小一半。

    • 若 max⁡−min⁡=0\max - \min = 0,则打加法标记。
    • 若 max⁡−min⁡=1\max - \min=1 且 ⌊max⁡p⌋≠⌊min⁡p⌋\left\lfloor\frac{\max}{p}\right\rfloor \neq \left\lfloor\frac{\min}{p}\right\rfloor,则打加法标记。

    区间按位与:一个二进制数 xx 对 vv 进行按位与,相当于是把所有 vv 为 00 的位,在 xx 中强制置为 00。若 vv 为 00 的位置集合被区间按位或和为 00 的位置集合包含,则 return。

    区间取最值(吉司机线段树):以区间取最小值为例。

    • 在线段树上的每一个节点 pp,需要维护:
      • max⁡\max:区间最大值。
      • cnt\mathrm{cnt}:区间最大值的个数。
      • smax\mathrm{smax}:区间严格次大值。
    • 在区间修改时,若递归途中遇到一个被询问区间完全包含的节点 pp 时:
      • 若 x≥max⁡px \geq \max_p,则 return。
      • 若 x≤smaxpx \leq \mathrm{smax}_p,则暴力往左右儿子递归。
      • 若 smaxp<x<max⁡p\mathrm{smax}_p < x < \max_p,则有 cnt\mathrm{cnt} 个 max⁡p\max_p 被改为 xx。打标记即可。
    • 无区间加时,时间复杂度 O(nlog⁡n)\mathcal{O}(n \log n)。
    • 有区间加时,时间复杂度 O(nlog⁡2n)\mathcal{O}(n \log^2 n)。

    历史线段树

    • 待填。

    李超线段树

    • 李超线段树,用于维护一个二维平面,支持插入一个定义域为 [l,r][l, r] 的一次函数 kx+bkx + b,查询某个横坐标上最大的函数值。
    • 李超线段树上的每一个节点,需要维护区间的优势线段(在 mid\mathrm{mid} 处取到最大函数值的线段),用标记永久化的方法处理。
    • 李超线段树支持持久化。
    • 李超线段树合并总复杂度,取决于所有线段树的节点总数。
    • 李超线段树合并支持持久化,需要在合并时新建节点。
    • 李超线段树仅支持插入函数,不支持删除函数。但可以考虑线段树分治。
    const int inf = 0x3f3f3f3f; 
    
    struct func {
        int k, b;
    
        func() { k = b = 0; }
        func(int A, int B) : k(A), b(B) {}
    
        int calc(int x) {
            return k * x + b; 
        }
    };
    
    namespace SGT {
        const int pond = ...;
    
        int nClock, root[N];
        struct node {
            int lc, rc;
            func p;
        } t[pond];
    
        int create() {
            int p = ++ nClock;
            t[p].lc = t[p].rc = 0, t[p].p = func();
            return p;
        }
    
        void insert(int &p, int l, int r, func q) {
            if (!p) {
                p = create(), t[p].p = q;
                return;
            }
    
            int pl = t[p].p.calc(l), pr = t[p].p.calc(r);
            int ql = q.calc(l), qr = q.calc(r);
    
            if (pl >= ql && pr >= qr) return;
            if (ql >= pl && qr >= pr) { t[p].p = q; return; }
    
            int mid = (l + r) >> 1;
    
            if (t[p].p.calc(mid) < q.calc(mid))
                std::swap(t[p].p, q), std::swap(pl, ql);
    
            if (pl <= ql)
                insert(t[p].lc, l, mid, q);
            else
                insert(t[p].rc, mid + 1, r, q); 
        }
    
        void insert(int &p, int l, int r, int s, int e, func q) {
            if (!p) p = create();
            if (s <= l && r <= e) {
                insert(p, l, r, q);
                return;
            }
    
            int mid = (l + r) >> 1;
    
            if (s <= mid)
                insert(t[p].lc, l, mid, s, e, q);
            if (mid < e)
                insert(t[p].rc, mid + 1, r, s, e, q);
        }
    
        int merge(int p, int q, int l, int r) {
            if (!p || !q) return p ^ q;
    
            int mid = (l + r) >> 1;
    
            t[p].lc = merge(t[p].lc, t[q].lc, l, mid);
            t[p].rc = merge(t[p].rc, t[q].rc, mid + 1, r);
            insert(p, l, r, t[q].p);
    
            return p;
        }
    
        int ask(int p, int l, int r, int x) {
            if (!p) return -inf;
            if (l == r) return t[p].p.calc(x);
            int mid = (l + r) >> 1;
            if (x <= mid)
                return std::max(ask(t[p].lc, l, mid, x), t[p].p.calc(x));
            else
                return std::max(ask(t[p].rc, mid + 1, r, x), t[p].p.calc(x));
        }
    }

    楼房重建式线段树

    参考:https://www.cnblogs.com/PinkRabbit/p/Segment-Tree-and-Prefix-Maximums.html

    写法 1:当需要维护的信息满足可减性时,可以考虑采用写法 1。

    • 在线段树上的每一个节点 pp,需要维护:

      • max⁡[p]\max[p]:区间最大值。
      • dat[p]\mathrm{dat}[p]:区间内所有前缀最大值的信息和。
    • 定义函数 calc(p,pre)\mathrm{calc}(p, \mathrm{pre}) 表示以 pre\mathrm{pre} 为初始的前缀最大值时,区间内所有前缀最大值的信息和。

      • 若 pp 为叶节点,则 calc(p,pre)=[pre<max[p]]\mathrm{calc}(p, \mathrm{pre}) = [\mathrm{pre} < \mathrm{max}[p]]。
      • 若 pre<max⁡[lc[p]]\mathrm{pre} < \max[\mathrm{lc}[p]],此时考虑完左子树后前缀最大值必定为 max⁡[lc[p]]\max[\mathrm{lc}[p]],而右子树的信息和可以通过做差得到。
      calc(p,pre)=calc(lc[p],pre)+(dat[p] deduct dat[rc[p]])\mathrm{calc}(p, \mathrm{pre}) = \mathrm{calc}(\mathrm{lc}[p], \mathrm{pre}) + (\mathrm{dat}[p] \ \mathrm{deduct} \ \mathrm{dat}[\mathrm{rc}[p]])
      • 若 pre≥max⁡[lc[p]]\mathrm{pre} \geq \max[\mathrm{lc}[p]],此时左子树不会出现前缀最大值,只需考虑右子树即可。
      calc(p,pre)=calc(rc[p],pre)\mathrm{calc}(p, \mathrm{pre}) = \mathrm{calc}(\mathrm{rc}[p], \mathrm{pre})
    • update 时,有 dat[p]=dat[lc[p]]+calc(rc[p],max⁡[lc[p]])\mathrm{dat}[p] = \mathrm{dat}[\mathrm{lc}[p]] + \mathrm{calc}(\mathrm{rc}[p], \max[\mathrm{lc}[p]])。

    写法 2:当需要维护的信息不满足可减性时,可以考虑采用写法 2。

    • 在线段树上的每一个节点 pp,需要维护:

      • max⁡[p]\max[p]:区间最大值。
      • dat[p]\mathrm{dat}[p]:以左子树的区间最大值为初始的前缀最大值时,右子树内所有前缀最大值的信息和。特别地,叶子无定义。
    • 定义函数 calc(p,pre)\mathrm{calc}(p, \mathrm{pre}) 表示以 pre\mathrm{pre} 为初始的前缀最大值时,区间内所有前缀最大值的信息和。

      • 若 pp 为叶节点,则 calc(p,pre)=[pre<max[p]]\mathrm{calc}(p, \mathrm{pre}) = [\mathrm{pre} < \mathrm{max}[p]]。
      • 若 pre<max[lc[p]]\mathrm{pre} < \mathrm{max}[\mathrm{lc}[p]],同上
      calc(p,pre)=calc(lc[p],pre)+dat[p]\mathrm{calc}(p, \mathrm{pre}) = \mathrm{calc}(\mathrm{lc}[p], \mathrm{pre}) + \mathrm{dat}[p]
      • 若 pre≥max⁡[lc[p]]\mathrm{pre} \geq \max[{\mathrm{lc}[p]}],同上
      calc(p,pre)=calc(rc[p],pre)\mathrm{calc}(p, \mathrm{pre}) = \mathrm{calc}(\mathrm{rc}[p], \mathrm{pre})
    • update 时,有 dat[p]=calc(rc[p],max⁡[lc[p]])\mathrm{dat}[p] = \mathrm{calc}(\mathrm{rc}[p], \max[\mathrm{lc}[p]])。

    猫树

    • 建猫树时,采用堆式建树(节点 pp 的左、右儿子分别为 2p2p 与 2p+12p + 1)。具体实现时不必显式地将左右儿子的结构建出来,只需记录每一层深度的具体信息,与每个元区间 [l,l][l, l] 对应的叶子节点编号即可。
    • 若将序列长度补成 22 的整数次幂:不难发现左儿子编号为父节点编号左移一位,右儿子编号为父节点编号左移一位再加一。
      • 故 [l,l][l, l] 与 [r,r][r, r] 的代表节点 x,yx, y 的 LCA 即为 x,yx, y 二进制下从高位向低位的 LCP。
      • 若 [l,l][l, l] 与 [r,r][r, r] 的代表节点为 x,yx, y,则 LCA 编号为 x >> logx[x ^ y],深度为 logx[x] - logx[x ^ y]。特别要注意的是 logx[0] = 0。
    namespace SGT {
        int dep[N * 4];
    
        int idx[N];
        int f[logN][N];
    
        void build(int p, int l, int r) {
            dep[p] = dep[p / 2] + 1;
        
            int mid = (l + r) >> 1; 
    
            // Calculate the data of the interval [l, mid]
    
            // Calculate the data of the interval [mid + 1, r]
    
            if (l == r) idx[l] = p;
            else build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r);
        }
    
        int ask(int l, int r) {
            int x = idx[l], y = idx[r];
        
            if (dep[x] > dep[y]) std::swap(x, y);
            while (dep[x] < dep[y]) y /= 2;
    
            while (x ^ y) x /= 2, y /= 2;
    
            return ...;
        }
    }
    namespace SGT {
        const int H = ...;
    
        int h, logx[H];
    
        int idx[H];
        int f[logH][H];
    
        void init() {
            h = 1;
            while (h < n) h <<= 1;
    
            logx[0] = 0;
            for (int i = 1; i <= h; i ++) logx[i] = logx[i >> 1] + 1;
        }
    
        void build(int p, int l, int r, int dep) {
            int mid = (l + r) >> 1; 
    
            // Calculate the data of the interval [l, mid]
    
            // Calculate the data of the interval [mid + 1, r]
    
            if (l == r) idx[l] = p;
            else build(p * 2, l, mid, dep + 1), build(p * 2 + 1, mid + 1, r, dep + 1);
        }
        
        int ask(int l, int r) {
            int x = idx[l], y = idx[r];
            int z_dep = logx[x] - logx[x ^ y];
    
            return ...;
        }
    }

    平衡树

    splay

    • splay 核心思想:每次操作完后,通过双旋 & 单旋将相关节点 xx 旋转至根,以此维持树高稳定。
    • splay 的三种旋转:
      • 当 xx 的父亲 pp 是根节点时,直接 zig/zag xx。
      • 当 xx 和上两代祖先位于一条链上:先 zig/zag pp,再 zig/zag xx。
      • 当 xx 和上两代祖先分叉时:先 zig/zag xx,再 zig/zag xx。
    • splay 基于均摊分析,不支持持久化。
    • splay 启发式合并的时间复杂度 O(nlog⁡n)\mathcal{O}(n \log n)(splay 是 Dynamic Finger Search Tree,需要保证第二棵树按中序遍历的顺序插入)。
    const int inf = 0x3f3f3f3f;
    namespace BST {
        int nClock, root;
        struct node {
            int son[2], Fa;
            int val;
            int sze;
            bool rev;
    
            #define lc son[0]
            #define rc son[1]
    
            void mk_rev() {
                std::swap(lc, rc);
                rev ^= 1;
            }
        } t[N];
    
        int create(int Fa_p, int val) {
            int p = ++ nClock;
            t[p].lc = t[p].rc = 0, t[p].Fa = Fa_p;
            t[p].val = val;
            t[p].sze = 1;
            t[p].rev = 0;
            return p;
        }
    
        void upd(int p) {
            t[p].sze = t[t[p].lc].sze + t[t[p].rc].sze + 1;
        }
    
        void spread(int p) {
            if (t[p].rev) {
                if (t[p].lc) t[t[p].lc].mk_rev();
                if (t[p].rc) t[t[p].rc].mk_rev();
                t[p].rev = 0;
            }
        }
    
        int dir(int x) {
            return t[t[x].Fa].rc == x;
        }
    
        void rotate(int x) {
            int y = t[x].Fa, z = t[y].Fa, k = dir(x);
            t[x].Fa = z; if (z) t[z].son[t[z].rc == y] = x;
            t[y].son[k] = t[x].son[k ^ 1], t[t[x].son[k ^ 1]].Fa = y;
            t[x].son[k ^ 1] = y, t[y].Fa = x;
            upd(y), upd(x);
        }
    
        void splay(int x, int tar) {
            int p;
            while (p = t[x].Fa, p != tar) {
                if (t[p].Fa != tar) rotate(dir(x) == dir(p) ? p : x);
                rotate(x);
            }
            if (!tar) root = x;
        }
    
        int find(int val) {
            int x = root, ans = 0;
            while (x) {
                spread(x);
                if (t[x].val == val) { ans = x; break; }
                x = t[x].son[val > t[x].val];
            }
            return ans;
        }
    
        int find_max(int p) {
            int x = p;
            while (spread(x), t[x].rc) x = t[x].rc;
            return x;
        }
    
        void insert(int val) {
            int x = root, Fa_x = 0;
            while (x) {
                spread(x);
                Fa_x = x;
                x = t[x].son[val > t[x].val];
            }
            x = create(Fa_x, val), t[Fa_x].son[val > t[Fa_x].val] = x;
            splay(x, 0);
        }
    
        void remove(int val) {
            int x = find(val), p;
            if (!x) return;
    
            splay(x, 0);
    
            if (t[x].lc) {
                p = find_max(t[x].lc), splay(p, x);
                t[p].rc = t[x].rc, t[t[x].rc].Fa = p, t[p].Fa = 0, upd(p);
                root = p;
            } else {
                t[t[x].rc].Fa = 0;
                root = t[x].rc;
            }
        }
    
        int ask_rk(int val) {
            int x = root, Fa_x = 0, cnt = 0;
            while (x) {
                spread(x);
                Fa_x = x;
    
                if (val > t[x].val) {
                    cnt += t[t[x].lc].sze + 1;
                    x = t[x].rc;
                } else {
                    x = t[x].lc;
                }
            }
    
            splay(Fa_x, 0);
            return cnt + 1;
        }
    
        int ask_val(int rk) {
            int x = root, Fa_x = 0, ans = 0;
            while (x) {
                spread(x);
                Fa_x = x;
     
                if (rk <= t[t[x].lc].sze) {
                    x = t[x].lc;
                } else if (rk == t[t[x].lc].sze + 1) {
                    ans = t[x].val;
                    break;
                } else {
                    rk -= t[t[x].lc].sze + 1;
                    x = t[x].rc;
                }
            }
    
            splay(Fa_x, 0);
            return ans;
        }
    
        int ask_prev(int val) {
            int x = root, Fa_x = 0, ans = -inf;
            while (x) {
                spread(x);
                Fa_x = x;
    
                if (val <= t[x].val) {
                    x = t[x].lc;
                } else {
                    ans = std::max(ans, t[x].val);
                    x = t[x].rc;
                }
            }
    
            splay(Fa_x, 0);
            return ans;
        }
    
        int ask_next(int val) {
            int x = root, Fa_x = 0, ans = inf;
            while (x) {
                spread(x);
                Fa_x = x;
    
                if (val >= t[x].val) {
                    x = t[x].rc;
                } else {
                    ans = std::min(ans, t[x].val);
                    x = t[x].lc;
                }
            }
    
            splay(Fa_x, 0);
            return ans;
        }
    }

    FHQ treap

    • treap 的每个节点有两个关键字 val\mathrm{val} 与 dat\mathrm{dat},其中数值 val\mathrm{val} 满足 BST 性质,随机键值 key\mathrm{key} 满足 heap 性质。故 treap 为笛卡尔树。
    • treap 的随机性,可以保证期望树高为 O(log⁡n)\mathcal{O}(\log n),分析同快速排序。
    • 当 FHQ treap 用作区间树时,可以用笛卡尔树的建树方式 O(n)\mathcal{O}(n) 建树。
    • FHQ treap 的合并操作,不能合并值域有交集的两棵树。
    • FHQ treap 支持持久化,需要在分裂时复制节点。涉及到打标记时,需要在标记下传时复制节点。在合并时要用 rand() % (t[p].sze + t[q].sze) < t[p].sze 来代替随机键值大小的判断。
    • FHQ treap 可以用持久化的方式复制区间。
    namespace BST {
        int nClock, root;
        struct node {
            int lc, rc;
            int val, key;
            int sze;
            bool rev;
    
            void mk_rev() {
                std::swap(lc, rc);
                rev ^= 1;
            }
        } t[N];
    
        int create(int val) {
            int p = ++ nClock;
            t[p].lc = t[p].rc = 0;
            t[p].val = val, t[p].key = rand();
            t[p].sze = 1;
            t[p].rev = 0;
            return p;
        }
    
    /* 可持久化平衡树
        int copy(int q) {
            int p = ++ nClock; t[p] = t[q];
            return p;
        } 
    */
    
        void upd(int p) {
            t[p].sze = t[t[p].lc].sze + t[t[p].rc].sze + 1;
        }
    
        void spread(int p) {
            if (t[p].rev) {
                if (t[p].lc) t[t[p].lc].mk_rev();
                if (t[p].rc) t[t[p].rc].mk_rev();
                t[p].rev = 0;
            }
        }
    
    /* 可持久化平衡树
        void spread(int p) {
            if (t[p].rev) {
                if (t[p].lc) t[p].lc = copy(t[p].lc), t[t[p].lc].mk_rev();
                if (t[p].rc) t[p].rc = copy(t[p].rc), t[t[p].rc].mk_rev();
                t[p].rev = 0;
            }
        }
    */
    
        void split_v(int p, int val, int &x, int &y) {
            if (!p)
                x = y = 0;
            else {
                spread(p);
                if (t[p].val <= val)
                    x = p, split_v(t[p].rc, val, t[x].rc, y);
                else
                    y = p, split_v(t[p].lc, val, x, t[y].lc);
                upd(p);
            }
        }
    
        void split_s(int p, int sze, int &x, int &y) {
            if (!p)
                x = y = 0;
            else {
                spread(p);
                if (t[t[p].lc].sze < sze)
                    x = p, split_s(t[p].rc, sze - t[t[p].lc].sze - 1, t[x].rc, y);
                else
                    y = p, split_s(t[p].lc, sze, x, t[y].lc);
                upd(p);
            }
        }
    
    /* 可持久化平衡树
        void split_v(int p, int val, int &x, int &y) {
            if (!p)
                x = y = 0;
            else {
                p = copy(p), spread(p);
                if (t[p].val <= val)
                    x = p, split_v(t[p].rc, val, t[x].rc, y);
                else
                    y = p, split_v(t[p].lc, val, x, t[y].lc);
                upd(p);
            }
        }
    
        void split_s(int p, int sze, int &x, int &y) {
            if (!p)
                x = y = 0;
            else {
                p = copy(p), spread(p);
                if (t[t[p].lc].sze < sze)
                    x = p, split_s(t[p].rc, sze - t[t[p].lc].sze - 1, t[x].rc, y);
                else
                    y = p, split_s(t[p].lc, sze, x, t[y].lc);
                upd(p);
            }
        }
    */
    
        int merge(int p, int q) {
            if (!p || !q) return p ^ q;
            if (t[p].key > t[q].key) {
                spread(p);
                t[p].rc = merge(t[p].rc, q), upd(p);
                return p;
            } else {
                spread(q);
                t[q].lc = merge(p, t[q].lc), upd(q);
                return q;
            }
        }
    
    /* 可持久化平衡树 
        int merge(int p, int q) {
            if (!p || !q) return p ^ q;
            if (rand() % (t[p].sze + t[q].sze) < t[p].sze) {
                spread(p);
                t[p].rc = merge(t[p].rc, q), upd(p);
                return p;
            } else {
                spread(q);
                t[q].lc = merge(p, t[q].lc), upd(q);
                return q;
            }
        }
    */
    }

    树套树

    树状数组套线段树

    • 常用于动态维护线段树的前缀和。

    线段树套线段树

    • 常用于动态维护一个 n×mn \times m 的矩形。涉及到区间修改时,需要标记永久化。

    线段树套平衡树

    • 常用于动态维护平衡树的区间和。

    笛卡尔树

    • 每个节点由一个二元组 (key,val)(\mathrm{key}, \mathrm{val}) 组成,其中键值 key\mathrm{key} 满足 BST 性质,权值 val\mathrm{val} 满足 heap 性质。
    • 若每个节点的 key,val\mathrm{key}, \mathrm{val} 均互不相同,则笛卡尔树的形态是唯一的。

    建树:以大根堆为例,将所有元素按 key\mathrm{key} 从小到大排序。每次插入的元素必然在该笛卡尔树的右链上(BST 性质),在右链查找第一个大于等于当前值的节点,将链拆成两部分,上半部分的下端接在当前节点的父亲上,下半部分的上端接在当前节点的左儿子上。

    namespace CAR {
        int root;
        struct node {
            int lc, rc;
        } t[N];
    
        void build() {
            static int top, stk[N];
            for (int i = 1; i <= n; i ++) {
                int k = top;
                while (k && a[stk[k]] < a[i]) k --;
    
                if (k) t[stk[k]].rc = i;
                if (k < top) t[i].lc = stk[k + 1];
    
                stk[top = k + 1] = i;
            }
    
            root = stk[1];
        }
    }
    • 对序列 aa 建笛卡尔树(小根堆),则 vv 为 uu 的祖先当且仅当 ava_v 是 u,vu, v 之间的最小值。

    分块

    • Bn 为分块大小,t 为分块数量,Lp[], Rp[] 为当前块的左右端点,belong[] 为当前点所属块的编号。
    int n, Bn;
    int t, Lp[Size_Bn], Rp[Size_Bn], belong[N];
    int main() {
        for (int i = Bn; i <= n; i += Bn) t ++, Lp[t] = i - Bn + 1, Rp[t] = i;
        if (Rp[t] < n) t ++, Lp[t] = Rp[t - 1] + 1, Rp[t] = n;
    
        for (int i = 1; i <= n; i ++) belong[i] = (i - 1) / Bn + 1;
    }
    • 当遇到单点修改、区间查询时,可以考虑用分块优化到 O(1)\mathcal{O}(1) 修改 O(n)\mathcal{O}(\sqrt{n}) 查询。
    • 当遇到区间修改、单点查询时,可以考虑用分块优化到 O(n)\mathcal{O}(\sqrt{n}) 修改 O(1)\mathcal{O}(1) 查询。
    • 当遇到区间修改、区间查询时,可以考虑用差分转化为单点修改、区间查询。
    • 当遇到限定 i→i+kii \to i + k_i,询问从 xx 出发首次 ≥y\geq y 的行动步数时,可以预处理每个元素走出所在块后到达的点及所需步数。
    • 当遇到区间 [l,r][l, r] 的子区间 [l′,r′](l≤l′≤r′≤r)[l', r'](l \leq l' \leq r' \leq r) 统计问题时,可以尝试分成以下几类讨论:
      • l′,r′l', r' 均在整块内。
      • l′,r′l', r' 中分别有一个在整块内、一个在散块内。
      • l′l' 在左散块,r′r' 在右散块。
      • l′,r′l', r' 均在左散块或 l′,r′l', r' 均在右散块。
    • 特别要注意的是,在使用 sqrt() 前要调用 #include <cmath>。

    莫队

    普通莫队

    • 最优排序方式等价于平面曼哈顿距离最短哈密顿路径,这是 NP 完全问题。
    • 莫队排序方式:
      • 第一关键字升序:左端点 ll 所在块编号。
      • 第二关键字升序:右端点 rr。
    • 奇偶性优化:当 belong[l]\mathrm{belong}[l] 为奇数时,第二关键字升序;当 belong[l]\mathrm{belong}[l] 为偶数时,第二关键字降序。
    • 当左右端点扩展时,为避免出现 l>rl > r 的情况,尽量保证区间先扩大,后缩小。
    • 当 n,mn, m 同阶时,分块大小 O(n)\mathcal{O}(\sqrt{n}),时间复杂度 O(nn)\mathcal{O}(n\sqrt{n})。
    • 当 n,mn, m 不同阶时,分块大小 O(nm−12)\mathcal{O}(nm^{-\frac{1}{2}}),时间复杂度 O(nm12)\mathcal{O}(nm^{\frac{1}{2}})。
    int n, m;
    int a[N];
    
    int Bn;
    int belong[N];
    
    struct qry {
        int l, r, id;
        bool operator < (const qry &rhs) const {
            if (belong[l] ^ belong[rhs.l]) return l < rhs.l;
            return belong[l] & 1 ? r < rhs.r : r > rhs.r;
        }
    } q[M];
    
    int ans[M];
    
    int main() {
        for (int i = 1; i <= m; i ++)
            std::cin >> q[i].l >> q[i].r, q[i].id = i;
    
        for (int i = 1; i <= n; i ++) belong[i] = (i - 1) / Bn + 1;
    
        std::sort(q + 1, q + 1 + m);
    
        int l = 1, r = 0;
        for (int i = 1; i <= m; i ++) {
            while (r < q[i].r) add(a[++ r]);
            while (l > q[i].l) add(a[-- l]);
            while (r > q[i].r) dec(a[r --]);
            while (l < q[i].l) dec(a[l ++]);
            // ans[q[i].id] = ...
        }
    }

    高维莫队

    • 对于 kk 维莫队,对前 k−1k - 1 维分块,第 i∈[1,k−1]i \in [1, k - 1] 关键字为第 ii 维坐标所在块编号,第 kk 关键字为第 kk 维坐标。
    • 分块大小 O(nm−1k)\mathcal{O}(nm^{-\frac{1}{k}}),时间复杂度 O(nm1−1k)\mathcal{O}(nm^{1 - \frac{1}{k}})。

    带修莫队

    • 普通莫队是不支持修改的。
    • 可以给每个询问附加一个时间戳 tt,来表示回答该次询问时已经经过了多少次修改。转化为三维莫队。
    • 当 n,mn, m 同阶时,分块大小 O(n23)\mathcal{O}(n^{\frac{2}{3}}),时间复杂度 O(n53)\mathcal{O}(n^{\frac{5}{3}})。
    • 当 n,mn, m 不同阶时,分块大小 O(nm−13)\mathcal{O}(nm^{-\frac{1}{3}}),时间复杂度 O(nm23)\mathcal{O}(nm^{\frac{2}{3}})。
    int n, m;
    int a[N];
    
    int Bn;
    int belong[N];
    
    int mc;
    struct cg {
        int x, v;
    } c[M];
    
    int mq;
    struct qry {
        int l, r, t, id;
        bool operator < (const qry &rhs) const {
            if (belong[l] ^ belong[rhs.l]) return l < rhs.l;
            if (belong[r] ^ belong[rhs.r]) return r < rhs.r;
            return t < rhs.t;
        }
    } q[M];
    
    int ans[M];
    
    int main() {
        for (int i = 1; i <= m; i ++) {
            if (opt[0] == 'C') {
                mc ++;
                std::cin >> c[mc].x >> c[mc].v;
            } else {
                mq ++;
                std::cin >> q[mq].l >> q[mq].r, q[mq].t = mc, q[mq].id = mq;
            }
        }
    
        for (int i = 1; i <= n; i ++) belong[i] = (i - 1) / Bn + 1;
    
        std::sort(q + 1, q + 1 + mq);
    
        int l = 1, r = 0, t = 0;
        for (int i = 1; i <= mq; i ++) {
            while (r < q[i].r) add(a[++ r]);
            while (l > q[i].l) add(a[-- l]);
            while (r > q[i].r) dec(a[r --]);
            while (l < q[i].l) dec(a[l ++]);
            while (t < q[i].t) {
                t ++;
                if (q[i].l <= c[t].x && c[t].x <= q[i].r) dec(a[c[t].x]), add(c[t].v);
                std::swap(a[c[t].x], c[t].v);
            }
            while (t > q[i].t) {
                if (q[i].l <= c[t].x && c[t].x <= q[i].r) dec(a[c[t].x]), add(c[t].v);
                std::swap(a[c[t].x], c[t].v);
                t --;
            }
            // ans[q[i].id] = ...
        }
    }

    回滚莫队

    • 用于解决一类插入容易、删除不易的莫队问题。
    • 当操作方便撤销时,可以考虑直接撤销。或是用栈记录操作,沿着栈撤销。
    • 当操作不方便撤销时,可以考虑加入这些数对答案的影响。
    int n, m;
    int a[N];
    
    int Bn;
    int belong[N];
    
    struct qry {
        int l, r, id;
        bool operator < (const qry &rhs) const {
            if (belong[l] ^ belong[rhs.l]) return l < rhs.l;
            return r < rhs.r;
        }
    } q[M];
    
    int ans[M];
    
    void add(int x, bool rem) {
        // ...
    }
    
    int main() {
        for (int i = 1; i <= m; i ++)
            std::cin >> q[i].l >> q[i].r, q[i].id = i;
    
        for (int i = 1; i <= n; i ++) belong[i] = (i - 1) / Bn + 1;
    
        std::sort(q + 1, q + 1 + m);
    
        for (int x = 1, y = 1; x <= m; x = y = y + 1) {
            while (y < m && belong[q[x].l] == belong[q[y + 1].l]) y ++;
    
            int rightpos = belong[q[x].l] * Bn;
    
            // init ...
    
            int l = rightpos + 1, r = rightpos;
            for (int i = x; i <= y; i ++) {
                if (q[i].r <= rightpos) {
                    for (int j = q[i].l; j <= q[i].r; j ++) add(j, 1); 
    
                    // ans[q[i].id] = ...
    
                    // Return to the last state.
                } else {
                    while (r < q[i].r) add(++ r, 0);
    
                    // Record the current state.
    
                    while (l > q[i].l) add(-- l, 1);
    
                    // ans[q[i].id] = ...
    
                    // Return to the last state.
                }
            }
        }
    }

    树上莫队

    欧拉序 2:在 dfs 时,第一次访问到该节点时将该节点加入欧拉序(记作 Inx\mathrm{In}_x),从该节点回溯时将该节点加入欧拉序(记作 Outx\mathrm{Out}_x)。

    • 对于从 xx 到 yy 的路径,不妨设 Inx<Iny\mathrm{In}_x < \mathrm{In}_y
      • 若 LCA(x,y)=x\mathrm{LCA}(x, y) = x,则从 xx 到 yy 的路径上的点为欧拉序 [Inx,Iny][\mathrm{In}_x, \mathrm{In}_y] 中只出现过一次的点。
      • 若 LCA(x,y)≠x\mathrm{LCA}(x, y) \neq x,则从 xx 到 yy 的路径上的点为欧拉序 [Outx,Iny][\mathrm{Out}_x, \mathrm{In}_y] 中只出现过一次的点与 LCA(x,y)\mathrm{LCA}(x, y)。
    int n, m;
    int a[N];
    
    int tot, head[N], ver[N * 2], Next[N * 2];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
    }
    
    int dep[N];
    int anc[logN + 1][N];
    
    int In[N], Out[N];
    int eul_len, eul[N * 2];
    
    int Bn;
    int belong[N * 2];
    
    void dfs(int u, int fu) {
        dep[u] = dep[fu] + 1;
    
        anc[0][u] = fu;
        for (int i = 1; i <= logN; i ++) anc[i][u] = anc[i - 1][anc[i - 1][u]];
    
        eul[++ eul_len] = u, In[u] = eul_len;
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == fu) continue;
    
            dfs(v, u);
        }
    
        eul[++ eul_len] = u, Out[u] = eul_len;
    }
    
    int lca(int x, int y) {
        if (dep[x] > dep[y]) std::swap(x, y);
        for (int i = logN; i >= 0; i --)
            if (dep[x] <= dep[y] - (1 << i)) y = anc[i][y];
        if (x == y) return x;
        for (int i = logN; i >= 0; i --)
            if (anc[i][x] != anc[i][y]) x = anc[i][x], y = anc[i][y];
        return anc[0][x];
    }
    
    struct ask {
        int l, r, z, id;
        bool operator < (const qry &rhs) const {
            if (belong[l] ^ belong[rhs.l]) return l < rhs.l;
            return belong[l] & 1 ? r < rhs.r : r > rhs.r;
        }
    } q[M];
    
    int ans[M]; 
    
    bool state[N];
    
    void attend(int p) {
        state[p] ^= 1;
        state[p] ? add(a[p]) : dec(a[p]);
    }
    
    int main() {
        dfs(1, 0);
    
        for (int i = 1, x, y, z; i <= m; i ++) {
            std::cin >> x >> y, z = lca(x, y);
            if (In[x] > In[y]) std::swap(x, y);
    
            if (z == x)
                q[i].l = In[x], q[i].r = In[y], q[i].z = 0, q[i].id = i;
            else
                q[i].l = Out[x], q[i].r = In[y], q[i].z = z, q[i].id = i;
        }
    
        for (int i = 1; i <= eul_len; i ++) belong[i] = (i - 1) / Bn + 1;
    
        sort(q + 1, q + 1 + m, cmp);
    
        int l = 1, r = 0;
        for (int i = 1; i <= m; i ++) {
            while (r < q[i].r) attend(eul[++ r]);
            while (l > q[i].l) attend(eul[-- l]);
            while (r > q[i].r) attend(eul[r --]);
            while (l < q[i].l) attend(eul[l ++]);
    
            if (q[i].z)
                // Calculate ans[q[i].id] with q[i].z
            else
                // Calculate ans[q[i].id]
        }
    }

    莫队二次离线

    • 待填。

    序列分治

    • 在序列分治的过程中,取分治重心 mid=⌊l+r2⌋\mathrm{mid} = \left\lfloor \frac{l + r}{2} \right\rfloor,尝试分成以下几类讨论(其中 3 是讨论重点):
      1. 分治递归到叶子节点(即 l=rl = r)。
      2. 左右端点均在区间 [l,mid][l, \mathrm{mid}] 或左右端点均在区间 [mid+1,r][\mathrm{mid} + 1, r]。
      3. 左端点在区间 [l,mid][l, \mathrm{mid}],右端点在区间 [mid+1,r][\mathrm{mid} + 1, r]。
    • 序列分治的分治树为猫树。

    最值分治

    • 在最值分治的过程中,取分治重心 pp 为 [l,r][l, r] 中的最值,尝试分成以下几类讨论(其中 3 是讨论重点):
      1. 分治递归到叶子节点(即 l=rl = r)。
      2. 左右端点均在区间 [l,p−1][l, p - 1] 或左右端点均在区间 [p+1,r][p + 1, r]。
      3. 左端点在区间 [l,p][l, p],右端点在区间 [p,r][p, r]。此时的子区间 [l′,r′][l', r'] 中的最值必为 apa_p。通常需要配合启发式合并。
    • 最值分治的分治树为笛卡尔树。

    CDQ 分治

    • 在序列分治的过程中,取分治重心 mid=⌊l+r2⌋\mathrm{mid} = \left\lfloor \frac{l + r}{2} \right\rfloor,尝试分成以下几类讨论(其中 3 是讨论重点):
      1. 分治递归到叶子节点(即 l=rl = r)。
      2. 递归计算区间 [l,mid][l, \mathrm{mid}] 中的答案。
      3. 统计区间 [l,mid][l, \mathrm{mid}] 对区间 [mid+1,r][\mathrm{mid} + 1, r] 的贡献。
      4. 递归计算区间 [mid+1,r][\mathrm{mid} + 1, r] 中的答案。

    整体二分

    • 在整体二分的过程中,取二分中点 mid=⌊l+r2⌋\mathrm{mid} = \left\lfloor \frac{l + r}{2} \right\rfloor,将答案 ≤mid\leq \mathrm{mid} 的询问分到区间 [l,mid][l, \mathrm{mid}] 中递归计算,将答案 >mid> \mathrm{mid} 的询问分到区间 [mid+1,r][\mathrm{mid} + 1, r] 中递归计算。

    二进制分组

    • 枚举每一个二进制位 ii。在此次分组中,若一个关键点的第 ii 位为 11,则将其归入 A 类点;若一个关键点的第 ii 位为 00,则将其归入 B 类点。计算 A 类点与 B 类点之间的信息。
    • 二进制分组一定覆盖了所有的关键点点对,因为对于两个不同的关键点,必有一个二进制位不相同。

    线段树分治

    • 待填。

    线段树优化建图

    • 待填。

    Trick

    区间加、区间查询 转 单点加、区间查询

    • 对于原序列 aa,记其差分序列为 bb。
    ∑i=1rai=∑i=1r∑j=1ibj=∑j=1rbj⋅(r−j+1)=(r+1)∑j=1rbj−∑j=1rj⋅bj\begin{aligned} \sum\limits_{i = 1}^r a_i & = \sum\limits_{i = 1}^r \sum\limits_{j = 1}^i b_j \\ & = \sum\limits_{j = 1}^r b_j \cdot (r - j + 1) \\ & = (r + 1) \sum\limits_{j = 1}^r b_j - \sum\limits_{j = 1}^r j \cdot b_j \end{aligned}

    连续段计数

    无重复元素:即统计 max−min=r−l\mathrm{max} - \mathrm{min} = r - l 的区间个数。

    • 注意到 max−min≥r−l\mathrm{max} - \mathrm{min} \geq r - l,即 max−min+l≥r\mathrm{max} - \mathrm{min} + l\geq r。
    • 从左到右枚举 rr,使用线段树配合两个单调栈,维护每个 ll 对应的 max−min+l\mathrm{max} - \mathrm{min} + l,线段树上需要维护区间中的最小值以及最小值个数。
    • 若线段树 [1,r][1, r] 中的最小值等于 rr,则 rr 对答案有 “ 线段树 [1,r][1, r] 中的最小值个数 “ 的贡献。

    有重复元素:即统计 max−min+cnt=r−l\mathrm{max} - \mathrm{min} + \mathrm{cnt} = r - l 的区间个数,其中 cnt\mathrm{cnt} 表示区间中重复数的个数。

    • 注意到 max−min+cnt≥r−l\mathrm{max} - \mathrm{min} + \mathrm{cnt} \geq r - l,即 max−min+cnt+l≥r\mathrm{max} - \mathrm{min} + \mathrm{cnt} + l\geq r。
    • 从左到右枚举 rr,使用线段树配合两个单调栈以及每个位置上一个相同数的位置,维护每个 ll 对应的 max−min+cnt+l\mathrm{max} - \mathrm{min} + \mathrm{cnt} + l,线段树上需要维护区间中的最小值以及最小值个数。
    • 若线段树 [1,r][1, r] 中的最小值等于 rr,则 rr 对答案有 “ 线段树 [1,r][1, r] 中的最小值个数 “ 的贡献。

    D - 数据结构 树上结构

    最近公共祖先 LCA

    树上倍增

    • O(nlog⁡n)−O(log⁡n)\mathcal{O}(n \log n) - \mathcal{O}(\log n)。

    重链剖分

    • O(n)−O(log⁡n)\mathcal{O}(n) - \mathcal{O(\log n)}。

    欧拉序 & ST 表

    • O(nlog⁡n)−O(1)\mathcal{O}(n \log n) - \mathcal{O}(1)。

    欧拉序 1:在 dfs 时,第一次访问到该节点时将该节点加入欧拉序(记作 Firx\mathrm{Fir}_x),回溯到该节点时将该节点加入欧拉序。

    • 不妨设 Firx<Firy\mathrm{Fir}_x < \mathrm{Fir}_y,则 LCA(u,v)\mathrm{LCA}(u, v) 为欧拉序 [Firx,Firy][\mathrm{Fir}_x, \mathrm{Fir}_y] 中深度最小的节点。用 ST 表维护。
    int tot, head[N], ver[N * 2], Next[N * 2];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
    }
    
    int dep[N];
    
    int Fir[N];
    int eul_len, eul[N * 2];
    
    void dfs(int u, int fu) {
        dep[u] = dep[fu] + 1;
    
        eul[++ eul_len] = u, Fir[u] = eul_len;
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == fu) continue;
    
            dfs(v, u), eul[++ eul_len] = u;
        }
    }
    
    namespace eul_ST {
        const int SIZE = N * 2;
    
        int logx[SIZE];
        int f[logSIZE + 1][SIZE];
    
        int great(int x, int y) {
            return dep[x] < dep[y] ? x : y;
        }
    
        void init() {
            logx[0] = -1;
            for (int i = 1; i <= eul_len; i ++) logx[i] = logx[i >> 1] + 1;
    
            for (int i = 1; i <= eul_len; i ++) f[0][i] = eul[i];
            for (int j = 1; j <= logSZ; j ++)
                for (int i = 1; i <= eul_len - (1 << j) + 1; i ++)
                    f[j][i] = great(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
        }
    
        int query(int l, int r) {
            int k = logx[r - l + 1];
            return great(f[k][l], f[k][r - (1 << k) + 1]);
        }
    }
    
    int lca(int x, int y) {
        int l = Fir[x], r = Fir[y]; if (l > r) std::swap(l, r);
        return eul_ST::query(l, r);
    }

    树的重心

    • 一个点是树的重心,当且仅当它的最大子树大小不超过整棵树的一半。
    • 树中所有点到重心的距离和是最小的。
    • 树至多有两个重心。若树有两个重心,则这两个重心相邻,此时树有偶数个节点,可以被划分成大小相等的两支。
    • 在两棵树之间加一条边,新树的重心在原来两棵树的重心的简单路径上。
    • 在一颗树上添加或删除一个叶子,重心至多只移动一条边的距离。

    树的直径

    • 在边权非负的前提下,合并两个点集时,新点集的直径端点,必定来自两个点集四个端点中的某两个,共六种情况。
    • 在边权非负的前提下,钦定点对 (u,v)(u, v) 作为直径端点的充要条件是,不存在其他点 ww 使得 dist(u,w)>dist(u,v)\mathrm{dist}(u, w) > \mathrm{dist}(u, v) 或 dist(v,w)>dist(u,v)\mathrm{dist}(v, w) > \mathrm{dist}(u, v)。

    树的同构

    T1,T2T_1, T_2 同构:若 T1,T2T_1, T_2 为同构树,当且仅当存在一个 1∼n1 \sim n 的排列 ff,使得 (i,j)∈E⇔(fi,fj)∈E(i, j) \in E \Leftrightarrow (f_i, f_j) \in E。

    有根树自同构树计数:对于每个点的每个儿子的子树,按照同构(指去掉标号、儿子间不区分顺序后俩子树相同)划分出等价类,按照每种等价类的大小的阶乘乘入答案。

    无根数自同构数计数:需要找到一个代表节点,当重心唯一时,取重心为根;当重心不唯一时,在重心之间加一点,取该点为根。转化为有根树计算。

    树哈希

    有根树树哈希:设 fuf_u 表示以 uu 为根的子树的哈希值,则 fuf_u 即为 uu 的所有儿子 vv 为根的子树的哈希值构成的多重集的哈希值。考虑使用集合哈希。

    fu=(c+∑v∈son(u)shift(fv)) mod mf_u = \left(c + \sum\limits_{v \in \mathrm{son}(u)} \mathrm{shift}(f_v)\right) \bmod m
    typedef unsigned long long u64;
    
    u64 mask = std::mt19937_64((unsigned)time(0))();
    u64 shift(u64 x) {
        x ^= mask;
        x ^= x << 13;
        x ^= x >> 7;
        x ^= x << 17;
        x ^= mask;
        return x;
    }
    
    u64 f[N];
    
    void dfs_hash(int u, int fu) {
        f[u] = 1;
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == fu) continue;
            dfs_hash(v, u);
            f[u] += shift(f[v]);
        }
    }

    无根树树哈希:需要找到一个代表节点,当重心唯一时,取重心为根;当重心不唯一时,在重心之间加一点,取该点为根。转化为有根树的情况。

    重链剖分

    • 重链优先 dfs 序列:
      • 任意子树在 dfs 序上,都对应一个连续区间。
      • 任意重链在 dfs 序上,都对应一个连续区间。
    • 向根的方向经过一条轻边后,所在子树大小至少乘 22。
    • 任意一点到根路径上的所有边,可分成 O(log⁡n)\mathcal{O}(\log n) 个重路径的不交并。
    • 任意两点之间路径上的所有边,可分成 O(log⁡n)\mathcal{O}(\log n) 个重路径的不交并。
    int tot, head[N], ver[N * 2], Next[N * 2];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
    }
    
    int dep[N], sze[N], Fa[N], son[N];
    
    void dfs1(int u) {
        dep[u] = dep[Fa[u]] + 1;
        sze[u] = 1;
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == Fa[u]) continue;
    
            Fa[v] = u;
            dfs1(v);
    
            sze[u] += sze[v];
            if (sze[v] > sze[son[u]]) son[u] = v;
        }
    }
    
    int dfsClock, dfn[N], idx[N];
    int chain_top[N];
    
    void dfs2(int u, int P) {
        dfsClock ++;
        dfn[u] = dfsClock, idx[dfsClock] = u;
    
        chain_top[u] = P;
    
        if (son[u]) dfs2(son[u], P);
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == Fa[u] || v == son[u]) continue;
    
            dfs2(v, v);
        }
    }
    
    void chain_operate(int x, int y) {
        while (chain_top[x] ^ chain_top[y]) {
            if (dep[chain_top[x]] > dep[chain_top[y]]) std::swap(x, y);
            // Operate on the [dfn[chain_top[y]], dfn[y]].
            y = Fa[chain_top[y]];
        }
    
        if (dep[x] > dep[y]) std::swap(x, y);
        // Operate on the [dfn[x], dfn[y]].
    }

    长链剖分

    • 所有长链的长度和为 nn。
    • 任意一点到根路径上的所有边,可分成 O(n)\mathcal{O}(\sqrt{n}) 个长路径的不交并。
    int tot, head[N], ver[N * 2], Next[N * 2];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
    }
    
    int dep[N], max_dep[N], Fa[N], son[N];
    
    void dfs1(int u) {
        max_dep[u] = dep[u] = dep[Fa[u]] + 1;
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == Fa[u]) continue;
    
            Fa[v] = u; 
            dfs1(v);
    
            if (max_dep[v] > max_dep[u]) max_dep[u] = max_dep[v], son[u] = v; 
        }
    }
    
    int chain_top[N];
    
    void dfs2(int u, int P) {
        chain_top[u] = P;
    
        if (son[u]) dfs2(son[u], P);
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == Fa[u] || v == son[u]) continue;
    
            dfs2(v, v);
        }
    }

    长链剖分优化 dp:长链剖分可以优化附带深度维的 dp。

    • 遍历每一个节点,统计每一个节点子树内的信息,设当前遍历到了节点 uu:
      • 递归计算 uu 的长子树的信息,将长子树的 dp 信息继承给 uu。
      • 递归计算 uu 的所有短子树的信息,将短子树的 dp 信息合并计入 uu。
    • 具体实现中,可以开一个内存池 pool,为一条长链统筹分配内存,通常链上不同的节点有不同的首指针,便于继承信息。因此,在完整地做完一遍 dp 后,只有长链链首的节点保留了正确的 dp 值。

    O(nlog⁡n)−O(1)\mathcal{O}(n \log n) - \mathcal{O}(1) 树上 kk 级祖先:

    • 任意一点 xx 的 kk 级祖先,其所在的长链长度 ≥k\geq k。
    • 对树进行长链剖分,预处理:
      • 每个点的树上 2k2^k 级祖先。
      • 每条长链(记该长链长度为 len\mathrm{len})从长链顶端向上的 len\mathrm{len} 个祖先和向下的 len\mathrm{len} 个儿子。
      • 每个二进制数的最高位。
    • 每次询问 xx 的 kk 级祖先:
      • 记 hh 为 kk 的最高二进制位。利用倍增数组先让 xx 跳到 xx 的 2h2^h 级祖先。
      • 记剩余级数为 k′=k−2hk' = k - 2^h。由于当前 xx 所在长链长度 len≥2h≥k−2h=k′\mathrm{len} \geq 2^h \geq k - 2^h = k',可以先让 xx 跳到 xx 所在长链顶端,若剩余级数为正,则利用预处理的数组向上跳求出答案;若剩余级数为负,则利用预处理的数组向下跳求出答案。
    int tot, head[N], ver[N * 2], Next[N * 2];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
    }
    
    int dep[N], max_dep[N], Fa[N], son[N];
    int anc[logN + 1][N]; 
    
    void dfs1(int u) {
        max_dep[u] = dep[u] = dep[Fa[u]] + 1;
    
        anc[0][u] = Fa[u];
        for (int i = 1; i <= logN; i ++) anc[i][u] = anc[i - 1][anc[i - 1][u]];
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == Fa[u]) continue;
    
            Fa[v] = u; 
            dfs1(v);
    
            if (max_dep[v] > max_dep[u]) max_dep[u] = max_dep[v], son[u] = v; 
        }
    }
    
    int chain_top[N];
    std::vector<int> up[N], dn[N];
    
    void dfs2(int u, int P) {
        chain_top[u] = P;
    
        if (u == P) {
            int len = max_dep[u] - dep[u] + 1;
            for (int step = len, x = u; step; step --, x = Fa[x]) up[u].push_back(x);
            for (int step = len, x = u; step; step --, x = son[x]) dn[u].push_back(x);
        }
    
        if (son[u]) dfs2(son[u], P);
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == Fa[u] || v == son[u]) continue;
    
            dfs2(v, v);
        }
    }
    
    int logx[N];
    
    int find(int x, int k) {
        if (!k) return x;
        int h = logx[k];
        k -= (1 << h), x = f[h][x];
        k -= dep[x] - dep[chain_top[x]], x = chain_top[x];
        return k >= 0 ? up[x][k] : dn[x][-k]; 
    }
    
    int main() {
        logx[0] = -1;
        for (int i = 1; i <= n; i ++) logx[i] = logx[i >> 1] + 1;
    
        // ...
    }

    LCT

    • LCT 的辅助树由 splay 森林组成,每一棵 splay 都维护了一条偏爱链,splay 的中序遍历对应着偏爱链从链顶至链底。
    • LCT 的每一棵 splay 的顶端节点,其父不认子。
    • LCT 的操作注意事项:
      • find_root(x):在找到根之后,需要将根 splay 上去,否则复杂度可能会退化。
      • link(x, y):在连边之前,需要判断 x,yx, y 所在连通块的根是否不同。
      • cut(x, y):在执行完 make_root(x), access(y), splay(y) 之后,需要判断 yy 的左子树是否有且仅有 xx。
    • LCT 经过 access 后,跨越非偏爱边的数量是 O(log⁡n)\mathcal{O}(\log n) 的。
    • LCT 的 access 操作,可以实现从某节点到根路径上的标记覆盖,可以实现从某节点到根路径上标记的批量处理(因为每条实链的标记都是相同的)。由于根是不变的,就不必写翻转标记了。
    namespace LCT {
        struct node {
            int son[2], Fa;
            int val;
            int sze;
            bool rev;
    
            #define lc son[0]
            #define rc son[1]
    
            void init(int x) {
                lc = rc = 0, Fa = 0;
                val = x;
                sze = 1;
                rev = 0;
            }
    
            void mk_rev() {
                std::swap(lc, rc);
                rev ^= 1;
            }
        } t[N];
    
        void upd(int p) {
            t[p].sze = t[t[p].lc].sze + t[t[p].rc].sze + 1;
        }
    
        void spread(int p) {
            if (t[p].rev) {
                if (t[p].lc) t[t[p].lc].mk_rev();
                if (t[p].rc) t[t[p].rc].mk_rev();
                t[p].rev = 0;
            }
        }
    
        int dir(int x) {
            return t[t[x].Fa].rc == x;
        }
    
        int is_top(int x) {
            return t[t[x].Fa].lc != x && t[t[x].Fa].rc != x;
        }
    
        void rotate(int x) {
            int y = t[x].Fa, z = t[y].Fa, k = dir(x);
            t[x].Fa = z; if (!is_top(y)) t[z].son[t[z].rc == y] = x;
            t[y].son[k] = t[x].son[k ^ 1], t[t[x].son[k ^ 1]].Fa = y;
            t[x].son[k ^ 1] = y, t[y].Fa = x;
            upd(y), upd(x);
        }
    
        void splay(int x) {
            static int top, stk[N], p;
    
            stk[top = 1] = x;
            for (p = x; !is_top(p); p = t[p].Fa) stk[++ top] = t[p].Fa;
            while (top) spread(stk[top --]);
    
            while (p = t[x].Fa, !is_top(x)) {
                if (!is_top(p)) rotate(dir(x) == dir(p) ? p : x);
                rotate(x);
            }
        }
    
        void access(int x) {
            for (int y = 0; x; y = x, x = t[x].Fa) {
                splay(x);
                t[x].rc = y;
                upd(x); 
            }
        }
    
        int find_root(int x) {
            access(x), splay(x);
            while (spread(x), t[x].lc) x = t[x].lc;
            return splay(x), x;
        }
    
        void make_root(int x) {
            access(x), splay(x), t[x].mk_rev();
        }
    
        void link(int x, int y) {
            if (find_root(x) == find_root(y)) return;
            make_root(x), t[x].Fa = y;
        }
    
        void cut(int x, int y) {
            make_root(x), access(y), splay(y);
            if (t[y].lc != x || t[x].rc) return;
            t[y].lc = t[x].Fa = 0, upd(y);
        }
    }

    LCT 维护子树信息:维护虚子树的信息总和(需要满足可减性),只有 access 与 link 操作需要改变。

    namespace LCT {
        struct node {
            int son[2], Fa;
            int sze;
            int vir;
            bool rev;
    
            #define lc son[0]
            #define rc son[1]
    
            void init() {
                lc = rc = 0, Fa = 0;
                sze = 1;
                vir = 0;
                rev = 0;
            }
    
            void mk_rev() {
                std::swap(lc, rc);
                rev ^= 1;
            }
        } t[N];
    
        void upd(int p) {
            t[p].sze = t[t[p].lc].sze + t[t[p].rc].sze + 1 + t[p].vir;
        }
    
        void spread(int p) {
            if (t[p].rev) {
                if (t[p].lc) t[t[p].lc].mk_rev();
                if (t[p].rc) t[t[p].rc].mk_rev();
                t[p].rev = 0;
            }
        }
    
        int dir(int x) {
            return t[t[x].Fa].rc == x;
        }
    
        bool is_top(int x) {
            return t[t[x].Fa].lc != x && t[t[x].Fa].rc != x;
        }
    
        void rotate(int x) {
            int y = t[x].Fa, z = t[y].Fa, k = dir(x);
            t[x].Fa = z; if (!is_top(y)) t[z].son[t[z].rc == y] = x;
            t[y].son[k] = t[x].son[k ^ 1], t[t[x].son[k ^ 1]].Fa = y;
            t[x].son[k ^ 1] = y, t[y].Fa = x;
            upd(y), upd(x);
        }
    
        void splay(int x) {
            static int top, stk[N], p;
    
            stk[top = 1] = x;
            for (p = x; !is_top(p); p = t[p].Fa) stk[++ top] = t[p].Fa;
            while (top) spread(stk[top --]);
    
            while (p = t[x].Fa, !is_top(x)) {
                if (!is_top(p)) rotate(dir(x) == dir(p) ? p : x);
                rotate(x);
            }
        }
    
        void access(int x) {
            for (int y = 0; x; y = x, x = t[x].Fa) {
                splay(x);
                t[x].vir += t[t[x].rc].sze - t[y].sze;
                t[x].rc = y;
                upd(x);
            }
        }
    
        void make_root(int x) {
            access(x), splay(x), t[x].mk_rev();
        }
    
        void link(int x, int y) {
            if (find_root(x) == find_root(y)) return;
            make_root(x), make_root(y);
            t[x].Fa = y, t[y].vir += t[x].sze, t[y].sze += t[x].sze;
        }
    
        void cut(int x, int y) {
            make_root(x), access(y), splay(y);
            if (t[y].lc != x || t[x].rc) return;
            t[y].lc = t[x].Fa = 0, upd(y);
        }
    }

    LCT 维护生成树:

    • 对于带权边 (u,v,w)(u, v, w),新建权值为 ww 的点 pp,连接边 (u,p)(u, p) 与 (p,v)(p, v),转化成点带权的树。
    • 加入带权边 (u,v,w)(u, v, w) 时(以最小生成树为例),记生成树 u→vu \to v 的路径上的最大边为 w′w'。若 w<w′w < w',则使用新边替换最大边;否则无法替换。使用 LCT 实现 link 与 cut。
    namespace LCT {
        const int pond = N + M;
    
        int nClock;
        struct node {
            int son[2], Fa;
            int val;
            int max_id;
            bool rev;
    
            #define lc son[0]
            #define rc son[1]
    
            void init(int x, int p) {
                lc = rc = 0, Fa = 0;
                val = x;
                max_id = p;
                rev = 0;
            }
    
            void mk_rev() {
                std::swap(lc, rc);
                rev ^= 1;
            }
        } t[pond];
    
        void upd(int p) {
            t[p].max_id = p;
            if (t[t[t[p].lc].max_id].val > t[t[p].max_id].val)
                t[p].max_id = t[t[p].lc].max_id;
            if (t[t[t[p].rc].max_id].val > t[t[p].max_id].val)
                t[p].max_id = t[t[p].rc].max_id;
        }
    
        void spread(int p) {
            if (t[p].rev) {
                if (t[p].lc) t[t[p].lc].mk_rev();
                if (t[p].rc) t[t[p].rc].mk_rev();
                t[p].rev = 0;
            }
        }
    
        int dir(int x) {
            return t[t[x].Fa].rc == x;
        }
    
        bool is_top(int x) {
            return t[t[x].Fa].lc != x && t[t[x].Fa].rc != x;
        }
    
        void rotate(int x) {
            int y = t[x].Fa, z = t[y].Fa, k = dir(x);
            t[x].Fa = z; if (!is_top(y)) t[z].son[t[z].rc == y] = x;
            t[y].son[k] = t[x].son[k ^ 1], t[t[x].son[k ^ 1]].Fa = y;
            t[x].son[k ^ 1] = y, t[y].Fa = x;
            upd(y), upd(x);
        }
    
        void splay(int x) {
            static int top, stk[pond], p;
    
            stk[top = 1] = x;
            for (p = x; !is_top(p); p = t[p].Fa) stk[++ top] = t[p].Fa;
            while (top) spread(stk[top --]);
    
            while (p = t[x].Fa, !is_top(x)) {
                if (!is_top(p)) rotate(dir(x) == dir(p) ? p : x);
                rotate(x);
            }
        }
    
        void access(int x) {
            for (int y = 0; x; y = x, x = t[x].Fa) {
                splay(x);
                t[x].rc = y;
                upd(x);
            }
        }
    
        int find_root(int x) {
            access(x), splay(x);
            while (spread(x), t[x].lc) x = t[x].lc;
            return splay(x), x;
        }
    
        void make_root(int x) {
            access(x), splay(x), t[x].mk_rev();
        }
    
        void link(int x, int y) {
            make_root(x), t[x].Fa = y;
        }
    
        void extend(int x, int y, int z) {
            t[++ nClock].init(z, nClock);
    
            if (find_root(x) != find_root(y)) {
                link(x, nClock), link(y, nClock);
            } else {
                make_root(x), access(y), splay(y);
    
                if (t[t[y].max_id].val <= z) return;
    
                int p = t[y].max_id;
                splay(p), t[t[p].lc].Fa = t[t[p].rc].Fa = 0;
    
                link(x, nClock), link(y, nClock);
            }
        }
    }
    
    int main() {
        for (int i = 1; i <= n; i ++) LCT::t[i].init(-inf, i);
        LCT::nClock = n;
    
        // ...
    }

    LCT 维护双连通分量:待填。

    LCT 维护黑白转色树(qtree6):定根,令每个黑点向黑点父亲连边,此时真正的连通块就是 splay 里的连通块删掉根。

    namespace LCT {
        int up[N];
        struct node {
            int son[2], Fa;
            int sze, vir;
    
            #define lc son[0]
            #define rc son[1]
    
            void init() {
                lc = rc = 0, Fa = 0;
                sze = 1, vir = 0;
            }
        } t[N];
    
        void upd(int p) {
            t[p].sze = t[t[p].lc].sze + t[t[p].rc].sze + 1 + t[p].vir;
        }
    
        int dir(int x) {
            return t[t[x].Fa].rc == x;
        }
    
        bool is_top(int x) {
            return t[t[x].Fa].lc != x && t[t[x].Fa].rc != x;
        }
    
        void rotate(int x) {
            int y = t[x].Fa, z = t[y].Fa, k = dir(x);
            t[x].Fa = z; if (!is_top(y)) t[z].son[t[z].rc == y] = x;
            t[y].son[k] = t[x].son[k ^ 1], t[t[x].son[k ^ 1]].Fa = y;
            t[x].son[k ^ 1] = y, t[y].Fa = x;
            upd(y), upd(x);
        }
    
        void splay(int x) {
            static int p;
            while (p = t[x].Fa, !is_top(x)) {
                if (!is_top(p)) rotate(dir(x) == dir(p) ? p : x);
                rotate(x);
            }
        }
    
        void access(int x) {
            for (int y = 0; x; y = x, x = t[x].Fa) {
                splay(x);
                t[x].vir += t[t[x].rc].sze - t[y].sze;
                t[x].rc = y;
                upd(x);
            }
        }
    
        int find_root(int x) {
            access(x), splay(x);
            while (t[x].lc) x = t[x].lc;
            return splay(x), x;
        }
    
        int ask(int x) { return t[t[find_root(x)].rc].sze; }
    
        void link(int x) {
            int y = up[x];
            splay(x);
            t[x].Fa = y, access(y), splay(y);
            t[y].vir += t[x].sze, t[y].sze += t[x].sze;
        }
    
        void cut(int x) {
            access(x), splay(x);
            t[x].lc = t[t[x].lc].Fa = 0, upd(x);,
        }
    }

    点分治、点分树

    参考:https://liu-cheng-ao.blog.uoj.ac/blog/2969

    • 点分治本质上是序列分治的树上衍生。
    • 在点分治过程中,将本层中与上一层重心相邻的点记作本层的根。若将以 “ 上一层的根 “ 作为根时的子树大小作为本层总节点数,虽然在本层的根在上一层的根与上一层的重心简单路径上时,本层总结点数会计算错误,但不影响复杂度。
    int tot, head[N], ver[N * 2], Next[N * 2];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
    }
    
    bool ban[N];
    
    int sz[N], mp[N];
    int A_sz, A_rt;
    
    void Get_rt(int u, int fu) {
        sz[u] = 1, mp[u] = 0;
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == fu || ban[v]) continue;
    
            Get_rt(v, u);
    
            sz[u] += sz[v];
            if (sz[v] > mp[u]) mp[u] = sz[v];
        }
    
        if (A_sz - sz[u] > mp[u]) mp[u] = A_sz - sz[u];
        if (A_rt == 0 || mp[u] < mp[A_rt]) A_rt = u;
    }
    
    void solve(int u) {
        ban[u] = 1;
    
        // Calculate the data of path through point u.
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (ban[v]) continue;
    
            A_sz = sz[v], A_rt = 0;
            Get_rt(v, u), solve(A_rt);
        }
    }
    
    int main() {
        A_sz = n, A_rt = 0;
        Get_rt(1, 0), solve(A_rt);
    }
    • 点分树本质上是点分治的分治树。
    • 点分树中任意两点 u,vu, v 的 LCA(u,v)\mathrm{LCA}(u, v) 一定在原树中 u,vu, v 的简单路径上。
    int tot, head[N], ver[N * 2], Next[N * 2];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
    }
    
    namespace PDT {
        int rt;
    
        int Fa[N];
        std::vector<int> son[N];
    
        void add_edge(int u, int v) {
            son[u].push_back(v), Fa[v] = u;
        }
    }
    
    bool ban[N];
    
    int sz[N], mp[N];
    int A_sz, A_rt;
    
    void Get_rt(int u, int fu) {
        sz[u] = 1, mp[u] = 0;
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == fu || ban[v]) continue;
    
            Get_rt(v, u);
    
            sz[u] += sz[v];
            if (sz[v] > mp[u]) mp[u] = sz[v];
        }
    
        if (A_sz - sz[u] > mp[u]) mp[u] = A_sz - sz[u];
        if (A_rt == 0 || mp[u] < mp[A_rt]) A_rt = u;
    }
    
    void solve(int u) {
        ban[u] = 1;
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (ban[v]) continue;
    
            A_sz = sz[v], A_rt = 0;
            Get_rt(v, u), PDT::add_edge(u, A_rt), solve(A_rt);
        }
    }
    
    int main() {
        A_sz = n, A_rt = 0;
        Get_rt(1, 0), PDT::rt = A_rt, solve(A_rt);
    }

    虚树

    • 对于关键点点集 SS,在包含关键点点集 SS 的极小联通子图中,分叉节点(儿子数 ≥2\geq 2 的节点)的数量不超过 ∣S∣−1|S| - 1。
    • 对于关键点点集 SS,虚树大小 ≤2∣S∣−1\leq 2|S| - 1。
    • 对于关键点点集 SS,记 uiu_i 为点集 SS 中的点按 dfs 序排序后的结果,则
    {LCA(ui,uj)∣1≤i<j≤∣S∣}={LCA(ui,ui+1)∣1≤i<∣S∣}\{\mathrm{LCA}(u_i, u_j) \mid 1 \leq i < j \leq |S|\} = \{ \mathrm{LCA}(u_i, u_{i + 1}) \mid 1 \leq i < |S| \}
    int tot, head[N], ver[N * 2], Next[N * 2];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
    }
    
    int dfsClock, dfn[N];
    
    int dep[N];
    int anc[logN + 1][N];
    
    void dfs(int u, int fu) {
        dfn[u] = ++ dfsClock;
    
        dep[u] = dep[fu] + 1;
    
        anc[0][u] = fu;
        for (int i = 1; i <= logN; i ++) anc[i][u] = anc[i - 1][anc[i - 1][u]];
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == fu) continue;
    
            dfs(v, u);
        }
    }
    
    int lca(int x, int y) {
        if (dep[x] > dep[y]) std::swap(x, y);
        for (int i = logN; i >= 0; i --)
            if (dep[x] <= dep[y] - (1 << i)) y = anc[i][y];
        if (x == y) return x;
        for (int i = logN; i >= 0; i --)
            if (anc[i][x] != anc[i][y]) x = anc[i][x], y = anc[i][y];
        return anc[0][x];
    }
    
    int crulen, cru[N];
    
    bool cmp(int x, int y) { return dfn[x] < dfn[y]; }
    
    namespace VT {
        int tim, tim_mark[N];
    
        int rt;
    
        int tot, head[N], ver[N], Next[N];
        void add_edge(int u, int v) {
            ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
        }
    
        void init(int u) { head[u] = 0; }
    
        void build() {
            static int top, stk[N];
    
            tot = 0;
    
            tim ++;
            for (int i = 1; i <= crulen; i ++) tim_mark[cru[i]] = tim;
    
            std::sort(cru + 1, cru + 1 + crulen, cmp);
    
            init(cru[1]), stk[top = 1] = cru[1];
            for (int i = 2; i <= crulen; i ++) {
                int x = cru[i], z = lca(stk[top], x);
    
                while (top > 1 && dep[z] <= dep[stk[top - 1]])
                    add_edge(stk[top - 1], stk[top]), top --;
    
                if (stk[top] != z)
                    init(z), add_edge(z, stk[top]), stk[top] = z;
    
                init(x), stk[++ top] = x;
            }
    
            while (top > 1)
                add_edge(stk[top - 1], stk[top]), top --;
    
            rt = stk[1];
        }
    }
    int tot, head[N], ver[N * 2], Next[N * 2];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
    }
    
    int dfsClock, dfn[N];
    
    int dep[N], sze[N];
    int anc[logN + 1][N];
    
    void dfs(int u, int fu) {
        dfn[u] = ++ dfsClock;
        sze[u] = 1; 
    
        dep[u] = dep[fu] + 1;
    
        anc[0][u] = fu;
        for (int i = 1; i <= logN; i ++) anc[i][u] = anc[i - 1][anc[i - 1][u]];
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == fu) continue;
    
            dfs(v, u);
            sze[u] += sze[v];
        }
    }
    
    int lca(int x, int y) {
        if (dep[x] > dep[y]) std::swap(x, y);
        for (int i = logN; i >= 0; i --)
            if (dep[x] <= dep[y] - (1 << i)) y = anc[i][y];
        if (x == y) return x;
        for (int i = logN; i >= 0; i --)
            if (anc[i][x] != anc[i][y]) x = anc[i][x], y = anc[i][y];
        return anc[0][x];
    }
    
    bool contain(int x, int y) {
        return dfn[x] <= dfn[y] && dfn[y] <= dfn[x] + sze[x] - 1;
    }
    
    int crulen, cru[N * 2];
    
    bool cmp(int x, int y) { return dfn[x] < dfn[y]; }
    
    namespace VT {
        int tim, tim_mark[N];
    
        int Fa[N];
    
        void build() {
            static int top, stk[N];
    
            tim ++;
            for (int i = 1; i <= crulen; i ++) tim_mark[cru[i]] = tim;
    
            std::sort(cru + 1, cru + 1 + crulen, cmp);
            for (int i = 1, o = crulen; i < o; i ++) cru[++ crulen] = lca(cru[i], cru[i + 1]);
            std::sort(cru + 1, cru + 1 + crulen, cmp);
            crulen = std::unique(cru + 1, cru + 1 + crulen) - cru - 1;
    
            top = 0;
            for (int i = 1; i <= crulen; i ++) {
                int x = cru[i];
    
                while (top && !contain(stk[top], x)) top --;
                Fa[x] = top ? stk[top] : 0;
                stk[++ top] = x;
            }
        }
    }

    DSU on tree

    • 遍历每一个节点,统计每一个节点子树内的信息,设当前遍历到了节点 uu:
      • 递归计算 uu 的所有轻子树的信息,回溯时需要撤销贡献。
      • 递归计算 uu 的重子树的信息,回溯时不需要撤销贡献。
      • 遍历 uu 的所有轻子树,统计所有轻子树的贡献。
    • 一个节点在重子树内被统计 11 次,在轻子树内被统计 O(log⁡n)\mathcal{O}(\log n) 次(取决于该点到根有多少条轻边)。
    int tot, head[N], ver[N * 2], Next[N * 2];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
    } 
    
    int dfsClock, dfn[N], idx[N];
    
    int sze[N], son[N];
    
    void dfs(int u, int fu) {
        dfsClock ++;
        dfn[u] = dfsClock, idx[dfsClock] = u;
    
        sze[u] = 1;
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == fu) continue;
    
            dfs(v, u);
    
            sze[u] += sze[v];
            if (sze[v] > sze[son[u]]) son[u] = v;
        }
    }
    
    void solve(int u, int fu, bool rem) {
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == fu || v == son[u]) continue;
    
            solve(v, u, 0);
        }
    
        if (son[u]) solve(son[u], u, 1);
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (v == fu || v == son[u]) continue;
    
            int nl = dfn[v], nr = dfn[v] + sze[v] - 1;
            for (int ni = nl; ni <= nr; ni ++) {
                int x = idx[ni];
                add(x);
            }
        }
    
        add(u);
    
        // ans[u] = ...
    
        if (!rem) {
            int nl = dfn[u], nr = dfn[u] + sze[u] - 1;
            for (int ni = nl; ni <= nr; ni ++) {
                int x = idx[ni];
                dec(x);
            }
        }
    }

    Trick

    树上倍增

    • 现要求 x→yx \to y 的信息和,若该信息满足 “ 可重复贡献性 “,则可以将 x→yx \to y 拆成 x→LCA(x,y)x \to \mathrm{LCA}(x, y) 与 y→LCA(x,y)y \to \mathrm{LCA}(x, y) 两段直链,将每一段直链分别拆成自链底向上、自链顶向下的长度为 22 的极大整数次幂的链,用三次合并计算四个树上倍增数组的信息和即可。

    树上差分

    • 对于大小为 mm 的关键点点集 SS,现在要求包含关键点点集 SS 的极小联通子图的边权和,记 uiu_i 为点集 SS 中的点按 dfs 序排序后的结果,则答案为
    12∑i=1mdist(ui,u(i mod m)+1)\frac{1}{2}\sum\limits_{i = 1}^{m} \mathrm{dist}(u_i, u_{(i \bmod m) + 1})
    • 对于大小为 mm 的关键点点集 SS,现在要给包含关键点点集 SS 的极小联通子图的所有点加上 dd,考虑树上差分后做一遍子树和,记 uiu_i 为点集 SS 中的点按 dfs 序排序后的结果,则

      • 对于 1≤i≤m1 \leq i \leq m,令 uiu_i 的差分数组加上 dd。
      • 对于 1≤i<m1 \leq i < m,令 LCA(ui,ui+1)\mathrm{LCA}(u_i, u_{i + 1}) 的差分数组减去 dd。特别地,令 faLCA(u1,um)\mathrm{fa}_{\mathrm{LCA}(u_1, u_m)} 的差分数组减去 dd。
    • 对于大小为 mm 的关键点点集 SS,现在要给包含关键点点集 SS 的极小联通子图的所有边加上 dd,考虑树上差分后做一遍子树和,记 uiu_i 为点集 SS 中的点按 dfs 序排序后的结果,则

      • 对于 1≤i≤m1 \leq i \leq m,令 uiu_i 的差分数组加上 dd。
      • 对于 1≤i≤m1 \leq i \leq m,令 LCA(ui,u(i mod m)+1)\mathrm{LCA}(u_i, u_{(i \bmod m) + 1}) 的差分数组减去 dd。

    路径加、子树查询 转 单点加、区间查询

    • 对于一个路径加 (path(x,y),+d)(\mathrm{path}(x, y), +d),记 z=LCA(x,y)z = \mathrm{LCA}(x, y),将其拆成四个到根节点的路径加
    (path(1,x),+d)(path(1,y),+d)(path(1,z),−d)(path(1,faz),−d)(\mathrm{path}(1, x), +d) \\ (\mathrm{path}(1, y), +d) \\ (\mathrm{path}(1, z), -d) \\ (\mathrm{path}(1, \mathrm{fa}_{z}), -d)
    • 一个到根节点的路径加 (path(1,x),+d)(\mathrm{path}(1, x), +d),会对 xx 的祖先节点 uu 产生 d⋅depx−d⋅(depu−1)d \cdot \mathrm{dep}_x - d \cdot (\mathrm{dep}_{u} - 1) 的贡献。

    换根

    • 钦定以 11 为根,考虑换根对信息的影响。
    • 设当前的根为 R\mathcal{R}:
      • 若 xx 为 R\mathcal{R},则以 R\mathcal{R} 为根时 xx 的子树,为整棵树。
      • 若 xx 为 R\mathcal{R} 的祖先,则以 R\mathcal{R} 为根时 xx 的子树,为整棵树刨去以 11 为根时 ss 的子树,其中 ss 为 xx 向 R\mathcal{R} 方向上的儿子。
      • 若是其他情况,则以 R\mathcal{R} 为根时 xx 的子树,为以 11 为根时 xx 的子树。
    • 设当前的根为 R\mathcal{R},则以 R\mathcal{R} 为根时的 LCA(x,y)\mathrm{LCA}(x, y),为以 11 为根时 LCA(x,y),LCA(x,R),LCA(y,R)\mathrm{LCA}(x, y), \mathrm{LCA}(x, \mathcal{R}), \mathrm{LCA}(y, \mathcal{R}) 中深度最大者。

    森林 / 沙漠 连通块计数

    • 森林:连通块个数 == 点数 −- 边数。
    • 沙漠:连通块个数 == 点数 −- 边数 ++ 环数。