[LCT刷题] P1501 [国家集训队]Tree II

题目思路

要求维护树上路径和，支持乘法、加法。

考虑如何使用LCT维护。首先LCT自带的反转标记仍然需要，在此基础上增加乘法标记和加法标记，然后会发现：标记无法像线段树一样用“区间长度”乘标记维护，因为LCT不具有区间长度规律。因此再记录一个$size$表示所在辅助森林中的$Splay$子树大小，那么就可以实现标记下放：

1. 先释放乘法标记：
   ( w [ x ] ∗ = v a l ) % = M O D ; ( t r e e [ x ] . s u m ∗ = v a l ) % = M O D ; ( t r e e [ x ] . a d d _ t a g ∗ = v a l ) % = M O D ; ( t r e e [ x ] . m u l _ t a g ∗ = v a l ) % = M O D ;
   (w[x]∗=val)%=MOD;(tree[x].sum∗=val)%=MOD;(tree[x].add_tag∗=val)%=MOD;(tree[x].mul_tag∗=val)%=MOD;" role="presentation" style="position: relative;">(w[x](tree[x].sum(tree[x].add_tag(tree[x].mul_tag∗=val)%=MOD;∗=val)%=MOD;∗=val)%=MOD;∗=val)%=MOD;$$\begin{array}{rl}(w[x]& \ast =val)\mathrm{\%}=MOD;\\ (tree[x].sum& \ast =val)\mathrm{\%}=MOD;\\ (tree[x].add\mathrm{\_}tag& \ast =val)\mathrm{\%}=MOD;\\ (tree[x].mul\mathrm{\_}tag& \ast =val)\mathrm{\%}=MOD;\end{array}$$
   (w[x](tree[x].sum(tree[x].add_tag(tree[x].mul_tag​∗=val)%=MOD;∗=val)%=MOD;∗=val)%=MOD;∗=val)%=MOD;​
2. 再释放加法标记：
   ( w [ x ] + = v a l ) % = M O D ; ( t r e e [ x ] . s u m + = v a l ∗ t r e e [ x ] . s i z ) % = M O D ; ( t r e e [ x ] . a d d t a g + = v a l ) % = M O D ;
   (w[x]+=val)%=MOD;(tree[x].sum+=val∗tree[x].siz)%=MOD;(tree[x].addtag+=val)%=MOD;" role="presentation" style="position: relative;">(w[x](tree[x].sum(tree[x].addtag+=val)%=MOD;+=val∗tree[x].siz)%=MOD;+=val)%=MOD;$$\begin{array}{rl}(w[x]& +=val)\mathrm{\%}=MOD;\\ (tree[x].sum& +=val\ast tree[x].siz)\mathrm{\%}=MOD;\\ (tree[x].ad{d}_{t}ag& +=val)\mathrm{\%}=MOD;\end{array}$$
   (w[x](tree[x].sum(tree[x].addt​ag​+=val)%=MOD;+=val∗tree[x].siz)%=MOD;+=val)%=MOD;​
3. 最后释放反转标记即可

对于所有的操作，首先$split$提取链，然后再对链进行操作即可。注意别抄错板子。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define elif else if
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10, MOD = 51061;

int w[N];

namespace LCT {
    struct Info{
        int sum, siz;
        int add_tag, mul_tag;
        void reset_add() { add_tag = 0; }
        void reset_mul() { mul_tag = 1; }
    } tree[N];
    int ch[N][2], f[N], tag[N];

    #define ls ch[x][0]
    #define rs ch[x][1]

    void init_tag(int n) { 
        for(int i = 1; i <= n; i++) 
            tree[i].reset_add(), tree[i].reset_mul(), tree[i].siz = 1; 
    }

    void push_up(int x) {
        tree[x].sum = (tree[ls].sum + tree[rs].sum + w[x]) % MOD;
        tree[x].siz = tree[ls].siz + tree[rs].siz + 1;
    }

    void push_reverse(int x) { swap(ls, rs), tag[x] ^= 1; }

    void push_mul(int x, int val) {
        (w[x] *= val) %= MOD;
        (tree[x].sum *= val) %= MOD;
        (tree[x].add_tag *= val) %= MOD;
        (tree[x].mul_tag *= val) %= MOD;
    }

    void push_add(int x, int val) {
        (w[x] += val) %= MOD;
        (tree[x].sum += val * tree[x].siz) %= MOD;
        (tree[x].add_tag += val) %= MOD;
    }

    void push_down(int x) {
        if(tree[x].mul_tag != 1) { 
            push_mul(ls, tree[x].mul_tag);
            push_mul(rs, tree[x].mul_tag);
            tree[x].reset_mul();
        }
        if(tree[x].add_tag) {
            push_add(ls, tree[x].add_tag);
            push_add(rs, tree[x].add_tag);
            tree[x].reset_add();
        }
        if(tag[x]) {
            if(ls) push_reverse(ls);
            if(rs) push_reverse(rs);
            tag[x] = 0;
        }
    }

    #define get(x) (ch[f[x]][1] == x)                        
    #define isRoot(x) (ch[f[x]][0] != x && ch[f[x]][1] != x)

    void rotate(int x) {
        int y = f[x], z = f[y], k = get(x);
        if(!isRoot(y)) ch[z][ch[z][1] == y] = x;
        ch[y][k] = ch[x][!k], f[ch[x][!k]] = y;
        ch[x][!k] = y, f[y] = x, f[x] = z;
        push_up(y); // push_up(x);
    }

    void update(int x) {
        if(!isRoot(x)) update(f[x]);
        push_down(x);
    }

    void splay(int x) {
        update(x);
        for(int fa = f[x]; !isRoot(x); rotate(x), fa = f[x]) {
            if(!isRoot(fa)) rotate(get(fa) == get(x) ? fa : x);
        }
        push_up(x);
    }

    int access(int x) {
        int p;
        for(p = 0; x; x = f[p = x]) splay(x), rs = p, push_up(x);
        return p;
    }

    void makeRoot(int x) { access(x), splay(x), push_reverse(x); }

    int findRoot(int x) {
        access(x), splay(x);
        while(ch[x][0]) push_down(x), x = ch[x][0];
        splay(x);
        return x;
    }

    void split(int x, int y) {
        makeRoot(x);
        access(y), splay(y);
    }

    void link(int x, int y) {
        makeRoot(x);
        if(findRoot(y) != x) f[x] = y;
    }

    void cut(int x, int y) {
        makeRoot(x);
        if(findRoot(y) == x && f[y] == x && !ch[y][0]) {
            f[y] = ch[x][1] = 0;
            push_up(x);
        }
    }
}

inline void solve(){
    int n, q; cin >> n >> q;
    LCT::init_tag(n);
    for(int i = 1; i <= n; i++) w[i] = 1;
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        LCT::link(u, v);
    }    
    while(q--) {
        char op; cin >> op;
        if(op == '+') {
            int u, v, k; cin >> u >> v >> k;
            LCT::split(u, v);
            LCT::push_add(v, k);       
        } elif(op == '-') {
            int u1, v1, u2, v2; cin >> u1 >> v1 >> u2 >> v2;
            LCT::cut(u1, v1), LCT::link(u2, v2);
        } elif(op == '*') {
            int u, v, k; cin >> u >> v >> k;
            LCT::split(u, v);
            LCT::push_mul(v, k);

        } else {
            int u, v; cin >> u >> v;
            LCT::split(u, v);
            cout << LCT::tree[v].sum << endl;
        }
    }

}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163