旅行

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100000;
const int MAXC = 100000;
int n, m;
int w[MAXN + 5];  // 每个点的权值
int c[MAXN + 5];  // 每个点的信仰
int rt[MAXC + 5]; // rt[i] 宗教 i 的根节点编号
namespace ST
{
    // 线段树：单点修改、区间查询（区间和）
    struct Node
    {
        // 左右子节点 lc,rc
        // 区间和: sum，区间最大值：mx，加法懒标记：lazy
        int lc, rc, sum, mx, lazy;
    };
    int tot; // 动态开点线段树节点数量
    Node t[20 * MAXN + 5];
    // 当前做到了树上的now号节点，当前节点对应的区间为 [l,r]
    // 需要给 [x,y] 这些数都增加 z
    void update(int now, int l, int r, int x, int y, int z)
    {
        t[now].sum += (min(y, r) - max(x, l) + 1) * z;
        if (x <= l && r <= y)
        {
            t[now].lazy += z;
            t[now].mx += z;
            return;
        }
        int mid = (l + r) / 2;
        // 左子树 now*2,l,mid
        // 右子树 now*2+1,mid+1,r
        if (x <= mid)
        {
            if (!t[now].lc)
                t[now].lc = ++tot;
            update(t[now].lc, l, mid, x, y, z);
        }
        if (y > mid)
        {
            if (!t[now].rc)
                t[now].rc = ++tot;
            update(t[now].rc, mid + 1, r, x, y, z);
        }
        t[now].mx = 0;
        if (t[now].lc)
            t[now].mx = max(t[now].mx, t[t[now].lc].mx);
        if (t[now].rc)
            t[now].mx = max(t[now].mx, t[t[now].rc].mx);
    }
    int query_sum(int now, int l, int r, int x, int y, int lazySum)
    {
        //[l,r] 是 [x,y] 的子区间
        if (x <= l && r <= y)
            return t[now].sum + (r - l + 1) * lazySum;
        int mid = (l + r) / 2;
        // 左子树 now*2,l,mid
        // 右子树 now*2+1,mid+1,r
        int res = 0;
        lazySum += t[now].lazy;
        if (x <= mid)
        {
            if (!t[now].lc)
                t[now].lc = ++tot;
            res += query_sum(t[now].lc, l, mid, x, y, lazySum);
        }
        if (y > mid)
        {
            if (!t[now].rc)
                t[now].rc = ++tot;
            res += query_sum(t[now].rc, mid + 1, r, x, y, lazySum);
        }
        return res;
    }
    int query_max(int now, int l, int r, int x, int y, int lazySum)
    {
        //[l,r] 是 [x,y] 的子区间
        if (x <= l && r <= y)
            return t[now].mx + lazySum;
        int mid = (l + r) / 2;
        // 左子树 now*2,l,mid
        // 右子树 now*2+1,mid+1,r
        int res = 0;
        lazySum += t[now].lazy;
        if (x <= mid)
        {
            if (!t[now].lc)
                t[now].lc = ++tot;
            res = max(res, query_max(t[now].lc, l, mid, x, y, lazySum));
        }
        if (y > mid)
        {
            if (!t[now].rc)
                t[now].rc = ++tot;
            res = max(res, query_max(t[now].rc, mid + 1, r, x, y, lazySum));
        }
        return res;
    }
}
namespace T
{
    vector<int> e[MAXN + 5];
    // 每个点的：父节点、深度、大小、重子节点
    int fa[MAXN + 5], dep[MAXN + 5], siz[MAXN + 5], hson[MAXN + 5];
    void dfs_build(int u, int fat)
    {
        hson[u] = 0;
        siz[hson[u]] = 0;
        siz[u] = 1;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i];
            if (v == fat)
                continue;
            dep[v] = dep[u] + 1;
            fa[v] = u;
            dfs_build(v, u);
            siz[u] += siz[v];
            if (siz[v] > siz[hson[u]])
                hson[u] = v;
        }
    }
    // 每个点的：所在链的链顶、重边优先的 dfs 序、dfs序对应的节点编号
    int tot, top[MAXN + 5], dfn[MAXN + 5], rnk[MAXN + 5];
    void dfs_div(int u, int fa)
    {
        dfn[u] = ++tot;
        rnk[tot] = u;
        if (hson[u])
        {
            top[hson[u]] = top[u];
            dfs_div(hson[u], u);
            for (int i = 0; i < e[u].size(); i++)
            {
                int v = e[u][i];
                if (v == fa || v == hson[u])
                    continue;
                top[v] = v;
                dfs_div(v, u);
            }
        }
    }
    void init(int root)
    {
        dep[root] = 1;
        fa[root] = 0;
        dfs_build(root, 0);
        tot = 0;
        top[root] = root;
        dfs_div(root, 0);
    }
    //---------操作---------
    // sum(u~v)
    int sumPath(int rt, int u, int v)
    {
        int res = 0;
        while (top[u] != top[v])
        {
            if (dep[top[u]] < dep[top[v]])
            {
                // v~top[v]
                res += ST::query_sum(rt, 1, tot, dfn[top[v]], dfn[v], 0);
                v = fa[top[v]];
            }
            else
            {
                // u~top[u]
                res += ST::query_sum(rt, 1, tot, dfn[top[u]], dfn[u], 0);
                u = fa[top[u]];
            }
        }
        if (dep[u] > dep[v])
            swap(u, v);
        res += ST::query_sum(rt, 1, tot, dfn[u], dfn[v], 0);
        return res;
    }
    int maxPath(int rt, int u, int v)
    {
        int res = 0;
        while (top[u] != top[v])
        {
            if (dep[top[u]] < dep[top[v]])
            {
                // v~top[v]
                res = max(res, ST::query_max(rt, 1, tot, dfn[top[v]], dfn[v], 0));
                v = fa[top[v]];
            }
            else
            {
                // u~top[u]
                res = max(res, ST::query_max(rt, 1, tot, dfn[top[u]], dfn[u], 0));
                u = fa[top[u]];
            }
        }
        if (dep[u] > dep[v])
            swap(u, v);
        res = max(res, ST::query_max(rt, 1, tot, dfn[u], dfn[v], 0));
        return res;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i] >> c[i]; // 评级，信仰
    }
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        T::e[u].push_back(v);
        T::e[v].push_back(u);
    }
    T::init(1);
    for (int i = 1; i <= n; i++)
    {
        if (rt[c[i]] == 0)
            rt[c[i]] = ++ST::tot;
        ST::update(rt[c[i]], 1, T::tot, T::dfn[i], T::dfn[i], w[i]);
    }
    while (m--)
    {
        string op;
        int x, y;
        cin >> op >> x >> y;
        if (op == "CC")
        {
            ST::update(rt[c[x]], 1, T::tot, T::dfn[x], T::dfn[x], -w[x]);
            c[x] = y;
            if (rt[c[x]] == 0)
                rt[c[x]] = ++ST::tot;
            ST::update(rt[c[x]], 1, T::tot, T::dfn[x], T::dfn[x], w[x]);
        }
        if (op == "CW")
        {
            ST::update(rt[c[x]], 1, T::tot, T::dfn[x], T::dfn[x], -w[x]);
            w[x] = y;
            ST::update(rt[c[x]], 1, T::tot, T::dfn[x], T::dfn[x], w[x]);
        }
        if (op == "QS")
        {
            cout << T::sumPath(rt[c[x]], x, y) << "\n";
        }
        if (op == "QM")
        {
            cout << T::maxPath(rt[c[x]], x, y) << "\n";
        }
    }
    return 0;
}

