剑锋所指,心之所向。

一些简单的树链剖分题目做题记录。

树链剖分

概述

把树上的一些不连续的节点,通过 dfs 序剖成若干条 dfs 序相邻的链,利用一些数据结构进行维护。

两种剖分方式:第一种重剖,将每个点与其 sz 大小最大的儿子相邻。第二种长剖,将每个点与其到叶子节点最远的点相邻。

例题

各种简单的裸题

过于简单,不放代码了。

【ZJOI 2008】树的统计Count

单点修改区间最值区间求和。

【BZOJ 3306】树

甚至不需要剖分,分类讨论一下就好。

SDOI 2014】旅行

动态开点线段树。

【NOI 2015】软件包管理器

区间推平区间求和。

树链剖分模板

换根,子树求和,子树加,链求和,链加。


链操作比较简单。

假设当前根为 rt,操作 u 的子树,考虑换根对子树的影响,分三类讨论:

anc(i) 表示在 1 为根的情况下,i 的祖先集合)

u \in anc(rt)

可以知道,除了 rt 所在的那个子树,u 的其他儿子的子树都会被修改。

所以通过倍增求出 rt 所在的子树的根,将所有的数修改并将该根减去影响就好。

rt \in anc(u)

直接子树加。

rt = u

全部加。

时间复杂度 O(n \log^2 n)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100000 + 10;
const int MAX_LOG = 18;

int n, m;

namespace G {
    int head[MAXN], e_cnt;
    struct Edge { int nxt, to; } e[MAXN << 1];
    void add_edge(int u, int v) { e[++e_cnt].nxt = head[u], e[e_cnt].to = v, head[u] = e_cnt; }
    int dfs_clock = 0, dtp[MAXN], rt;
    struct Vertix { int dep, son, sz, fa, ff[MAX_LOG + 10], top, dfn, val; } vtx[MAXN];
    void dfs1(int u) {
        vtx[u].dep = vtx[vtx[u].fa].dep + 1, vtx[u].sz = 1, vtx[u].ff[0] = vtx[u].fa;
        for (int i = 1; i <= MAX_LOG; ++i) vtx[u].ff[i] = vtx[vtx[u].ff[i - 1]].ff[i - 1];
        for (int _ = head[u], v; _; _ = e[_].nxt) {
            v = e[_].to; if (v == vtx[u].fa) continue;
            vtx[v].fa = u, dfs1(v), vtx[u].sz += vtx[v].sz;
            if (vtx[v].sz > vtx[vtx[u].son].sz) vtx[u].son = v;
        }
    }
    void dfs2(int u, int top) {
        vtx[u].top = top, dtp[vtx[u].dfn = ++dfs_clock] = u;
        if (vtx[u].son) dfs2(vtx[u].son, top);
        for (int _ = head[u], v; _; _ = e[_].nxt) {
            v = e[_].to; if (v == vtx[u].fa || v == vtx[u].son) continue;
            dfs2(v, v);
        }
    }
    int find_son(int u, int top) {
        for (int i = MAX_LOG; ~i; --i) if (vtx[vtx[u].ff[i]].dep > vtx[top].dep) u = vtx[u].ff[i];
        return u;
    }
}

namespace Segment_Tree {
struct Segment_Tree {
    #define mid ((l + r) >> 1)
    #define ls k << 1, l, mid
    #define rs k << 1 | 1, mid + 1, r
    struct node { ll data, add; } t[MAXN << 2];
    void build(int k, int l, int r) {
        if (l == r) { t[k].data = G::vtx[G::dtp[l]].val; return ; }
        build(ls), build(rs);
        t[k].data = t[k << 1].data + t[k << 1 | 1].data;
    }
    void modify(int k, int l, int r, int ql, int qr, ll val) {
        if (ql <= l && r <= qr) { t[k].add += val; return ; }
        t[k].data += 1ll * (min(qr, r) - max(ql, l) + 1) * val;
        if (ql <= mid) modify(ls, ql, qr, val);
        if (qr > mid) modify(rs, ql, qr, val);
    }
    ll query(int k, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) { return t[k].data + 1ll * (r - l + 1) * t[k].add; }
        ll val = 1ll * (min(qr, r) -  max(ql, l) + 1) * t[k].add;
        if (ql <= mid) val += query(ls, ql, qr);
        if (qr > mid) val += query(rs, ql, qr);
        return val;
    }
} t;
} using namespace Segment_Tree;

