https://www.luogu.com.cn/problem/P3384
$rt$

#include <cstdio>
#include <vector>
#include <utility>
#define uint unsigned long long
#define sint long long
const int maxLevel = 18;
struct Position{
    int level, pos;
};

struct node{
    uint val, tag;
};
std::vector <node> tree[maxLevel + 1];
int leftLimit(Position k){
    return k.pos << (maxLevel - k.level);
}
int rightLimit(Position k){
    return ((k.pos + 1) << (maxLevel - k.level)) - 1;
}
void pushUp(Position k){
    if(k.level < maxLevel){
        tree[k.level][k.pos].val = tree[k.level + 1][k.pos << 1].val + tree[k.level + 1][k.pos << 1 | 1].val;
    } 
}
void renew(Position k, uint value){
    tree[k.level][k.pos].val += value << (maxLevel - k.level);
    tree[k.level][k.pos].tag += value;
}
void pushDown(Position k){
    if(k.level < maxLevel){
        renew({k.level + 1, k.pos << 1}, tree[k.level][k.pos].tag);
        renew({k.level + 1, k.pos << 1 | 1}, tree[k.level][k.pos].tag);
        tree[k.level][k.pos].tag = 0;
    }
}
void build(){
    for(int i = 0; i <= maxLevel; i++) tree[i].resize(1 << i);
}
uint query(int leftPos, int rightPos, Position pre = {0, 0}){
    const int ll = leftLimit(pre), rl = rightLimit(pre);
    if(ll > rightPos || rl < leftPos) return 0;
    if(leftPos <= ll && rl <= rightPos) return tree[pre.level][pre.pos].val; 
    pushDown(pre);
    uint result = 0;
    const int mid = (ll + rl) >> 1;
    if(leftPos <= mid) result += query(leftPos, rightPos, Position({pre.level + 1, pre.pos << 1}));
    if(rightPos > mid) result += query(leftPos, rightPos, Position({pre.level + 1, pre.pos << 1 | 1}));
    return result;
}
void update(int leftPos, int rightPos, int value, Position pre = {0, 0}){ 
    if(pre.level <= maxLevel){
        const int ll = leftLimit(pre), rl = rightLimit(pre);
        if(leftPos <= ll && rl <= rightPos){
            renew(pre, value);
            return;
        }
        const int mid = (ll + rl) >> 1;
        pushDown(pre);
        if(leftPos <= mid) update(leftPos, rightPos, value, Position({pre.level + 1, pre.pos << 1}));
        if(rightPos >= mid + 1) update(leftPos, rightPos, value, Position({pre.level + 1, pre.pos << 1 | 1}));        
        pushUp(pre);
    }
}
const int maxn = 1e5 + 5;
int mod;
std::vector <int> graph[maxn];
int time_ = 1;
int cntNode[maxn], heavySonPos[maxn], fatherPos[maxn], top[maxn], dfsOrder[maxn], dfsPos[maxn], depth[maxn];
void dfs1(int pre, int father = 0){
    fatherPos[pre] = father;
    depth[pre] = depth[father] + 1;
    cntNode[pre] = 1;
    for(int i = 0; i < graph[pre].size(); i++){
        if(graph[pre][i] != father){
            dfs1(graph[pre][i], pre);
            cntNode[pre] += cntNode[graph[pre][i]];
            if(cntNode[heavySonPos[pre]] < cntNode[graph[pre][i]]) heavySonPos[pre] = graph[pre][i];
        }
    }  
}
void dfs2(int pre, int thisTop){
    top[pre] = thisTop;
    dfsOrder[pre] = time_;
    dfsPos[time_] = pre;
    time_ ++;
    if(heavySonPos[pre]) dfs2(heavySonPos[pre], thisTop);
    for(int i = 0; i < graph[pre].size(); i++){
        if(graph[pre][i] != fatherPos[pre] && graph[pre][i] != heavySonPos[pre]){
            dfs2(graph[pre][i], pre);
        }
    }  
}
void addChain(int u, int v, int value){
    while(top[u] != top[v]){
        if(dfsOrder[u] > dfsOrder[v]) std::swap(u, v);
        update(dfsOrder[top[v]], dfsOrder[v], value);
        v = fatherPos[top[v]];
    }
    if(dfsOrder[u] > dfsOrder[v]) std::swap(u, v);    
    update(dfsOrder[u], dfsOrder[v], value);
}
uint getSumChain(int u, int v){
    uint result = 0;
    while(top[u] != top[v]){
        if(dfsOrder[u] > dfsOrder[v]) std::swap(u, v);
        result += query(dfsOrder[top[v]], dfsOrder[v]);
        v = fatherPos[top[v]];
    }
    if(dfsOrder[u] > dfsOrder[v]) std::swap(u, v);
    result += query(dfsOrder[u], dfsOrder[v]);
    return result;
}
void addSubtree(int pos, int value){
    update(dfsOrder[pos], dfsOrder[pos] + cntNode[pos] - 1, value);
}
uint getSumSubtree(int pos){
    return query(dfsOrder[pos], dfsOrder[pos] + cntNode[pos] - 1);
}
int main()
{
    build();
    int numNode, numOper, rootPos;
    scanf("%d %d %d %d", &numNode, &numOper, &rootPos, &mod);
    for(int i = 1; i <= numNode; i++){
        int num;
        scanf("%d", &num);
        update(i, i, num);
    }
    for(int i = 1; i < numNode; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs1(rootPos);
    dfs2(rootPos, rootPos);
    for(int i = 0; i < numOper; i++){
        int op;
        scanf("%d", &op);
        if(op == 1){
            int u, v, value;
            scanf("%d %d %d", &u, &v, &value);
            addChain(u, v, value);
        }
        if(op == 2){
            int u, v;
            scanf("%d %d", &u, &v);
            printf("%llu\n", getSumChain(u, v) % mod);
        }
        if(op == 3){
            int u, value;
            scanf("%d %d", &u, &value);
            addSubtree(u, value);
        }
        if(op == 4){
            int u;
            scanf("%d", &u);
            printf("%llu\n", getSumSubtree(u) % mod);
        }
    }
    return 0;
}

没过样例，但是不知道哪里出了问题
求条
玄 $3$ 关