P3178 [HAOI2015]树上操作

树剖做法略，下面是非树剖做法。

线段树维护每个点到根节点路径的点权和 (dep[i]*t1[i]+t2[i])

• 操作 1 ：把某个节点 x 的点权增加 a 。
  • 整个子树（dfs序连续）都加 (0,a)
• 操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
  • 整个子树（dfs序连续）都加 (y, -(dep[x] - 1) * y)
• 操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
  • 单点查询

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
int n, m;
int a[MAXN];
vector<int> e[MAXN];
int dep[MAXN]; //节点i的深度
int siz[MAXN]; //节点i的子树大小
//dfs
int dfscnt, dfn[MAXN];
void dfs(int u, int fa)
{
    dfn[u] = ++dfscnt;
    siz[u] = 1;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        siz[u] += siz[v];
    }
}
//线段树
long long d[4 * MAXN + 5]; //前缀和
long long t1[4 * MAXN + 5], t2[4 * MAXN + 5];
//下放标记
void push_down(int now)
{
    t1[now * 2] += t1[now];
    t1[now * 2 + 1] += t1[now];
    t2[now * 2] += t2[now];
    t2[now * 2 + 1] += t2[now];
    t1[now] = t2[now] = 0;
}
//把[x,y]区间增加k1,k2
void update(int now, int l, int r, int x, int y, long long k1, long long k2)
{
    if (x <= l && r <= y)
    {
        t1[now] += k1;
        t2[now] += k2;
        return;
    }
    push_down(now);
    int mid = (l + r) / 2;
    if (x <= mid)
        update(now * 2, l, mid, x, y, k1, k2);
    if (y > mid)
        update(now * 2 + 1, mid + 1, r, x, y, k1, k2);
}
//查询 x（u的dfs序为x）
long long query(int now, int l, int r, int x, int u)
{
    if (l == r)
        return dep[u] * t1[now] + t2[now];
    push_down(now);
    int mid = (l + r) / 2;
    if (x <= mid)
        return query(now * 2, l, mid, x, u);
    return query(now * 2 + 1, mid + 1, r, x, u);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfscnt = 0;
    dep[1] = 1;
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
        update(1, 1, n, dfn[i], dfn[i] + siz[i] - 1, 0, a[i]);
    for (int i = 1; i <= m; i++)
    {
        int op, x;
        long long y;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y;
            update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, 0, y);
        }
        else if (op == 2)
        {
            cin >> x >> y;
            update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, y, -(dep[x] - 1) * y);
        }
        else if (op == 3)
        {
            cin >> x;
            cout << query(1, 1, n, dfn[x], x) << "\n";
        }
    }
    return 0;
}

