P3384 【模板】轻重链剖分/树链剖分
  • Problem

    • 【模板】轻重链剖分/树链剖分

      • 题目描述

        如题,已知一棵包含 N 个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作:

        • 1 x y z,表示将树从 xy 结点最短路径上所有节点的值都加上 z

        • 2 x y,表示求树从 xy 结点最短路径上所有节点的值之和。

        • 3 x z,表示将以 x 为根节点的子树内所有节点值都加上 z

        • 4 x 表示求以 x 为根节点的子树内所有节点值之和

      • 输入格式

        第一行包含 4 个正整数 N,M,R,P,分别表示树的结点个数、操作个数、根节点序号和取模数(即所有的输出结果均对此取模)。

        接下来一行包含 N 个非负整数,分别依次表示各个节点上初始的数值。

        接下来 N-1 行每行包含两个整数 x,y,表示点 x 和点 y 之间连有一条边(保证无环且连通)。

        接下来 M 行每行包含若干个正整数,每行表示一个操作。

  • Code

    #include <bits/stdc++.h>
    using namespace std;
    #define cint const int&
    #define ls (x << 1)
    #define rs (ls | 1)
    #define mids(l,r) const int mid = l+r>>1
    const int maxn = 1e5 + 10;
    int cnt, head[maxn], dfcnt, n, m, r, p, x, y, z;
    namespace SegMentTree {
        struct segment {
            int seg, tag;
        }seg[maxn << 2ll];
    #define pushdown(x,ml,mr)\
        mids(ml, mr);\
        if(seg[x].tag){\
            seg[ls].seg += seg[x].tag * (mid - ml + 1);\
            seg[rs].seg += seg[x].tag * (mr - mid);\
            seg[ls].tag += seg[x].tag;\
            seg[rs].tag += seg[x].tag;\
            seg[x].tag = 0;\
        }
    #define pushup seg[x].seg = (seg[ls].seg + seg[rs].seg)%p
        int w[maxn], a[maxn], dfn[maxn], dep[maxn], siz[maxn], top[maxn], fa[maxn], son[maxn];
        void build(cint x, cint l, cint r) {
            if (l == r)
                return void(seg[x] = { .seg = a[l],.tag = 0 });
            mids(l, r);
            build(ls, l, mid), build(rs, mid + 1, r);
            pushup;
        }
        void add(cint x, cint ml, cint mr, cint ql, cint qr, cint v) {
            if (ql <= ml && mr <= qr)
                return
                (seg[x].seg += (mr - ml + 1) * v) %= p,
                (seg[x].tag += v) %= p, void(0);
            pushdown(x, ml, mr);
            if (mid >= ql) add(ls, ml, mid, ql, qr, v);
            if (mid < qr) add(rs, mid + 1, mr, ql, qr, v);
            pushup;
        }
        int get(cint x, cint ml, cint mr, cint ql, cint qr) {
            if (ql <= ml && mr <= qr) return seg[x].seg;
            pushdown(x, ml, mr);
            int ans = 0;
            if (mid >= ql) (ans += get(ls, ml, mid, ql, qr)) %= p;
            if (mid < qr) (ans += get(rs, mid + 1, mr, ql, qr)) %= p;
            return ans;
        }
    }using namespace SegMentTree;
    namespace Group {
        struct { int nxt, v; }edge[maxn << 1];
        inline void addedge(cint u, cint v) {
            edge[++cnt] = { .nxt = head[u],.v = v };
            head[u] = cnt;
        }
    }using namespace Group;
    namespace hld {
        void dfs1(cint x, cint f) {
            fa[x] = f;
            siz[x] = 1;
            dep[x] = dep[f] + 1;
            int maxsiz = 0;
            for (auto i = head[x]; i; i = edge[i].nxt) {
                const auto v = edge[i].v;
                if (v == f) continue;
                dfs1(v, x);
                if (siz[v] > maxsiz)
                    maxsiz = siz[v], son[x] = v;
                siz[x] += siz[v];
            }
        }
        void dfs2(cint u, cint tp) {
            dfn[u] = ++dfcnt;
            a[dfcnt] = w[u] % p;
            top[u] = tp;
            if (!son[u]) return;
            dfs2(son[u], tp);
            for (auto i = head[u]; i; i = edge[i].nxt) {
                const int v = edge[i].v;
                if (v == fa[u] || v == son[u]) continue;
                dfs2(v, v);
            }
        }
        inline void addpath(int u, int v, cint w) {
            while (top[u] != top[v]) {
                if (dep[top[u]] < dep[top[v]]) swap(u, v);
                add(1, 1, n, dfn[top[u]], dfn[u], w);
                u = fa[top[u]];
            }
            if (dep[u] > dep[v]) swap(u, v);
            add(1, 1, n, dfn[u], dfn[v], w);
        }
        inline int getpath(int u, int v) {
            int ans = 0;
            while (top[u] != top[v]) {
                if (dep[top[u]] < dep[top[v]]) swap(u, v);
                (ans += get(1, 1, n, dfn[top[u]], dfn[u])) %= p;
                u = fa[top[u]];
            }
            if (dep[u] > dep[v]) swap(u, v);
            ans += get(1, 1, n, dfn[u], dfn[v]);
            return ans % p;
        }
        inline void addson(cint u, cint v) { add(1, 1, n, dfn[u], dfn[u] + siz[u] - 1, v); }
        inline int getson(cint u) { return get(1, 1, n, dfn[u], dfn[u] + siz[u] - 1); }
    }using namespace hld;
    char opt;
    signed main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cin >> n >> m >> r >> p;
        for (int i = 1; i <= n; ++i)
            cin >> w[i];
        for (int i = 1; i < n; ++i) {
            cin >> x >> y;
            addedge(x, y),addedge(y, x);
        }
        dfs1(r, 0);
        dfs2(r, r);
        build(1, 1, n);
        while (m--)
            switch (cin >> opt;opt) {
            case '1':
                cin >> x >> y >> z;
                addpath(x, y, z % p);
                break;
            case '2':
                cin >> x >> y;
                cout << getpath(x, y) << '\n';
                break;
            case '3':
                cin >> x >> y;
                addson(x, y % p);
                break;
            default:
                cin >> x;
                cout << getson(x) << '\n';
                break;
            }
    }
    
  • Tip

    • 线段树

      ls or rs
      others….

    • dfs

      use dfn[u] not u

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