[洛谷P1501][国家集训队]Tree II

#include <cstdio>

#define maxn 100010

#define lc(rt) son[rt][0]

#define rc(rt) son[rt][1]

const long long mod = 51061;

int n, q;

long long V[maxn], s[maxn], tg[maxn], M[maxn], A[maxn];

int son[maxn][2], fa[maxn], sz[maxn];

inline void swap(int &a, int &b) {a ^= b ^= a ^= b;}

inline void swap(int x) {

    swap(lc(x), rc(x));

    tg[lc(x)] ^= 1, tg[rc(x)] ^= 1, tg[x] = 0;

}

inline void setmul(int x) {

    long long &tmp = M[x];

    M[lc(x)] = M[lc(x)] * tmp % mod, M[rc(x)] = M[rc(x)] * tmp % mod;

    A[lc(x)] = A[lc(x)] * tmp % mod, A[rc(x)] = A[rc(x)] * tmp % mod;

    V[lc(x)] = V[lc(x)] * tmp % mod, V[rc(x)] = V[rc(x)] * tmp % mod;

    s[lc(x)] = s[lc(x)] * tmp % mod, s[rc(x)] = s[rc(x)] * tmp % mod;

    tmp = 1;

}

inline void setadd(int x) {

    long long &tmp = A[x];

    A[lc(x)] = (A[lc(x)] + tmp) % mod, A[rc(x)] = (A[rc(x)] + tmp) % mod;

    V[lc(x)] = (V[lc(x)] + tmp) % mod, V[rc(x)] = (V[rc(x)] + tmp) % mod;

    s[lc(x)] = (s[lc(x)] + sz[lc(x)] * tmp) % mod, s[rc(x)] = (s[rc(x)] + sz[rc(x)] * tmp) % mod;

    tmp = 0;

}

inline void pushdown(int x) {

    if (tg[x]) swap(x);

    if (M[x] != 1) setmul(x);

    if (A[x]) setadd(x);

}

inline void update(int x) {

    s[x] = (s[lc(x)] + s[rc(x)] + V[x]) % mod;

    sz[x] = sz[lc(x)] + sz[rc(x)] + 1;

}

inline int get(int x) {return rc(fa[x]) == x;}

inline bool isrt(int x) {return lc(fa[x]) != x && rc(fa[x]) != x;}

inline void rotate(int x) {

    int y = fa[x], z = fa[y], b = get(x);

    if (!isrt(y)) son[z][get(y)] = x;

    fa[son[y][b] = son[x][!b]] = y; son[x][!b] = y;

    fa[y] = x, fa[x] = z;

    update(y), update(x);

}

int S[maxn], top;

inline void splay(int x) {

    S[top = 1] = x;

    for (int y = x; !isrt(y); S[++top] = y = fa[y]);

    for (; top; top--) pushdown(S[top]);

    for (; !isrt(x); rotate(x)) if (!isrt(fa[x]))

        get(x) ^ get(fa[x]) ? rotate(x) : rotate(fa[x]);

    update(x);

}

inline void access(int x) {for (int t = 0; x; rc(x) = t, t = x, x = fa[x]) splay(x);}

inline void mkrt(int x) {access(x), splay(x), tg[x] ^= 1;}

inline void link(int x, int y) {mkrt(x), fa[x] = y;}

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

inline void cut(int x, int y) {split(x, y), lc(y) = fa[x] = 0;}

inline void add(int x, int y, long long num) {

    split(x, y);

    A[y] = (A[y] + num) % mod;

    V[y] = (V[y] + num) % mod;

    s[y] = (s[y] + sz[y] * num) % mod;

}

inline void mul(int x, int y, long long num) {

    split(x, y);

    A[y] = A[y] * num % mod;

    V[y] = V[y] * num % mod;

    M[y] = M[y] * num % mod;

    s[y] = s[y] * num % mod;

}

inline long long query(int x, int y) {

    split(x, y);

    pushdown(y);

    return s[y];

}

int main() {

    scanf("%d%d", &n, &q);

    for (int i = 1; i <= n; i++) V[i] = 1, M[i] = 1, s[i] = 1;

    for (int i = 1; i < n; i++) {

        int a, b;

        scanf("%d%d", &a, &b);

        link(a, b);

    }

    while (q --> 0) {

        int x, y;

        long long z;

        char op[10];

        scanf("%s%d%d", op, &x, &y);

        switch (*op) {

            case '+': scanf("%lld", &z), add(x, y, z); break;

            case '-': cut(x, y), scanf("%d%d", &x, &y), link(x, y); break;

            case '*': scanf("%lld", &z), mul(x, y, z); break;

            case '/': printf("%lld\n", query(x, y));

        }

    }

    return 0;

}