void route_modify(int u, int v, ll val) {
    using namespace G;
    while (vtx[u].top != vtx[v].top) {
        if (vtx[vtx[u].top].dep < vtx[vtx[v].top].dep) swap(u, v);
        t.modify(1, 1, n, vtx[vtx[u].top].dfn, vtx[u].dfn, val);
        u = vtx[vtx[u].top].fa;
    }
    t.modify(1, 1, n, min(vtx[u].dfn, vtx[v].dfn), max(vtx[u].dfn, vtx[v].dfn), val);
}
ll route_query(int u, int v) {
    using namespace G;
    ll ans = 0;
    while (vtx[u].top != vtx[v].top) {
        if (vtx[vtx[u].top].dep < vtx[vtx[v].top].dep) swap(u, v);
        ans += t.query(1, 1, n, vtx[vtx[u].top].dfn, vtx[u].dfn);
        u = vtx[vtx[u].top].fa;
    }
    ans += t.query(1, 1, n, min(vtx[u].dfn, vtx[v].dfn), max(vtx[u].dfn, vtx[v].dfn));
    return ans;
}

void subtree_modify(int u, ll val) {
    using namespace G;
    if (rt == u) t.modify(1, 1, n, 1, n, val);
    else if (vtx[u].dfn <= vtx[rt].dfn && vtx[rt].dfn <= vtx[u].dfn + vtx[u].sz - 1) {
        int v = find_son(rt, u);
        t.modify(1, 1, n, 1, n, val), t.modify(1, 1, n, vtx[v].dfn, vtx[v].dfn + vtx[v].sz - 1, -val);
    } else t.modify(1, 1, n, vtx[u].dfn, vtx[u].dfn + vtx[u].sz - 1, val);
}
ll subtree_query(int u) {
    using namespace G;
    ll ans = 0;
    if (u == rt) return t.query(1, 1, n, 1, n);
    else if (vtx[u].dfn <= vtx[rt].dfn && vtx[rt].dfn <= vtx[u].dfn + vtx[u].sz - 1) {
        int v = find_son(rt, u);
        ans = t.query(1, 1, n, 1, n), ans -= t.query(1, 1, n, vtx[v].dfn, vtx[v].dfn + vtx[v].sz - 1);
    } else ans = t.query(1, 1, n, vtx[u].dfn, vtx[u].dfn + vtx[u].sz - 1);
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &G::vtx[i].val);
    G::rt = 1;
    for (int i = 2, fa; i <= n; ++i) {
        scanf("%d", &fa); G::add_edge(fa, i), G::add_edge(i, fa);
    }
    G::dfs1(1), G::dfs2(1, 1);
    scanf("%d", &m);
    t.build(1, 1, n);
    for (int i = 1, opt; i <= m; ++i) {
        scanf("%d", &opt);
        if (opt == 1) scanf("%d", &G::rt);
        else if (opt == 2) {
            int u, v; ll val; scanf("%d %d %lld", &u, &v, &val);
            route_modify(u, v, val);   
        } else if (opt == 4) {
            int u, v; scanf("%d %d", &u, &v);
            printf("%lld\n", route_query(u, v));
        } else if (opt == 3) {
            int u; ll val; scanf("%d %lld", &u, &val);
            subtree_modify(u, val);
        } else {
            int u; scanf("%d", &u);
            printf("%lld\n", subtree_query(u));
        }
    }
    return 0;
}

【ZJOI 2011】道馆之战

一棵树,每个节点是一个房间,两个房间相邻当且仅当树上两个节点相邻。

每个房间有且只有两个区域,称为 A, B 区域。每个区域要么为冰块,要么为障碍物。

一次游走从节点 u 到节点 v 是合法的,当且仅当:

  • 只能严格按照树上 uv 的简单路径走。
  • 任何时刻不能在障碍物上。
  • 不能重复经过同一个房间的同一个区域。
  • 可以从一个房间的一个区域到另一个区域。
  • 从一个房间到另一个房间,必须从同一个区域出发,到达同一个区域。

求一次游走最多能经过多少冰块。

n \leq 3 \times 10^4


先考虑区间上的情况。

看起来可以线段树。

假设线段树节点 i,代表区间 [l_i, r_i],记录 mx(0/1, 0/1, 0/1),代表从最左/右的房间出发,由房间的 A/B 区域进,A/B 区域出(但并不要求一定要走出去),最多踩多少冰块。

考虑如何合并,因为涉及连通性,所以还得再维护一个 can(0/1, 0/1),表示能否从最左端的 A/B 一直走到最右端的 A/B。

合并如下:

Node operator +(const Node& a, const Node& b) {
    Node res;
    for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) {
        res.mx[0][i][j] = max(a.mx[0][i][0] + a.can[i][0] * b.mx[0][0][j], a.mx[0][i][1] + a.can[i][1] * b.mx[0][1][j]);
        res.mx[1][i][j] = max(b.mx[1][i][0] + b.can[0][i] * a.mx[1][0][j], b.mx[1][i][1] + b.can[1][i] * a.mx[1][1][j]);
        res.can[i][j] = (a.can[i][0] && b.can[0][j]) || (a.can[i][1] && b.can[1][j]);
    }
    return res;
}

