树剖板子，TLE#8, 9, 10 求调qwq

讨论版上关于#8 9 10 TLE的都看了，但是我代码既没有忘记更新重儿子，也没有忘记开4倍空间，实在调不出来

附上代码链接P3384 TLE#8 9 10

// P3384
#include <bits/stdc++.h>
using std::cin,std::cout,std::vector;
//#define endl std::endl
#define endl "\n"

// 以下为线段树

#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((rtL+rtR)>>1)

int MOD,n;
std::vector<int>tree, tag;

void push_up(int rt){ tree[rt]=(tree[ls]+tree[rs])%MOD; }
void addtag(int rt,int rtL,int rtR,int d) {
    tag[rt]=(tag[rt]+d)%MOD;
    tree[rt]=(tree[rt]+1LL*d*(rtR-rtL+1))%MOD;
}

void push_down(int rt,int rtL,int rtR) {
    if(tag[rt]){
        addtag(ls,rtL,mid,tag[rt]);
        addtag(rs,mid+1,rtR,tag[rt]);
        tag[rt]=0;
    }
}

void add(int L,int R,int rt,int rtL,int rtR,int d) {
    if(L<=rtL&&rtR<=R){ addtag(rt,rtL,rtR,d); return; }
    push_down(rt,rtL,rtR);
    if(L<=mid) add(L,R,ls,rtL,mid,d);
    if(R>mid) add(L,R,rs,mid+1,rtR,d);
    push_up(rt);
}

int query(int L,int R,int rt,int rtL,int rtR) {
    if(L<=rtL&&rtR<=R) return tree[rt];
    push_down(rt,rtL,rtR);
    int res=0;
    if(L<=mid) res=(res+query(L,R,ls,rtL,mid))%MOD;
    if(R>mid) res=(res+query(L,R,rs,mid+1,rtR))%MOD;
    return res;
}
int query(int L,int R) { return query(L,R,1,1,n); }

void build(int rt,int rtL,int rtR,std::vector<int>vec) {
    tag[rt]=0;
    if(rtL==rtR){ tree[rt]=vec[rtL]; return; }
    build(ls,rtL,mid,vec); build(rs,mid+1,rtR,vec);
    push_up(rt);
}

void add(int L,int R,int d) {
    add(L,R,1,1,n,d);
}

// 以下为树剖

struct Node{
    int dep,siz,son,top,pre,id,val;
};

int m,rt;
vector<vector<int>>adj;
vector<Node>aa;
vector<int>new_aa;
void dfs1(int now,int pre) {
    aa[now].siz=1; aa[now].dep=aa[pre].dep+1; aa[now].pre=pre;
    for(auto nxt:adj[now]){
        if(nxt==pre) continue;
        dfs1(nxt,now);
        aa[now].siz+=aa[nxt].siz;
        if(!aa[now].son||aa[nxt].siz>aa[aa[now].son].siz) aa[now].son=nxt;
    }
};

int cnt=0;
void dfs2(int now,int top) {
    aa[now].id=++cnt; aa[now].top=top;
    new_aa[cnt]=aa[now].val;
    if(!aa[now].son) return;
    dfs2(aa[now].son,top);
    for(auto nxt:adj[now]) if(nxt!=aa[now].pre&&nxt!=aa[now].son) dfs2(nxt,nxt);
};

void add_range(int u,int v,int w) { // u->v +w
    while(aa[u].top!=aa[v].top){
        if(aa[aa[u].top].dep<aa[aa[v].top].dep) std::swap(u,v); // 使得u所在树链端点更深
        add(aa[aa[u].top].id,aa[u].id,w);
        u=aa[aa[u].top].pre;
    }
    if(aa[u].dep>aa[v].dep) std::swap(u,v); // 使得u节点所在树深度更浅
    add(aa[u].id,aa[v].id,w);
};

int query_range(int u,int v) {
    int res=0;
    while(aa[u].top!=aa[v].top){
        if(aa[aa[u].top].dep<aa[aa[v].top].dep) std::swap(u,v);
        res=(res+query(aa[aa[u].top].id,aa[u].id))%MOD;
        u=aa[aa[u].top].pre;
    }
    if(aa[u].dep>aa[v].dep) std::swap(u,v);
    res+=query(aa[u].id,aa[v].id);
    return res%MOD;
};

void add_tree(int rt,int w){ add(aa[rt].id,aa[rt].id+aa[rt].siz-1,w); };
int query_tree(int rt){ return query(aa[rt].id,aa[rt].id+aa[rt].siz-1)%MOD; };

int main()
{
    cin>>n>>m>>rt>>MOD;
    adj.resize(n+1); aa.resize(n+1); new_aa.resize(n+1); tree.resize(n<<2|3); tag.resize(n<<2|3);
    for(int i=1;i<=n;++i) cin>>aa[i].val;
    for(int i=1;i<n;++i){
        int u,v; cin>>u>>v;
        adj[u].emplace_back(v); adj[v].emplace_back(u);
    }

    dfs1(rt,0);
    dfs2(rt,rt);
    build(1,1,n,new_aa);
    while(m--){
        int opt,u,v,w; cin>>opt;
        switch(opt){
            case 1: cin>>u>>v>>w; add_range(u,v,w); break;
            case 2: cin>>u>>v; cout<<query_range(u,v)<<endl; break;
            case 3: cin>>u>>w; add_tree(u,w); break;
            case 4: cin>>u; cout<<query_tree(u)<<endl; break;        
        }
    }
    return 0;
}