P3384 【模板】重链剖分/树链剖分

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100000 + 5;
const int INF = 0x3f3f3f3f;
int n, m, r, p;
vector<int> e[MAXN];
int w[MAXN]; // 每个点的权值
//---------树剖基础---------
// 每个点的：父节点、深度、大小、重子节点
int fa[MAXN], dep[MAXN], siz[MAXN], hson[MAXN];
void dfs_build(int u, int fat)
{
    hson[u] = 0;
    siz[hson[u]] = 0;
    siz[u] = 1;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fat)
            continue;
        dep[v] = dep[u] + 1;
        fa[v] = u;
        dfs_build(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[hson[u]])
            hson[u] = v;
    }
}
// 每个点的：所在链的链顶、重边优先的 dfs 序、dfs序对应的节点编号
int tot, top[MAXN], dfn[MAXN], rnk[MAXN];
void dfs_div(int u, int fa)
{
    dfn[u] = ++tot;
    rnk[tot] = u;
    if (hson[u])
    {
        top[hson[u]] = top[u];
        dfs_div(hson[u], u);
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i];
            if (v == fa || v == hson[u])
                continue;
            top[v] = v;
            dfs_div(v, u);
        }
    }
}

//---------线段树---------
struct SegTree
{
    int sum[MAXN * 4], lazy[MAXN * 4];
    void build(int o, int l, int r)
    {
        if (l == r)
        {
            sum[o] = w[rnk[l]];
            lazy[o] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(o * 2, l, mid);
        build(o * 2 + 1, mid + 1, r);
        sum[o] = sum[o * 2] + sum[o * 2 + 1];
        sum[o] %= p;
    }
    int query_sum(int o, int l, int r, int ql, int qr)
    {
        if (l > qr || r < ql)
            return 0;
        if (ql <= l && r <= qr)
            return sum[o];
        int mid = (l + r) >> 1;
        // 下放懒标记
        if (lazy[o] != 0)
        {
            sum[o * 2] += lazy[o] * (mid - l + 1);
            sum[o * 2] %= p;
            sum[o * 2 + 1] += lazy[o] * (r - mid);
            sum[o * 2 + 1] %= p;
            lazy[o * 2] += lazy[o];
            lazy[o * 2] %= p;
            lazy[o * 2 + 1] += lazy[o];
            lazy[o * 2 + 1] %= p;
            lazy[o] = 0;
        }
        return (query_sum(o * 2, l, mid, ql, qr) +
                query_sum(o * 2 + 1, mid + 1, r, ql, qr)) % p;
    }
    // 把[x,y]区间都加k
    void add(int o, int l, int r, int x, int y, int k)
    {
        if (x <= l && r <= y)
        {
            sum[o] += k * (r - l + 1);
            sum[o] %= p;
            lazy[o] += k;
            lazy[o] %= p;
            return;
        }
        int mid = (l + r) / 2;
        // 下放懒标记
        if (lazy[o] != 0)
        {
            sum[o * 2] += lazy[o] * (mid - l + 1);
            sum[o * 2] %= p;
            sum[o * 2 + 1] += lazy[o] * (r - mid);
            sum[o * 2 + 1] %= p;
            lazy[o * 2] += lazy[o];
            lazy[o * 2] %= p;
            lazy[o * 2 + 1] += lazy[o];
            lazy[o * 2 + 1] %= p;
            lazy[o] = 0;
        }
        if (x <= mid)
            add(o * 2, l, mid, x, y, k);
        if (y > mid)
            add(o * 2 + 1, mid + 1, r, x, y, k);
        sum[o] = sum[o * 2] + sum[o * 2 + 1];
        sum[o] %= p;
    }
} st;
//---------操作---------
// u~v += x
void addPath(int u, int v, int x)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]])
        {
            // v~top[v]
            st.add(1, 1, tot, dfn[top[v]], dfn[v], x);
            v = fa[top[v]];
        }
        else
        {
            // u~top[u]
            st.add(1, 1, tot, dfn[top[u]], dfn[u], x);
            u = fa[top[u]];
        }
    }
    if (dep[u] > dep[v])
        swap(u, v);
    st.add(1, 1, tot, dfn[u], dfn[v], x);
}
// sum(u~v)
int sumPath(int u, int v)
{
    int res = 0;
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]])
        {
            // v~top[v]
            res += st.query_sum(1, 1, tot, dfn[top[v]], dfn[v]);
            res %= p;
            v = fa[top[v]];
        }
        else
        {
            // u~top[u]
            res += st.query_sum(1, 1, tot, dfn[top[u]], dfn[u]);
            res %= p;
            u = fa[top[u]];
        }
    }
    if (dep[u] > dep[v])
        swap(u, v);
    res += st.query_sum(1, 1, tot, dfn[u], dfn[v]);
    res %= p;
    return res;
}