树上会有一些区别。

假设要求 uv 的节点。

首先,左链(u 到 LCA)上,靠 v 近的是左边,右链靠 v 近的是右边。左链反了。

其次,当前记录的答案应该作为右值更新。因为我们记录的是深度更深的,是右边。

然后就能搬到树上了。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50000 + 10;
const int MAXM = 100000 + 10;

int n, m;

namespace Segment_Tree {
    #define mid ((l + r) >> 1)
    #define ls k << 1, l, mid
    #define rs k << 1 | 1, mid + 1, r
    struct Node {
        int mx[2][2][2], can[2][2];
        Node& swp() {
            for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) swap(mx[0][i][j], mx[1][i][j]);
            swap(can[0][1], can[1][0]);
            return *this;
        }
        void init() { memset(mx, 0, sizeof mx), memset(can, 0, sizeof can); }
    } arr[MAXN];
    Node operator +(const Node& a, const Node& b) {
        Node res;
        for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) {
            res.mx[0][i][j] = max(a.mx[0][i][0] + a.can[i][0] * b.mx[0][0][j], a.mx[0][i][1] + a.can[i][1] * b.mx[0][1][j]);
            res.mx[1][i][j] = max(b.mx[1][i][0] + b.can[0][i] * a.mx[1][0][j], b.mx[1][i][1] + b.can[1][i] * a.mx[1][1][j]);
            res.can[i][j] = (a.can[i][0] && b.can[0][j]) || (a.can[i][1] && b.can[1][j]);
        }
        return res;
    }
    Node generator(int a, int b) {
        Node res;
        for (int i = 0; i < 2; ++i) res.mx[i][0][0] = a, res.mx[i][1][1] = b, res.mx[i][0][1] = a ? (b ? 2 : 1) : 0, res.mx[i][1][0] = b ? (a ? 2 : 1) : 0;
        res.can[0][0] = a, res.can[0][1] = res.can[1][0] = (a && b), res.can[1][1] = b;
        return res;
    }
    struct Segment_Tree {
        Node t[MAXN << 2];
        void build(int k, int l, int r) {
            if (l == r) { t[k] = arr[l]; return ; }
            build(ls), build(rs);
            t[k] = t[k << 1] + t[k << 1 | 1];
        }
        void modify(int k, int l, int r, int pos, const Node& val) {
            if (l == r) { t[k] = val; return ; }
            if (pos <= mid) modify(ls, pos, val);
            else modify(rs, pos, val);
            t[k] = t[k << 1] + t[k << 1 | 1];
        }
        Node query(int k, int l, int r, int ql, int qr) {
            if (ql <= l && r <= qr) return t[k];
            Node res; bool flg = false;
            if (ql <= mid) res = query(ls, ql, qr), flg = true;
            if (qr > mid) flg ? res = res + query(rs, ql, qr) : res = query(rs, ql, qr);
            return res;
        }
    } t;
} using namespace Segment_Tree;

namespace G {
    int head[MAXN], e_cnt;
    struct Edge { int nxt, to; } e[MAXN << 1];
    void add(int u, int v) { e[++e_cnt].to = v, e[e_cnt].nxt = head[u], head[u] = e_cnt; }
    struct Vertix { int dep, fa, sz, son, top, dfn, vala, valb; } vtx[MAXN];
    void dfs1(int u) {
        vtx[u].dep = vtx[vtx[u].fa].dep + 1, vtx[u].sz = 1;
        for (int _ = head[u], v; _; _ = e[_].nxt) {
            v = e[_].to;
            if (v == vtx[u].fa) continue;
            vtx[v].fa = u, dfs1(v), vtx[u].sz += vtx[v].sz;
            if (vtx[vtx[u].son].sz < vtx[v].sz) vtx[u].son = v;
        }
    }
    int dfs_clock;
    void dfs2(int u, int top) {
        vtx[u].top = top; arr[vtx[u].dfn = ++dfs_clock] = generator(vtx[u].vala, vtx[u].valb);
        if (vtx[u].son) dfs2(vtx[u].son, top);
        for (int _ = head[u], v; _; _ = e[_].nxt) {
            v = e[_].to;
            if (v == vtx[u].son || v == vtx[u].fa) continue;
            dfs2(v, v);
        }
    }
} 

