rt 本人袜子

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 5, p = 20160501, inv = 10080251;
ll dep[maxn], val[maxn], ide[maxn], son[maxn], top[maxn], siz[maxn], fat[maxn], a[maxn], b[maxn], sum[maxn][2];
vector <ll> G[maxn];
ll ver[maxn], rt, op, x, y, w, vers, lst, num, n, q, u, v, cnt;
void dfs1(ll u, ll fa) {
    fat[u] = fa;
    dep[u] = dep[fa] + 1;
    siz[u] = 1;
    for (auto g : G[u]) {
        if (g == fa) continue;
        dfs1(g, u);
        siz[u] += siz[g];
        if (siz[g] > siz[son[u]]) son[u] = g;
    }
}
void dfs2(ll u, ll T) {
    ide[u] = ++cnt;
    top[u] = T;
    a[cnt] = val[u];
    b[cnt] = dep[u];
    if (son[u]) dfs2(son[u], T);
    for (auto g : G[u]) {
        if (g == fat[u] || g == son[u]) continue;
        dfs2(g, g);
    }
}
struct node {
    ll sum, smul, spow, tag;
    ll ls, rs, lv, rv;
    inline void out() {
    	cout << sum << ' ' << smul << ' ' << spow << ' ' << tag << ' ' << ls << ' ' << rs << ' ' << lv << ' ' << rv << '\n';
	}
    friend node operator + (node a, node b) {
        return node{
            (a.sum + b.sum) % p,
            (a.smul + b.smul) % p,
            (a.spow + b.spow) % p,
            0, 0, 0, 0, 0};
    }
} t[maxn << 6];
ll tot;
#define mid (l + r >> 1)
void build(ll l, ll r, ll &u) {
    u = ++tot;
    if (l == r) {
        t[u] = {
            a[l],
            a[l] * b[l] % p,
            a[l] * b[l] % p * b[l] % p,
            0, 0, 0, 0, 0};
        sum[l][0] = (sum[l - 1][0] + b[l]) % p;
        sum[l][1] = (sum[l - 1][1] + b[l] * b[l] % p) % p;
    } else {
        build(l, mid, t[u].ls);
        build(mid + 1, r, t[u].rs);
        node c = t[t[u].ls] + t[t[u].rs];
        t[u].sum  = c.sum;
        t[u].smul = c.smul;
        t[u].spow = c.spow;
    } return;
}
inline ll clone(ll u) {
    t[++tot] = t[u];
    t[tot].lv = t[tot].rv = false;
    return tot;
}
inline void pushup(ll l, ll r, node &x, ll k) {
    x.sum  = (x.sum  + (r - l + 1) * k % p) % p;
    x.smul = (x.smul + (sum[r][0] - sum[l - 1][0] + p) % p * k % p) % p;
    x.spow = (x.spow + (sum[r][1] - sum[l - 1][1] + p) % p * k % p) % p;
    return;
}
void update(ll l, ll r, ll u, ll a, ll b, ll k) {
    pushup(max(l, a), min(r, b), t[u], k);
    if (a <= l && r <= b) {
        t[u].tag = (t[u].tag + k) % p;
    } else {
        if (a <= mid) {
            if (!t[u].lv) {
                t[u].ls = clone(t[u].ls);
                t[u].lv = true;
                t[t[u].ls].lv = t[t[u].ls].rv = false;
            } update(l, mid, t[u].ls, a, b, k);
        }
        if (mid < b) {
            if (!t[u].rv) {
                t[u].rs = clone(t[u].rs);
                t[u].rv = true;
                t[t[u].rs].lv = t[t[u].rs].rv = false;
            } update(mid + 1, r, t[u].rs, a, b, k);
        }	
    } return;
}
node query(ll l, ll r, ll u, ll a, ll b) {
    if (a <= l && r <= b) {
        return t[u];
    } else {
        node res = {0, 0, 0, 0, 0, 0, 0, 0};
        pushup(max(l, a), min(r, b), res, t[u].tag);
        if (a <= mid) res = res + query(l, mid, t[u].ls, a, b);
        if (mid < b)  res = res + query(mid + 1, r, t[u].rs, a, b);
        return res;
    }
}
void lca_update(ll rt, ll u, ll v, ll k) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) {
            update(1, n, ver[rt], ide[top[u]], ide[u], k);
            u = fat[top[u]];
        } else {
            update(1, n, ver[rt], ide[top[v]], ide[v], k);
            v = fat[top[v]];
        }
    }
    if (dep[u] > dep[v]) swap(u, v);
    update(1, n, ver[rt], ide[u], ide[v], k);
}
ll lca(ll u, ll v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) {
            u = fat[top[u]];
        } else {
            v = fat[top[v]];
        }
    }
    return dep[u] < dep[v] ? u : v;
}
inline ll A(ll l, ll r, ll rt, ll deplca, ll depv) {
    if (l > r) return 0;
    node ret = query(1, n, ver[rt], l, r);
    ll res = ret.spow;
    res = (res + (2 * depv - 4 * deplca + 1) * ret.smul % p) % p;
    res = (res + (4 * deplca * deplca + depv - 4 * deplca * depv - 2 * deplca + p) % p * ret.sum % p) % p;
    return res;
}
inline ll B(ll l, ll r, ll rt, ll deplca, ll depv) {
    if (l > r) return 0;
    node ret = query(1, n, ver[rt], l, r);
    ll res = ret.spow;
    res = (res - (2 * depv + 1) * ret.smul % p + p) % p;
    res = (res + (depv * depv + depv) * ret.sum % p) % p;
    return res;
}
ll lca_query(ll rt, ll u, ll v) {
    ll res = 0, Lca = lca(u, v), depv = dep[v];
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) {
            res = (res + A(ide[top[u]], ide[u], rt, dep[Lca], depv)) % p;
            u = fat[top[u]];
        } else {
            res = (res + B(ide[top[v]], ide[v], rt, dep[Lca], depv)) % p;
            v = fat[top[v]];
        }
    }
    if (dep[u] >= dep[v]) {
    	res = (res + A(ide[v], ide[u], rt, dep[Lca], depv)) % p;
    	//cout << "A " << ide[v] << ' ' << ide[u] << '\n';
	} else {
		res = (res + B(ide[u], ide[v], rt, dep[Lca], depv)) % p;
		//cout << "B " << ide[u] << ' ' << ide[v] << '\n'; 
	} return res * inv % p;
}
void DEBUG() {
	for (int i = 1; i <= n; i++) {
		node res = query(1, n, ver[rt], i, i);
		cout << res.sum << ' ' << res.smul << ' ' << res.spow << '\n';
	} cout << '\n';
}
void dfs(ll l, ll r, ll u) {
	cout << '[' << l << ',' << r << "]:" << u << ' '; t[u].out();
	if (l == r) return;
	dfs(l, mid, t[u].ls); dfs(mid + 1, r, t[u].rs);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }
    dfs1(1, 0); dfs2(1, 1);
    build(1, n, ver[0]);
    //DEBUG();
    while (q--) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> w;
            x ^= lst; y ^= lst;
            ll nwrt = clone(ver[rt]);
            ver[++vers] = nwrt;
            rt = vers;
            t[ver[rt]].lv = t[ver[rt]].rv = false;
            lca_update(rt, x, y, w);
        }
        if (op == 2) {
            cin >> x >> y;
            x ^= lst; y ^= lst;
            lst = lca_query(rt, x, y);
            cout << lst << '\n';
        }
        if (op == 3) {
            cin >> x;
            x ^= lst;
            rt = x;
        } //DEBUG();
    }
    return 0;
}
/*
5 6
1 2
2 3
3 4
4 5
1 2 3 4 5
1 1 5 2
3 0
1 1 3 2
1 3 4 2
3 2
2 1 5

73

time0 ver0:
1 2 3 4 5
1 4 9 16 25
1 8 27 64 125

time1 ver1:
3 4 5 6 7
3 8 15 64 35
3 16 45 96 175

time2 ver0:
1 2 3 4 5
1 4 9 16 25
1 8 27 64 125

time3 ver2:
3 4 5 4 5
3 8 15 16 25
3 16 45 64 125

time4 ver3:
3 4 7 6 5
3 8 21 24 25
3 16 63 96 125

time5 ver2:
3 4 5 4 5
3 8 15 16 25
3 16 45 64 125

time6 ver2:
3 4 5 4 5
3 8 15 16 25
3 16 45 64 125

3 4 5 4 5

3 * 4 * 5 + 4 * 3 * 4 + 5 * 2 * 3 + 4 * 1 * 2 = 60 + 48 + 30 + 8 = 146
*/