// tree(u) += x
void addTree(int u, int x)
{
    st.add(1, 1, tot, dfn[u], dfn[u] + siz[u] - 1, x);
}
// sum(tree(u))
int sumTree(int u)
{
    return st.query_sum(1, 1, tot, dfn[u], dfn[u] + siz[u] - 1);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> r >> p;
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dep[r] = 1;
    fa[r] = 0;
    dfs_build(r, 0);
    tot = 0;
    top[r] = r;
    dfs_div(r, 0);
    st.build(1, 1, tot);
    while (m--)
    {
        int op, x, y, z;
        cin >> op;
        if (op == 1)
        {
            // x~y += z
            cin >> x >> y >> z;
            addPath(x, y, z);
        }
        if (op == 2)
        {
            // sum(x~y)
            cin >> x >> y;
            cout << sumPath(x, y) << "\n";
        }
        if (op == 3)
        {
            // 子树(x) += z
            cin >> x >> z;
            addTree(x, z);
        }
        if (op == 4)
        {
            // sum(子树(x))
            cin >> x;
            cout << sumTree(x) << "\n";
        }
    }
    return 0;
}

树剖LCA

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000 + 5;
int n, m, s;
vector<int> e[MAXN];
//每个点的：父节点、深度、大小、重子节点
int fa[MAXN], dep[MAXN], siz[MAXN], hson[MAXN];
void dfs_build(int u, int fat)
{
    hson[u] = 0;
    siz[hson[u]] = 0;
    siz[u] = 1;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fat)
            continue;
        dep[v] = dep[u] + 1;
        fa[v] = u;
        dfs_build(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[hson[u]])
            hson[u] = v;
    }
}
//每个点的：所在链的链顶、重边优先的 dfs 序、dfs序对应的节点编号
int tot, top[MAXN], dfn[MAXN], rnk[MAXN];
void dfs_div(int u, int fa)
{
    dfn[u] = ++tot;
    rnk[tot] = u;
    if (hson[u])
    {
        top[hson[u]] = top[u];
        dfs_div(hson[u], u);
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i];
            if (v == fa || v == hson[u])
                continue;
            top[v] = v;
            dfs_div(v, u);
        }
    }
}
int lca(int u, int v)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] > dep[top[v]])
            u = fa[top[u]];
        else
            v = fa[top[v]];
    }
    return dep[u] > dep[v] ? v : u;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dep[s] = 1;
    fa[s] = 0;
    dfs_build(s, 0);
    tot = 0;
    top[s] = s;
    dfs_div(s, 0);
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
    return 0;
}