int route_query(int u, int v) {
    using namespace G;
    Node res[2];
    bool cur = false, flg[2];
    flg[0] = flg[1] = false;
    while (vtx[u].top != vtx[v].top) {
        if (vtx[vtx[u].top].dep < vtx[vtx[v].top].dep) swap(u, v), cur ^= 1;
        int top = vtx[u].top;
        if (flg[cur]) res[cur] = t.query(1, 1, n, vtx[top].dfn, vtx[u].dfn) + res[cur]; else res[cur] = t.query(1, 1, n, vtx[top].dfn, vtx[u].dfn), flg[cur] = true;
        u = vtx[top].fa;
    }
    if (vtx[u].dep < vtx[v].dep) swap(u, v), cur ^= 1;
    if (flg[cur]) res[cur] = t.query(1, 1, n, vtx[v].dfn, vtx[u].dfn) + res[cur]; else flg[cur] = true, res[cur] = t.query(1, 1, n, vtx[v].dfn, vtx[u].dfn);
    Node ans;
    if (!flg[0] && flg[1]) ans = res[1];
    else if (!flg[1] && flg[0]) ans = res[0].swp();
    else ans = res[0].swp() + res[1];
    int fans = -INT_MAX;
    for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) fans = max(fans, ans.mx[0][i][j]);
    return fans;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d %d", &u, &v);
        G::add(u, v), G::add(v, u);
    }
    char s[4];
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s + 1);
        G::vtx[i].vala = s[1] == '.', G::vtx[i].valb = s[2] == '.';
    }
    G::dfs1(1), G::dfs2(1, 1);
    t.build(1, 1, n);
    char opt[4];
    for (int i = 1; i <= m; ++i) {
        scanf("%s", opt + 1);
        if (opt[1] == 'C')  {
            int u; 
            scanf("%d %s", &u, s + 1);
            Node cur = generator(s[1] == '.', s[2] == '.');
            t.modify(1, 1, n, G::vtx[u].dfn, cur);
        } else {
            int u, v;
            scanf("%d %d", &u, &v);
            printf("%d\n", route_query(u, v));
        }
    }
    return 0;
}

【BZOJ 2157】旅游

给一棵树,边带权,链取反,边更改,求链 max, min, sum。


考虑边转点,边权转到深度较深的点上。

特判 LCA,两种方式,第一种同树链剖分模板,倍增找点。

第二种临时修改 LCA 的点权。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;
const int MAX_LOG = 18;

int n;

void chkmin(int& a, int b) { if (a > b) a = b; }
void chkmax(int& a, int b) { if (a < b) a = b; }

namespace G {
    int head[MAXN], e_cnt;
    int dwn[MAXN];
    struct Edge { int nxt, to, w, id; } e[MAXN];
    void add(int u, int v, int w, int id) { e[++e_cnt].nxt = head[u], e[e_cnt].to = v, e[e_cnt].w = w, e[e_cnt].id = id, head[u] = e_cnt; }
    struct Vertix { int dep, fa, sz, son, dfn, val, top, ff[MAX_LOG + 3]; } vtx[MAXN];
    void dfs1(int u) {
        vtx[u].dep = vtx[vtx[u].fa].dep + 1, vtx[u].sz = 1, vtx[u].ff[0] = vtx[u].fa;
        for (int i = 1; i <= MAX_LOG; ++i) vtx[u].ff[i] = vtx[vtx[u].ff[i - 1]].ff[i - 1];
        for (int _ = head[u], v; _; _ = e[_].nxt) {
            v = e[_].to;
            if (v == vtx[u].fa) continue;
            dwn[e[_].id] = v;
            vtx[v].fa = u, dfs1(v), vtx[u].sz += vtx[v].sz;
            vtx[v].val = e[_].w;
            if (vtx[v].sz > vtx[vtx[u].son].sz) vtx[u].son = v;
        } 
    }
    int dfs_clock, dtp[MAXN];
    void dfs2(int u, int top) {
        vtx[u].top = top, dtp[vtx[u].dfn = ++dfs_clock] = u;
        if (vtx[u].son) dfs2(vtx[u].son, top);
        for (int _ = head[u], v; _; _ = e[_].nxt) {
            v = e[_].to;
            if (v == vtx[u].son || v == vtx[u].fa) continue;
            dfs2(v, v);
        }
    }
    int lca(int u, int v) {
        while (1) {
            if (vtx[u].top == vtx[v].top) return vtx[u].dep < vtx[v].dep ? u : v;
            if (vtx[vtx[u].top].dep < vtx[vtx[v].top].dep) swap(u, v);
            u = vtx[vtx[u].top].fa;
        }
    }
    int find_rt(int u, int top) {
        for (int i = MAX_LOG; ~i; --i) if (vtx[u].dep - (1 << i) > vtx[top].dep) u = vtx[u].ff[i];
        return u;
    }
}

