关于我之前写的阴间指针树剖模板

更好的阅读体验戳此进入

（建议您从上方链接进入我的个人网站查看此 Blog，在 Luogu 中图片会被墙掉，部分 Markdown 也会失效）

rt，树剖比较简单就不具体写做法了，总之就是之前实现的一个及其阴间的指针版树剖模板，然后一直 RE 没调出来，今天想着重调一下，结果看了一遍就找到问题了，判断深度时直接判断了节点的深度而非节点所在链顶的深度。

该说不说这玩意拿指针是真难写，正常的树剖默认下标为 $0$$0$，调用默认下标获得的值也是 $0$$0$，然而指针版全都是 RE。

xxxxxxxxxx
190
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define siz(p) (p ? p->siz : 0)
9

10
using namespace std;
11

12
mt19937 rnd(random_device{}());
13
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
14

15
typedef unsigned int uint;
16
typedef unsigned long long unll;
17
typedef long long ll;
18

19
struct Node;
20

21
struct Edge{
22
    Edge* nxt;
23
    Node* to;
24
    void* operator new(size_t);
25
    Edge(Edge* nxt, Node* to):nxt(nxt), to(to){;}
26
    Edge(void) = default;
27
}eData[210000];
28
void* Edge::operator new(size_t){static Edge* P = eData; return ++P;}
29
int N, M, R, MOD;
30

31
struct Node{
32
    #define dep(p) (p ? p->dep : 0)
33
    int val;
34
    int dfn;
35
    int dep;
36
    int siz;
37
    Node* fa;
38
    Node* top;
39
    Node* hson;
40
    Edge* head;
41
    Node(int val):val(val){;}
42
    Node(void) = default;
43
    void* operator new(size_t);
44
}nData[110000];
45
void* Node::operator new(size_t){static Node* P = nData; return ++P;}
46
Node* tr[110000];
47
Node* idx[110000];
48

49
template<typename T = int>
50
inline T read(void);
51

52
void dfs_pretreat(Node* p, Node* fa){
53
    p->fa = fa;
54
    p->dep = dep(p->fa) + 1;
55
    p->siz = 1;
56
    for(auto i = p->head; i; i = i->nxt){
57
        if(SON == fa)continue;
58
        // printf("%d %d\n", SON->val, fa ? fa->val : 0);
59
        dfs_pretreat(SON, p);
60
        p->siz += SON->siz;
61
        if(siz(SON) > siz(p->hson))p->hson = SON;
62
    }
63
}
64
void dfs_build(Node* p, Node* top){
65
    static int dfn(0);
66
    p->dfn = ++dfn;
67
    idx[p->dfn] = p;
68
    p->top = top;
69
    if(p->hson)dfs_build(p->hson, top);
70
    for(auto i = p->head; i; i = i->nxt){
71
        if(SON != p->hson && SON != p->fa){
72
            dfs_build(SON, SON);
73
        }
74
    }
75
}
76
class SegTree{
77
private:
78
    ll st[110000 << 2], lt[110000 << 2];
79
    #define LS (p << 1)
80
    #define RS ((p << 1) + 1)
81
    #define MID ((gl + gr) >> 1)
82
    #define SIZ (gr - gl + 1)
83
    #define SIZL (MID - gl + 1)
84
    #define SIZR (gr - MID - 1 + 1)
85
public:
86
    void Pushdown(int p, int gl, int gr){
87
        st[LS] = (st[LS] + SIZL * lt[p] % MOD) % MOD,
88
        st[RS] = (st[RS] + SIZR * lt[p] % MOD) % MOD,
89
        lt[LS] = (lt[LS] + lt[p]) % MOD, lt[RS] = (lt[RS] + lt[p]) % MOD;
90
        lt[p] = 0;
91
    }
92
    void Pushup(int p){
93
        st[p] = (st[LS] + st[RS]) % MOD;
94
    }
95
    void Build(int p = 1, int gl = 1, int gr = N){
96
        if(gl == gr){
97
            // printf("st[%d] <- idx[%d] = %d\n", p, gl, idx[gl]->val);
98
            return (void)(st[p] = idx[gl = gr]->val);
99
        }
100
        Build(LS, gl, MID);
101
        Build(RS, MID + 1, gr);
102
        Pushup(p);
103
    }
104
    void Modify(int l, int r, int val, int p = 1, int gl = 1, int gr = N){
105
        if(l <= gl && gr <= r)return (void)(st[p] = (st[p] + SIZ * val) % MOD, lt[p] = (lt[p] + val) % MOD);
106
        if(lt[p])Pushdown(p, gl, gr);
107
        if(l <= MID)Modify(l, r, val, LS, gl, MID);
108
        if(r >= MID + 1)Modify(l, r, val, RS, MID + 1, gr);
109
        Pushup(p);
110
    }
111
    ll Query(int l, int r, int p = 1, int gl = 1, int gr = N){
112
        if(l <= gl && gr <= r)return st[p];
113
        if(lt[p])Pushdown(p, gl, gr);
114
        return(
115
            (l <= MID ? Query(l, r, LS, gl, MID) : 0) +
116
            (r >= MID + 1 ? Query(l, r, RS, MID + 1, gr) : 0)
117
        ) % MOD;
118
    }
119
    void Desc(void){
120
        int cur(0);
121
        for(int i = 1; i <= 1 << 4; i <<= 1)
122
            for(int j = 1; j <= i; ++j)printf("%lld%c", st[++cur], j == i ? '\n' : ' ');
123
    }
124
}st;
125

