#include
using namespace std;
typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int)
struct edge { int t; edge *next; }; struct seg { dint a, b, s; int t; seg *ls, *rs; }; #define sgt_root 1,n+1 #define midp ((pl+pr)»1) #define pls pl,midp #define prs midp,pr
const int maxn = 100009;
int n, m, p; int d[maxn], sz[maxn], fa[maxn], tc, fc[maxn], ch[maxn], fs[maxn]; int dfb[maxn], dfe[maxn], dfo[maxn], ci, ti; edge elst[maxn « 1], *ep(elst), *head[maxn]; seg *rt[0];
inline seg* newSeg() { static const int bsz = 1000000; static int cb(1); static seg* sp; if (!– cb) return cb = bsz - 1, sp = new seg[bsz]; else return ++ sp; } inline seg* cpSeg(seg* p) { seg* q(newSeg()); memcpy(q, p, sizeof(seg)); return q; }
inline void addEdge(int u, int v) { ep-> t = v; ep-> next = head[u]; head[u] = ep ++; }
inline seg* sgtBuild(int pl, int pr) { seg *p(newSeg()); p-> t = 0; p-> a = p-> b = p-> s = 0; if (pl + 1 < pr) { p-> ls = sgtBuild(pls); p-> rs = sgtBuild(prs); } return p; }
inline seg* sgtChg(seg* p, int pl, int pr, int l, int r, dint va, dint vb) { seg *g; if (p-> t == ti) { g = p; } else { g = cpSeg(p); g-> t = ti; } g-> s += va * (r - l) + ((vb * (r - l) * (r - l - 1))» 1); if (pl == l && pr == r) { g-> a += va; g-> b += vb; } else if (r <= midp) g-> ls = sgtChg(p-> ls, pls, l, r, va, vb); else if (l >= midp) g-> rs = sgtChg(p-> rs, prs, l, r, va, vb); else { g-> ls = sgtChg(p-> ls, pls, l, midp, va, vb); g-> rs = sgtChg(p-> rs, prs, midp, r, va + vb * (midp - l), vb); } return g; }
inline dint sgtQry(seg* p, int pl, int pr, int l, int r) { if (pl == l && pr == r) return p-> s; else { dint sa(p-> a * (r - l) + ((p-> b * (l + r - 1 - pl * 2) * (r - l)) » 1)); if (r <= midp) return sgtQry(p-> ls, pls, l, r) + sa; else if (l >= midp) return sgtQry(p-> rs, prs, l, r) + sa; else return sgtQry(p-> ls, pls, l, midp) + sgtQry(p-> rs, prs, midp, r) + sa; } }
#define cpos(p) (d[p]-d[ch[fc[p]]])
void divide() { static int stc[maxn]; int tst(1), dfn(0); memset(d, 0, sizeof(d)); d[stc[1] = 1] = 1; fa[1] = 0; while (tst) { int p(stc[tst –]); dfo[++ dfn] = p; for (edge* e = head[p]; e; e = e-> next) if (!d[e-> t]) { d[e-> t] = d[p] + 1; fa[e-> t] = p; stc[++ tst] = e-> t; } } tc = 0; for (int i = n; i; – i) { int p(dfo[i]); fs[p] = -1; sz[p] = 1; for (edge* e = head[p]; e; e = e-> next) if (fa[e-> t] == p) { sz[p] += sz[e-> t]; if (fs[p] == -1 || sz[e-> t] > sz[fs[p]]) fs[p] = e-> t; } if (fs[p] == -1) fc[p] = ++ tc; else fc[p] = fc[fs[p]]; ch[fc[p]] = p; } stc[tst = 1] = 1; dfn = 0; while (tst) { int p(stc[tst –]); dfo[dfb[p] = ++ dfn] = p; dfe[p] = dfb[p]; for (edge* e = head[p]; e; e = e-> next) if (fa[e-> t] == p && e-> t != fs[p]) stc[++ tst] = e-> t; if (fs[p] > -1) stc[++ tst] = fs[p]; } for (int i = n; i > 1; – i) { int p(dfo[i]); dfe[fa[p]] = max(dfe[fa[p]], dfe[p]); } rt[ti = ci = 0] = sgtBuild(sgt_root); }
int LCA(int u, int v) { while (fc[u] ^ fc[v]) if (d[ch[fc[u]]] > d[ch[fc[v]]]) u = fa[ch[fc[u]]]; else v = fa[ch[fc[v]]]; if (d[u] < d[v]) return u; else return v; }
int main() { #ifndef ONLINE_JUDGE freopen(“in.txt”, “r”, stdin); #endif
scanf("%d%d", &n, &m);
for (int i = 1; i < n; ++ i) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
divide();
dint lans(0);
while (m --) {
char opt[3];
dint xo, yo;
int u, v;
scanf("%s", opt);
if (opt[0] == 'c') {
dint a, b;
scanf(lld lld lld lld, &xo, &yo, &a, &b);
u = xo ^ lans;
v = yo ^ lans;
int w(LCA(u, v));
++ ti;
rt[ti] = rt[ci];
ci = ti;
for (; fc[u] ^ fc[w]; u = fa[ch[fc[u]]]) {
a += b * cpos(u);
rt[ci] = sgtChg(rt[ci], sgt_root, dfb[ch[fc[u]]], dfb[u] + 1, a, -b);
a += b;
}
if (u ^ w) {
a += b * (d[u] - d[w] - 1);
rt[ci] = sgtChg(rt[ci], sgt_root, dfb[w] + 1, dfb[u] + 1, a, -b);
a += b;
}
a += b * (d[v] - d[w]);
for (; fc[v] ^ fc[w]; v = fa[ch[fc[v]]]) {
a -= b * cpos(v);
rt[ci] = sgtChg(rt[ci], sgt_root, dfb[ch[fc[v]]], dfb[v] + 1, a, b);
a -= b;
}
a -= b * (d[v] - d[w]);
rt[ci] = sgtChg(rt[ci], sgt_root, dfb[w], dfb[v] + 1, a, b);
}
else if (opt[0] == 'q') {
scanf(lld lld, &xo, &yo);
u = xo ^ lans;
v = yo ^ lans;
dint ans(0);
while (fc[u] ^ fc[v])
if (d[ch[fc[u]]] > d[ch[fc[v]]]) {
ans += sgtQry(rt[ci], sgt_root, dfb[ch[fc[u]]], dfb[u] + 1);
u = fa[ch[fc[u]]];
}
else {
ans += sgtQry(rt[ci], sgt_root, dfb[ch[fc[v]]], dfb[v] + 1);
v = fa[ch[fc[v]]];
}
if (d[u] < d[v])
ans += sgtQry(rt[ci], sgt_root, dfb[u], dfb[v] + 1);
else
ans += sgtQry(rt[ci], sgt_root, dfb[v], dfb[u] + 1);
printf(lld "\n", (lans = ans));
}
else if (opt[0] == 'l') {
scanf(lld, &xo);
ci = xo ^ lans;
}
// lans = 0; } }