namespace Segment_Tree {
    #define mid ((l + r) >> 1)
    #define ls k << 1, l, mid
    #define rs k << 1 | 1, mid + 1, r
    struct Segment_Tree {    
        struct Node { ll data[3]; bool flg; } t[MAXN << 2];
        void pushdown(int k) {
            if (t[k].flg) {
                t[k << 1].flg ^= 1, t[k << 1 | 1].flg ^= 1;
                t[k << 1].data[0] = -t[k << 1].data[0], t[k << 1 | 1].data[0] = -t[k << 1 | 1].data[0];
                swap(t[k << 1].data[1], t[k << 1].data[2]), t[k << 1].data[1] = -t[k << 1].data[1], t[k << 1].data[2] = -t[k << 1].data[2];
                swap(t[k << 1 | 1].data[1], t[k << 1 | 1].data[2]), t[k << 1 | 1].data[1] = -t[k << 1 | 1].data[1], t[k << 1 | 1].data[2] = -t[k << 1 | 1].data[2];
                t[k].flg ^= 1;
            }
        }
        void pushup(int k) {
            t[k].data[0] = t[k << 1 | 1].data[0] + t[k << 1].data[0];
            t[k].data[1] = min(t[k << 1].data[1], t[k << 1 | 1].data[1]), t[k].data[2] = max(t[k << 1].data[2], t[k << 1 | 1].data[2]);
        }
        void build(int k, int l, int r) {
            if (l == r) { t[k].data[0] = t[k].data[1] = t[k].data[2] = G::vtx[G::dtp[l]].val; return ; }
            build(ls), build(rs);
            pushup(k);
        }
        void modify(int k, int l, int r, int pos, int val) {
            if (l == r) { t[k].data[0] = t[k].data[1] = t[k].data[2] = val; return ; }
            pushdown(k);
            if (pos <= mid) modify(ls, pos, val);
            else modify(rs, pos, val);
            pushup(k);
        }
        void negtive(int k, int l, int r, int ql, int qr) {
            if (ql <= l && r <= qr) { t[k].data[0] = -t[k].data[0], swap(t[k].data[1], t[k].data[2]), t[k].data[1] = -t[k].data[1], t[k].data[2] = -t[k].data[2], t[k].flg ^= 1; return ; }
            pushdown(k);
            if (ql <= mid) negtive(ls, ql, qr) ;
            if (qr > mid) negtive(rs, ql, qr);
            pushup(k);
        }
        ll query(int k, int l, int r, int ql, int qr, int mode) {
            if (ql <= l && r <= qr) { return t[k].data[mode]; }
            pushdown(k); ll ret = (mode == 0 ? 0 : (mode == 1 ? INT_MAX : -INT_MAX));
            if (ql <= mid) ret = (mode == 0 ? ret + query(ls, ql, qr, mode) : (mode == 1 ? min(ret, query(ls, ql, qr, mode)) : max(ret, query(ls, ql, qr, mode))));
            if (qr > mid) ret = (mode == 0 ? ret + query(rs, ql, qr, mode) : (mode == 1 ? min(ret, query(rs, ql, qr, mode)) : max(ret, query(rs, ql, qr, mode))));
            return ret;
        }
    } t;
} using namespace Segment_Tree;

void negtive(int u, int v) {
    using namespace G;
    int w = lca(u, v);
    while (1) {
        if (vtx[u].top == vtx[w].top) { if (u == w) break; t.negtive(1, 1, n, vtx[find_rt(u, w)].dfn, vtx[u].dfn); break; }
        int top = vtx[u].top;
        t.negtive(1, 1, n, vtx[top].dfn, vtx[u].dfn);
        u = vtx[top].fa;
    }
    while (1) {
        if (vtx[v].top == vtx[w].top) { if (v == w) break; t.negtive(1, 1, n, vtx[find_rt(v, w)].dfn, vtx[v].dfn); break; }
        int top = vtx[v].top;
        t.negtive(1, 1, n, vtx[top].dfn, vtx[v].dfn);
        v = vtx[top].fa;
    }
}