126
#define top(p) (p ? p->top : npt)
127
#define dfn(p) (p ? p->dfn : 0)
128

129
void ModifyTree(Node* from, Node* to, int val){
130
    while(top(from) != top(to)){
131
        if(dep(top(from)) < dep(top(to)))swap(from, to);
132
        st.Modify(dfn(from->top), dfn(from), val);
133
        from = from ? from->top->fa : npt;
134
    }
135
    if(dep(from) < dep(to))swap(from, to);
136
    st.Modify(dfn(to), dfn(from), val);
137
}
138
ll QueryTree(Node* from, Node* to){
139
    ll ret(0);
140
    while(top(from) != top(to)){
141
        if(dep(top(from)) < dep(top(to)))swap(from, to);
142
        ret = (ret + st.Query(dfn(from->top), dfn(from))) % MOD;
143
        from = from ? from->top->fa : npt;
144
    }
145
    if(dep(from) < dep(to))swap(from, to);
146
    ret = (ret + st.Query(dfn(to), dfn(from))) % MOD;
147
    return ret;
148
}
149

150
int main(){
151
    // freopen("in.txt", "r", stdin);
152
    N = read(), M = read(), R = read(), MOD = read();
153
    for(int i = 1; i <= N; ++i)tr[i] = new Node(read());
154
    for(int i = 1; i <= N - 1; ++i){
155
        int f = read(), t = read();
156
        tr[f]->head = new Edge(tr[f]->head, tr[t]);
157
        tr[t]->head = new Edge(tr[t]->head, tr[f]);
158
    }
159
    dfs_pretreat(tr[R], npt);
160
    dfs_build(tr[R], tr[R]);
161
    st.Build();
162
    while(M--){
163
        int opt = read();
164
        switch(opt){
165
            case 1:{int f = read(), t = read(), val = read() % MOD; ModifyTree(tr[f], tr[t], val);break;}
166
            case 2:{int f = read(), t = read();  printf("%lld\n", QueryTree(tr[f], tr[t])); break;}
167
            case 3:{int x = read(), val = read() % MOD; st.Modify(tr[x]->dfn, tr[x]->dfn + tr[x]->siz - 1, val);break;}
168
            case 4:{int x = read(); printf("%lld\n", st.Query(tr[x]->dfn, tr[x]->dfn + tr[x]->siz - 1)); break;}
169
        }
170
    }
171

172
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
173
    return 0;
174
}
175

176
template<typename T>
177
inline T read(void){
178
    T ret(0);
179
    short flag(1);
180
    char c = getchar();
181
    while(c != '-' && !isdigit(c))c = getchar();
182
    if(c == '-')flag = -1, c = getchar();
183
    while(isdigit(c)){
184
        ret *= 10;
185
        ret += int(c - '0');
186
        c = getchar();
187
    }
188
    ret *= flag;
189
    return ret;
190
}

UPD

update-2022_10_13 初稿