• + 0 comments

    using namespace std; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; typedef vector vl; typedef pair pll; typedef vector > vpll; typedef vector vs; typedef long double ld; template inline void amin(T &x, U y) { if(y < x) x = y; } template inline void amax(T &x, U y) { if(x < y) x = y; }

    struct To { typedef int Vertex; Vertex to; To() { } To(Vertex to_): to(to_) { } };

    template struct StaticGraph { typedef To_ To; typedef typename To::Vertex Vertex; typedef std::pair Edge; typedef const To *const_iterator;

    void init(int n_, const std::vector<Edge> &edges) {
        n = n_; int m = edges.size();
        tos.resize(m+1); offsets.resize(n+1);
        for(int e = 0; e < m; e ++) offsets[edges[e].first] ++;
        for(int v = 1; v <= n_; v ++) offsets[v] += offsets[v-1];
        for(int e = 0; e < m; e ++)
            tos[-- offsets[edges[e].first]] = edges[e].second;
    }
    int numVertices() const { return n; }
    int numEdges() const { return tos.size() - 1; }
    
    inline const_iterator edgesBegin(int v) const { return &tos[offsets[v]]; }
    inline const_iterator edgesEnd(int v) const { return &tos[offsets[v+1]]; }
    

    private: int n; std::vector tos; std::vector offsets; };

    class SchieberVishkinLCA { public: typedef StaticGraph Graph; typedef unsigned Word; typedef Graph::Vertex Vertex; private:

    static inline Word lowestOneBit(Word v) {
        return v & (~v+1);
    }
    static inline Word highestOneBitMask(Word v) {
        v |= v >> 1;
        v |= v >> 2;
        v |= v >> 4;
        v |= v >> 8;
        v |= v >> 16;
        return v >> 1;
    }
    
    std::vector<Word> indices;            //Vertex -> index
    std::vector<Word> maxHIndices;        //Vertex -> index
    std::vector<Word> ancestorHeights;    //Vertex -> Word
    std::vector<Vertex> pathParents;    //index-1 -> Vertex
    

    public: //g????????????? void build(const Graph &g, Vertex root) { return build(g, std::vector(1, root)); } void build(const Graph &g, const std::vector &roots) { int N = g.numVertices();

        ancestorHeights.resize(N);
        std::vector<Vertex> parents(N);
        maxHIndices.resize(N);
        std::vector<Vertex> vertices; vertices.reserve(N);
        indices.resize(N);
    
        //inorder traversal
        Word currentIndex = 1;
        for(int ri = 0; ri < (int)roots.size(); ri ++) {
            Vertex root = roots[ri];
            parents[root] = root;    //???????
            vertices.push_back(root);
        }
        while(!vertices.empty()) {
            Vertex v = vertices.back(); vertices.pop_back();
            indices[v] = currentIndex ++;
            for(const Graph::To *it = g.edgesBegin(v); it != g.edgesEnd(v); ++ it) {
                parents[it->to] = v;
                vertices.push_back(it->to);
            }
        }
    
        //BFS (???????????????)
        int head = 0, tail = roots.size();
        vertices.resize(N);
        for(int ri = 0; ri < (int)roots.size(); ri ++)
            vertices[ri] = roots[ri];
        while(head != tail) {
            Vertex v = vertices[head ++];
            for(const Graph::To *it = g.edgesBegin(v); it != g.edgesEnd(v); ++ it)
                vertices[tail ++] = it->to;
        }
    
        //?????
        for(std::vector<Vertex>::const_iterator it = vertices.begin(); it != vertices.end(); ++ it)
            maxHIndices[*it] = indices[*it];
        for(std::vector<Vertex>::const_reverse_iterator it = vertices.rbegin(); it != vertices.rend(); ++ it) {
            Vertex v = *it, parent = parents[v];
            if(lowestOneBit(maxHIndices[parent]) < lowestOneBit(maxHIndices[v]))
                maxHIndices[parent] = maxHIndices[v];
        }
    
        //A????
        for(int ri = 0; ri < (int)roots.size(); ri ++) {
            Vertex root = roots[ri];
            ancestorHeights[root] = 0;
        }
        for(std::vector<Vertex>::const_iterator it = vertices.begin(); it != vertices.end(); ++ it) {
            Vertex v = *it;
            ancestorHeights[v] = ancestorHeights[parents[v]] | lowestOneBit(maxHIndices[v]);
        }
    
        pathParents.swap(parents);    //???????
        for(int ri = 0; ri < (int)roots.size(); ri ++) {
            Vertex root = roots[ri];
            pathParents[indices[root]-1] = root;
        }
        for(std::vector<Vertex>::const_iterator it = vertices.begin(); it != vertices.end(); ++ it) {
            Vertex v = *it;
            for(const Graph::To *jt = g.edgesBegin(v); jt != g.edgesEnd(v); ++ jt) {
                if(maxHIndices[v] != maxHIndices[jt->to])
                    pathParents[indices[jt->to]-1] = v;
                else
                    pathParents[indices[jt->to]-1] = pathParents[indices[v]-1];
            }
        }
    }
    
    Vertex query(Vertex v, Vertex u) const {
        //binary tree???LCA???????
        Word Iv = maxHIndices[v], Iu = maxHIndices[u];
        Word hIv = lowestOneBit(Iv), hIu = lowestOneBit(Iu);
        Word hbMask = highestOneBitMask((Iv ^ Iu) | hIv | hIu);
        Word j = lowestOneBit(ancestorHeights[v] & ancestorHeights[u] & ~hbMask);
        //j = hI(lca(v,u)) ??? (????hI(x) = 2^(complete binary tree???I(x)???), I(x) = maxHIndices[x])
        //(hI(lca(v,u)) = j)?hI(v)?hI(u)????????????????????????…
        Vertex x, y;
        if(j == hIv) x = v;
        else {            //lca?v????????
            Word kMask = highestOneBitMask(ancestorHeights[v] & (j-1));    //v?????j???????????????????
            x = pathParents[(indices[v] & ~kMask | (kMask+1))-1];    //indices[v]?k???????????
        }
        if(j == hIu) y = u;
        else {            //lca?u????????
            Word kMask = highestOneBitMask(ancestorHeights[u] & (j-1));    //u?????j???????????????????
            y = pathParents[(indices[u] & ~kMask | (kMask+1))-1];    //indices[u]?k???????????
        }
        return indices[x] < indices[y] ? x : y;    //in-order????????????????????
    }
    

    };

    template struct ModInt { static const int Mod = MOD; unsigned x; ModInt(): x(0) { } ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; } ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; } int get() const { return (int)x; }

    ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    
    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
    

    }; typedef ModInt<1000000007> mint;

    struct Val { bool sign; mint x; int depth; Val() { } Val(bool sign_, mint x_, int depth_): sign(sign_), x(x_), depth(depth_) { } };

    struct Sum { mint signedSum, signedDepthSum, signedCount; Sum(): signedSum(0), signedDepthSum(0), signedCount(0) { } Sum(const Val &val, int pos) { bool sign = val.sign; signedDepthSum = !sign ? val.depth : -val.depth; signedSum = !sign ? val.x : -val.x; signedCount = !sign ? 1 : -1; } Sum &operator+=(const Sum &that) { signedSum += that.signedSum; signedDepthSum += that.signedDepthSum; signedCount += that.signedCount; return *this; } Sum operator+(const Sum &that) const { return Sum(*this) += that; } };

    struct Laziness { mint add0, add1; Laziness(): add0(0), add1(0) { } Laziness(mint add0_, mint add1_): add0(add0_), add1(add1_) { } Laziness &operator+=(const Laziness &that) { add0 += that.add0; add1 += that.add1; return *this; } void addToVal(Val &val, int pos_) const { val.x += add0 + add1 * val.depth; } void addToSum(Sum &sum, int left_, int right_) const { sum.signedSum += add0 * sum.signedCount + add1 * sum.signedDepthSum; } };

    struct SegmentTree { vector leafs; vector nodes; vector laziness; vector leftpos, rightpos; int n, n2; void init(int n_, const Val &v = Val()) { init(vector(n_, v)); } void init(const vector &u) { n = 2; while(n < (int)u.size()) n *= 2; n2 = (n - 1) / 2 + 1; leafs = u; leafs.resize(n, Val()); nodes.resize(n); for(int i = n-1; i >= n2; -- i) nodes[i] = Sum(leafs[i*2-n], i*2-n) + Sum(leafs[i*2+1-n], i*2+1-n); for(int i = n2-1; i > 0; -- i) nodes[i] = nodes[i*2] + nodes[i*2+1]; laziness.assign(n, Laziness());

        leftpos.resize(n); rightpos.resize(n);
        for(int i = n-1; i >= n2; -- i) {
            leftpos[i] = i*2-n;
            rightpos[i] = (i*2+1-n) + 1;
        }
        for(int i = n2-1; i > 0; -- i) {
            leftpos[i] = leftpos[i*2];
            rightpos[i] = rightpos[i*2+1];
        }
    }
    Val get(int i) {
        static int indices[128];
        int k = getIndices(indices, i, i+1);
        propagateRange(indices, k);
        return leafs[i];
    }
    Sum getRange(int i, int j) {
        static int indices[128];
        int k = getIndices(indices, i, j);
        propagateRange(indices, k);
        Sum res = Sum();
        for(int l = i + n, r = j + n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) res += sum(l ++);
            if(r & 1) res += sum(-- r);
        }
        return res;
    }
    void set(int i, const Val &x) {
        static int indices[128];
        int k = getIndices(indices, i, i+1);
        propagateRange(indices, k);
        leafs[i] = x;
        mergeRange(indices, k);
    }
    void addToRange(int i, int j, const Laziness &x) {
        if(i >= j) return;
        static int indices[128];
        int k = getIndices(indices, i, j);
        propagateRange(indices, k);
        int l = i + n, r = j + n;
        if(l & 1) { int p = (l ++) - n; x.addToVal(leafs[p], p); }
        if(r & 1) { int p = (-- r) - n; x.addToVal(leafs[p], p); }
        for(l >>= 1, r >>= 1; l < r; l >>= 1, r >>= 1) {
            if(l & 1) laziness[l ++] += x;
            if(r & 1) laziness[-- r] += x;
        }
        mergeRange(indices, k);
    }
    

    private: int getIndices(int indices[128], int i, int j) { int k = 0, l, r; if(i >= j) return 0; for(l = (n + i) >> 1, r = (n + j - 1) >> 1; l != r; l >>= 1, r >>= 1) { indices[k ++] = l; indices[k ++] = r; } for(; l; l >>= 1) indices[k ++] = l; return k; } void propagateRange(int indices[], int k) { for(int i = k - 1; i >= 0; -- i) propagate(indices[i]); } void mergeRange(int indices[], int k) { for(int i = 0; i < k; ++ i) merge(indices[i]); } inline void propagate(int i) { if(i >= n) return; laziness[i].addToSum(nodes[i], leftpos[i], rightpos[i]); if(i * 2 < n) { laziness[i * 2] += laziness[i]; laziness[i * 2 + 1] += laziness[i]; }else { laziness[i].addToVal(leafs[i * 2 - n], i * 2); laziness[i].addToVal(leafs[i * 2 + 1 - n], i * 2 + 1); } laziness[i] = Laziness(); } inline void merge(int i) { if(i >= n) return; nodes[i] = sum(i * 2) + sum(i * 2 + 1); } inline Sum sum(int i) { propagate(i); return i < n ? nodes[i] : Sum(leafs[i - n], i - n); } };

    vector t_parent; vi t_seq; vector t_sign; vector t_left, t_right;

    void tree_signedeulertour(const vector &g, int root) { int n = g.size(); t_parent.assign(n, -1); t_left.assign(n, -1); t_right.assign(n, -1); t_seq.assign(n * 2, -1); t_sign.assign(n * 2, false); int pos = 0;

    vector<int> stk; stk.push_back(root);
    while(!stk.empty()) {
        int i = stk.back(); stk.pop_back();
        if(i < 0) {
            i = -i - 1;
            t_seq[pos] = i;
            t_sign[pos] = true;
            pos ++;
            t_right[i] = pos;
            continue;
        }
        t_left[i] = pos;
        t_seq[pos] = i;
        t_sign[pos] = false;
        pos ++;
    
        stk.push_back(-(i+1));
        for(int j = (int)g[i].size()-1; j >= 0; j --) {
            int c = g[i][j];
            if(t_parent[c] == -1 && c != root)
                stk.push_back(c);
            else
                t_parent[i] = c;
        }
    }
    

    }

    int main() { int N, Q, root; scanf("%d%d%d", &N, &Q, &root), root --; vector g(N); rep(i, N-1) { int a, b; scanf("%d%d", &a, &b), a --, b --; g[a].pb(b); g[b].pb(a); } tree_signedeulertour(g, root); vi depth(N, -1); rep(ix, t_seq.size()) if(!t_sign[ix]) { int i = t_seq[ix]; depth[i] = i == root ? 0 : depth[t_parent[i]] + 1; }

    vector<SchieberVishkinLCA::Graph::Edge> edges;
    rep(i, N) if(i != root) {
        edges.push_back(SchieberVishkinLCA::Graph::Edge(t_parent[i], i));
    }
    SchieberVishkinLCA lca;
    SchieberVishkinLCA::Graph gg; gg.init(N, edges);
    lca.build(gg, root);
    
    SegmentTree segt;
    {    vector<Val> vals;
        rep(i, t_seq.size())
            vals.push_back(Val(t_sign[i], 0, depth[t_seq[i]]));
        segt.init(vals);
    }
    rep(ii, Q) {
        static char q[2];
        scanf("%s", q);
        if(*q == 'U') {
            int T, V, K;
            scanf("%d%d%d", &T, &V, &K), T --;
            Laziness l(mint(V) - mint(K) * depth[T], K);
            segt.addToRange(t_left[T], t_right[T], l);
        }else {
            int A, B;
            scanf("%d%d", &A, &B), A --, B --;
            int C = lca.query(A, B);
            mint ans = 0;
            ans += segt.getRange(t_left[C], t_left[A]+1).signedSum;
            ans += segt.getRange(t_left[C]+1, t_left[B]+1).signedSum;
            printf("%d\n", ans.get());
        }
    }
    return 0;
    

    }