ll route_query(int u, int v, int mode) {
    using namespace G;
    int w = lca(u, v); ll ret = (mode == 0 ? 0 : (mode == 1 ? INT_MAX : -INT_MAX));
    while (1) {
        if (vtx[u].top == vtx[w].top) {
            if (u == w) break;
            int top = find_rt(u, w);
            ret = (mode == 0 ? ret + t.query(1, 1, n, vtx[top].dfn, vtx[u].dfn, mode) : 
                  (mode == 1 ? min(ret, t.query(1, 1, n, vtx[top].dfn, vtx[u].dfn, mode)) :
                               max(ret, t.query(1, 1, n, vtx[top].dfn, vtx[u].dfn, mode))));
            break;
        }
        int top = vtx[u].top;
        ret = (mode == 0 ? ret + t.query(1, 1, n, vtx[top].dfn, vtx[u].dfn, mode) : 
              (mode == 1 ? min(ret, t.query(1, 1, n, vtx[top].dfn, vtx[u].dfn, mode)) :
                           max(ret, t.query(1, 1, n, vtx[top].dfn, vtx[u].dfn, mode))));
        u = vtx[top].fa;
    }
    while (1) {
        if (vtx[v].top == vtx[w].top) {
            if (v == w) break;
            int top = find_rt(v, w);
            ret = (mode == 0 ? ret + t.query(1, 1, n, vtx[top].dfn, vtx[v].dfn, mode) : 
                  (mode == 1 ? min(ret, t.query(1, 1, n, vtx[top].dfn, vtx[v].dfn, mode)) :
                               max(ret, t.query(1, 1, n, vtx[top].dfn, vtx[v].dfn, mode))));
            break;
        }
        int top = vtx[v].top;
        ret = (mode == 0 ? ret + t.query(1, 1, n, vtx[top].dfn, vtx[v].dfn, mode) : 
              (mode == 1 ? min(ret, t.query(1, 1, n, vtx[top].dfn, vtx[v].dfn, mode)) :
                           max(ret, t.query(1, 1, n, vtx[top].dfn, vtx[v].dfn, mode))));
        v = vtx[top].fa;
    }
    return ret;
}

int main() {
    scanf("%d", &n);
    for (int i = 1, u, v, w; i < n; ++i) {
        scanf("%d %d %d", &u, &v, &w);
        u++, v++;
        G::add(u, v, w, i), G::add(v, u, w, i);
    }
    G::dfs1(1), G::dfs2(1, 1);
    t.build(1, 1, n);
    int q; scanf("%d", &q);
    char opt[5];
    for (int _ = 1; _ <= q; ++_) {
        scanf("%s", opt + 1);
        if (opt[1] == 'C') {
            int pos; ll val;
            scanf("%d %lld", &pos, &val);
            t.modify(1, 1, n, G::vtx[G::dwn[pos]].dfn, val);
        } else if (opt[1] == 'N') {
            int u, v; scanf("%d %d", &u, &v); u++, v++;
            negtive(u, v);
        } else if (opt[1] == 'S') {
            int u, v; scanf("%d %d", &u, &v); u++, v++;
            printf("%lld\n", route_query(u, v, 0));
        } else if (opt[2] == 'A') {
            int u, v; scanf("%d %d", &u, &v); u++, v++;
            printf("%lld\n", route_query(u, v, 2));
        } else {
            int u, v; scanf("%d %d", &u, &v); u++, v++;
            printf("%lld\n", route_query(u, v, 1));
        }
    }
    return 0;
}

【HAOI 2015】树上操作

询问根到点的点权和,点加,子树加。


考虑直接维护答案。

点加就是子树加。

子树加则考虑影响,假设加节点 u,值为 x

对于 v \in \operatorname{subtree}(u),其答案会增加 (\operatorname{dep}(v) - \operatorname{u} + 1) * x

发现 -(\operatorname{dep(u)} + 1) * x 对于一次操作是常数,直接修改。而对于子树中的每一个点打上 x 的标记,询问时加上 \operatorname{dep}(v) * \operatorname{tag}(v) 即可。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 10;

typedef long long ll;

int n, m;

namespace G {
    int head[MAXN], e_cnt;
    struct Edge { int nxt, to, id; } e[MAXN << 1];
    void add(int u, int v) { e[++e_cnt].nxt = head[u], e[e_cnt].to = v, head[u] = e_cnt; }
    struct Vertix { int dep, fa, dfn, sz; ll val, add; } vtx[MAXN];
    int dfs_clock, dtp[MAXN];
    void dfs(int u) {
        vtx[u].sz = 1, vtx[u].dep = vtx[vtx[u].fa].dep + 1, dtp[vtx[u].dfn = ++dfs_clock] = u; vtx[u].val += vtx[vtx[u].fa].val;
        for (int _ = head[u], v; _; _ = e[_].nxt) {
            v = e[_].to;
            if (v == vtx[u].fa) continue;
            vtx[v].fa = u, dfs(v), vtx[u].sz += vtx[v].sz;
        }
    }
}

