解题思路

算是一道 Link/Cut Tree 的模板题了，另外也可以巩固一下 Splay 的合并信息的方法。应特别注意 PushDown 相关的计算不要出错。

参考代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define lc sp[x].ch[0]
#define rc sp[x].ch[1]
#define pa sp[x].fa

const long long mod = 51061;
const int MAXN = 100001;

struct node {
    int ch[2], fa;
    long long w;
    long long sum;
    long long add, mul;
    int size;
    bool rev;
    node(): add(0), mul(1) {}
} sp[MAXN];

inline int IsRC(int x) {
    return sp[pa].ch[1] == x;
}

inline bool IsRoot(int x) {
    return sp[pa].ch[0]!=x && sp[pa].ch[1]!=x;
}

inline void PushUp(int x) {
    sp[x].sum = (sp[lc].sum + sp[rc].sum + sp[x].w) % mod;    // 合并 sum 信息
    sp[x].size = sp[lc].size + sp[rc].size + 1;    // 合并 size 信息
}

inline void Reverse(int x) {
    sp[x].rev ^= 1;
    swap(lc, rc);
}

inline void Update(int x, long long add_v, long long mul_v){
    sp[x].add = (sp[x].add*mul_v + add_v) % mod;
    sp[x].mul = (sp[x].mul*mul_v) % mod;
    sp[x].w = (sp[x].w*mul_v + add_v) % mod;
    sp[x].sum = (sp[x].sum*mul_v + add_v*sp[x].size) % mod;
}

inline void PushDown(int x) {
    if(sp[x].rev) {
        if(lc) Reverse(lc);
        if(rc) Reverse(rc);
        sp[x].rev = false;
    }
    if(sp[x].add || sp[x].mul!=1){
        Update(lc, sp[x].add, sp[x].mul);
        Update(rc, sp[x].add, sp[x].mul);
        sp[x].add = 0;
        sp[x].mul = 1;
    }
}

void PD(int x) {
    if(!IsRoot(x)) PD(pa);
    PushDown(x);
}

inline void Rotate(int x) {
    int f = sp[x].fa, g = sp[f].fa, c = IsRC(x);
    if(!IsRoot(f)) sp[g].ch[IsRC(f)] = x;
    sp[x].fa = g;
    sp[f].ch[c] = sp[x].ch[c^1];
    sp[sp[f].ch[c]].fa = f;
    sp[x].ch[c^1] = f;
    sp[f].fa = x;
    PushUp(f);
    PushUp(x);
}

inline void Splay(int x) {
    PD(x);
    for(; !IsRoot(x); Rotate(x)) {
        if(!IsRoot(pa)) Rotate(IsRC(pa)==IsRC(x) ? pa : x);
    }
}

// 访问 x
inline void Access(int x) {
    for(int y=0; x; y=x, x=pa) {
        Splay(x);
        rc = y;
        PushUp(x);
    }
}

// 查找 x 所在辅助树的根
inline int FindRoot(int x) {
    Access(x);
    Splay(x);
    while(lc) {
        // PushDown(x);
        x = lc;
    }
    return x;
}

// 使 x 成为根（注意并非所在辅助树的根）
inline void MakeRoot(int x) {
    Access(x);
    Splay(x);
    Reverse(x);
}

// 连接 x 和 y
inline void Link(int x, int y) {
    MakeRoot(x);
    sp[x].fa = y;
}

// 将 x 及其父结点切断
inline void CutFa(int x) {
    Access(x);
    Splay(x);
    sp[x].ch[0] = sp[sp[x].ch[0]].fa = 0;
    PushUp(x);
}

// 将边 x - y 切断
inline void Cut(int x, int y) {
    MakeRoot(x);
    CutFa(y);
}

// 使用 x 到 y 的路径，为相关操作做准备
inline void Use(int x, int y) {
    MakeRoot(x);
    Access(y);
    Splay(y);
}

// 将下标为 x 处的值修改为 y
inline int Change(int x, int y) {
    // MakeRoot(x);
    // sp[x].w = y;
    // PushUp(x);
    sp[x].w = y;
    Splay(x);
}

// 修改 x 的父结点为 y
inline int ChangeFa(int x, int y) {
    CutFa(x);
    sp[x].fa = y;
}

// 查询 x 到 y 路径上的和
inline int QuerySum(int x, int y) {
    Use(x, y);
    return sp[y].sum;
}

// 查询 x 到根的路径上的结点个数（距离）
inline int QuerySize(int x) {
    Access(x);
    Splay(x);
    // return sp[x].size;    // 包括自己的结点个数
    return sp[sp[x].ch[0]].size;    // 不包括自己的结点个数
}

int main(int argc, char const *argv[]) {
    int n, q, u, v;
    long long c;
    char op[2];
    scanf("%d %d", &n, &q);
    for(int i=0; i<n-1; ++i) {
        scanf("%d %d", &u, &v);
        Link(u, v);
    }
    for(int i=1; i<=n; ++i) {
        sp[i].w = 1;
    }
    while(q--) {
        scanf("%s", op);
        if(op[0] == '+') {
            scanf("%d %d %lld", &u, &v, &c);
            Use(u, v);
            Update(v, c, 1);
        }
        if(op[0] == '-') {
            scanf("%d %d", &u, &v);
            Cut(u, v);
            scanf("%d %d", &u, &v);
            Link(u, v);
        }
        if(op[0] == '*') {
            scanf("%d %d %lld", &u, &v, &c);
            Use(u, v);
            Update(v, 0, c);
        }
        if(op[0] == '/') {
            scanf("%d %d", &u, &v);
            printf("%lld\n", QuerySum(u, v));
        }
    }
    
    return 0;
}