namespace Segment_Tree {
    #define mid ((l + r) >> 1)
    #define ls k << 1, l, mid
    #define rs k << 1 | 1, mid + 1, r
    struct Segment_Tree { 
        struct Node { ll data, add, s; } t[MAXN << 2];
        void pushdown(int k) {
            t[k << 1].add += t[k].add, t[k << 1].s += t[k].s;
            t[k << 1 | 1].add += t[k].add, t[k << 1 | 1].s += t[k].s;
            t[k].s = t[k].add = 0;
        }
        void build(int k, int l, int r) {
            if (l == r) { t[k].add = G::vtx[G::dtp[l]].val; return ; }
            build(ls), build(rs);
        }
        void modify(int k, int l, int r, int ql, int qr, ll val1, ll val2) {
            if (ql <= l && r <= qr) { t[k].add += val1, t[k].s += val2; return ; }
            pushdown(k);
            if (ql <= mid) modify(ls, ql, qr, val1, val2);
            if (qr > mid) modify(rs, ql, qr, val1, val2);
        }
        ll query(int k, int l, int r, int pos) {
            if (l == r) return t[k].add + t[k].s * G::vtx[G::dtp[l]].dep;
            pushdown(k); ll ret = 0;
            if (pos <= mid) return query(ls, pos);
            else return query(rs, pos);
        }

    } t;
} using namespace Segment_Tree;

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%lld", &G::vtx[i].val);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d %d", &u, &v);
        G::add(u, v), G::add(v, u);
    }
    G::dfs(1);
    t.build(1, 1, n);
    for (int i = 1, opt; i <= m; ++i) {
        scanf("%d", &opt);
        if (opt == 1) {
            int x; ll a;
            scanf("%d %lld", &x, &a); t.modify(1, 1, n, G::vtx[x].dfn, G::vtx[x].dfn + G::vtx[x].sz - 1, a, 0);
        } else if (opt == 2) {
            int x; ll a;
            scanf("%d %lld", &x, &a); t.modify(1, 1, n, G::vtx[x].dfn, G::vtx[x].dfn + G::vtx[x].sz - 1, -1ll * (G::vtx[x].dep - 1) * a, a);
        } else {
            int x; scanf("%d", &x);
            printf("%lld\n", t.query(1, 1, n, G::vtx[x].dfn));
        }
    }
    return 0;
}

【BZOJ 3221】Obserbing the tree树上询问

链加等差数列,链求和,支持历史版本。


主席树就行。

标记永久化比较麻烦,我的写法是 tag 维护完全覆盖的贡献,不完全覆盖就加到 data 里头。

搬到树上的时候,要考虑清楚,左链的公差是相反数。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 4e6 + 10;
const int MAX_NODE_CNT = 1e7 + 10;

int n, m;
char opt[3];

namespace G {
    int head[MAXN], e_cnt;
    struct Edge { int nxt, to; } e[MAXN << 1];
    void addedge(int u, int v) { e[++e_cnt].nxt = head[u], e[e_cnt].to = v, head[u] = e_cnt; }
    struct Vertix { int fa, dep, sz, son, top, dfn; } vtx[MAXN];
    void dfs1(int u) {
        vtx[u].dep = vtx[vtx[u].fa].dep + 1, vtx[u].sz = 1;
        int max_son = 0;
        for (int _ = head[u], v; _; _ = e[_].nxt) {
            v = e[_].to;
            if (v == vtx[u].fa) continue;
            vtx[v].fa = u, dfs1(v); vtx[u].sz += vtx[v].sz;
            if (vtx[v].sz > max_son) max_son = vtx[v].sz, vtx[u].son = v;
        }
    }
    int dfs_clock, dtp[MAXN];
    void dfs2(int u, int top) {
        vtx[u].top = top, dtp[vtx[u].dfn = ++dfs_clock] = u;
        if (vtx[u].son) dfs2(vtx[u].son, top);
        for (int _ = head[u], v; _; _ = e[_].nxt) {
            v = e[_].to;
            if (v == vtx[u].fa || v == vtx[u].son) continue;
            dfs2(v, v);
        }
    } 
    int lca(int u, int v) {
        while (1) {
            if (vtx[u].top == vtx[v].top) return vtx[u].dep < vtx[v].dep ? u : v;
            if (vtx[vtx[u].top].dep > vtx[vtx[v].top].dep) swap(u, v);
            v = vtx[vtx[v].top].fa;
        }
    }
};

int ver_cnt, cur_ver;
namespace Chairman_Tree {
    struct Chairman_Tree {
        #define mid ((l + r) >> 1)
        #define ls(_) t[_].ls
        #define rs(_) t[_].rs
        #define lq(_) t[_].ls, l, mid
        #define rq(_) t[_].rs, mid + 1, r
        int node_cnt, rt[MAXN];
        int& operator [](const int& x) { return rt[x]; }
        struct node { int ls, rs; ll sum, num, delta; } t[MAX_NODE_CNT];
        void build(int& cur, int l, int r) {
            cur = ++node_cnt;
            if (l == r) return ;
            build(lq(cur)), build(rq(cur));
        }
        void modify(int pre, int& cur, int l, int r, int ql, int qr, ll num, ll delta) {
            cur = ++node_cnt; t[cur] = t[pre];
            if (ql <= l && r <= qr) { t[cur].num += num, t[cur].delta += delta; return ; }
            int sl = max(l, ql), sr = min(r, qr);
            t[cur].sum += (num + 1ll * (sl - ql) * delta + num + 1ll * (sr - ql) * delta) * (sr - sl + 1) / 2;
            if (ql <= mid) modify(ls(pre), lq(cur), ql, min(qr, mid), num, delta);
            if (qr > mid) modify(rs(pre), rq(cur), max(mid + 1, ql), qr, num + 1ll * (max(mid + 1, ql) - ql) * delta, delta);
        }
        ll query(int cur, int l, int r, int ql, int qr) {
            if (ql <= l && r <= qr) { return t[cur].sum + (t[cur].num + t[cur].num + 1ll * (r - l) * t[cur].delta) * (r - l + 1) / 2; }
            int sl = max(l, ql), sr = min(r, qr);
            ll val = (t[cur].num + 1ll * (sl - l) * t[cur].delta + t[cur].num + 1ll * (sr - l) * t[cur].delta) * (sr - sl + 1) / 2;
            if (ql <= mid) val += query(lq(cur), ql, min(mid, qr));
            if (qr > mid) val += query(rq(cur), max(mid + 1, ql), qr);
            return val;
        }
    } t;
} using namespace Chairman_Tree;

void modify(int u, int v, ll num, ll delta) {
    int lca = G::lca(u, v);
    t[++ver_cnt] = t[cur_ver];
    cur_ver = ver_cnt;
    while (1) {
        if (G::vtx[u].top == G::vtx[lca].top) {
            num += 1ll * (G::vtx[u].dep - G::vtx[lca].dep) * delta;
            t.modify(t[cur_ver], t[cur_ver], 1, n, G::vtx[lca].dfn, G::vtx[u].dfn, num, -delta);
            t.modify(t[cur_ver], t[cur_ver], 1, n, G::vtx[lca].dfn, G::vtx[lca].dfn, -num, 0);
            break;
        }
        int top = G::vtx[u].top;
        num += 1ll * (G::vtx[u].dep - G::vtx[top].dep) * delta;
        t.modify(t[cur_ver], t[cur_ver], 1, n, G::vtx[top].dfn, G::vtx[u].dfn, num, -delta);
        u = G::vtx[top].fa; num += delta;
    }
    num += 1ll * (G::vtx[v].dep - G::vtx[lca].dep) * delta;
    while (1) {
        if (G::vtx[v].top == G::vtx[lca].top) {
            num -= 1ll * (G::vtx[v].dep - G::vtx[lca].dep) * delta;
            t.modify(t[cur_ver], t[cur_ver], 1, n, G::vtx[lca].dfn, G::vtx[v].dfn, num, delta);
            break;
        }
        int top = G::vtx[v].top;
        num -= 1ll * (G::vtx[v].dep - G::vtx[top].dep) * delta;
        t.modify(t[cur_ver], t[cur_ver], 1, n, G::vtx[top].dfn, G::vtx[v].dfn, num, delta);
        v = G::vtx[top].fa; num -= delta;
    }
}

ll query(int u, int v) {
    ll ans = 0;
    while (G::vtx[u].top != G::vtx[v].top) {
        if (G::vtx[G::vtx[u].top].dep < G::vtx[G::vtx[v].top].dep) swap(u, v);
        ans += t.query(t[cur_ver], 1, n, G::vtx[G::vtx[u].top].dfn, G::vtx[u].dfn);
        u = G::vtx[G::vtx[u].top].fa;
    }
    ans += t.query(t[cur_ver], 1, n, min(G::vtx[u].dfn, G::vtx[v].dfn), max(G::vtx[u].dfn, G::vtx[v].dfn));
    return ans;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int _ = 1, u, v; _ < n; ++_) {
        scanf("%d %d", &u, &v); G::addedge(u, v), G::addedge(v, u);
    }
    G::dfs1(1), G::dfs2(1, 1);
    ll pre_ans = 0;
    t.build(t[0], 1, n);
    for (int i = 1; i <= m; ++i) {
        scanf("%s", opt + 1);
        if (opt[1] == 'c') {
            int x, y; ll num, delta;
            scanf("%d %d %lld %lld", &x, &y, &num, &delta);
            x ^= pre_ans, y ^= pre_ans;
            modify(x, y, num, delta);
        } else if (opt[1] == 'q') {
            int x, y; scanf("%d %d", &x, &y);
            x ^= pre_ans, y ^= pre_ans;
            printf("%lld\n", pre_ans = query(x, y));
        } else {
            int x; scanf("%d", &x);
            x ^= pre_ans;
            cur_ver = x;
        }
    }
    return 0;
}

关于证明欧拉函数的积性性质
上一篇 «
可持久化线段树 可持久化 01Trie 简述与做题记录
» 下一篇