标题
标题
标题
标题
标题
标题
#include#define R register int#define I inline void#define IL inline#define ls c[x][0]#define rs c[x][1]const int _ = 3e5 + 5;int n, m;struct Link_Cut_Tree{ int f[_], c[_][2], v[_], s[_], st[_], r[_]; I _swap(R &x, R &y) { R t = x; x = y; y = t; } IL bool nroot(R x) { return c[f[x]][0] == x || c[f[x]][1] == x; } I pushup(R x) { s[x] = s[ls] ^ s[rs] ^ v[x]; } I pushr(R x) { _swap(ls, rs); r[x] ^= 1; } I pushdown(R x) { if(r[x]) { if(ls) pushr(ls); if(rs) pushr(rs); r[x] = 0; } } I pushall(R x) { if(nroot(x)) pushall(f[x]); pushdown(x); } I rotate(R x) { R y = f[x], z = f[y], k = c[y][1] == x, w = c[x][!k]; if(nroot(y)) c[z][c[z][1] == y] = x; c[x][!k] = y; c[y][k] = w; if(w) f[w] = y; f[y] = x; f[x] = z; pushup(y); } I splay(R x) { R y, z; pushall(x); while(nroot(x)) { y = f[x]; z = f[y]; if(nroot(y)) rotate((c[y][0] == x) ^ (c[z][0] == y) ? x : y); rotate(x); } pushup(x); } I access(R x) { for(R y = 0; x; x = f[y = x]) splay(x), rs = y, pushup(x); } I makeroot(R x) { access(x); splay(x); pushr(x); } IL int findroot(R x) { access(x); splay(x); while(ls) pushdown(x), x = ls; splay(x); return x; } I split(R x, R y) { makeroot(x); access(y); splay(y); } I link(R x, R y) { makeroot(x); if(findroot(y) != x) f[x] = y; } I cut(R x, R y) { makeroot(x); if(findroot(y) != x || f[y] != x || c[y][0]) return; f[y] = c[x][1] = 0; pushup(x); }}lct;int main(){ int opt, x, y; scanf("%d%d", &n, &m); for(R i = 1; i <= n; ++i) scanf("%d", &lct.v[i]); while(m--) { scanf("%d%d%d", &opt, &x, &y); if(opt == 0) lct.split(x, y), printf("%d\n", lct.s[y]); else if(opt == 1) lct.link(x, y); else if(opt == 2) lct.cut(x, y); else if(opt == 3) lct.splay(x), lct.v[x] = y; } return 0;}
#include#include #define ll long longusing namespace std;const int N = 1e5 + 10;int n,m,root,mod,cnt,a[N],father[N],deep[N],size[N],son[N],rk[N],top[N],id[N];struct Edge { int Next, to;}e[N<<1];int head[N], num;void add(int from, int to) { e[++num].Next = head[from]; e[num].to = to; head[from] = num;}struct Segment_Tree{ ll ans[N<<2], tag[N<<2]; inline ll ls(ll p) { return p << 1; } inline ll rs(ll p) { return p << 1 | 1; } inline void pushup(ll p) { ans[p] = (ans[ls(p)] + ans[rs(p)]) % mod; } inline void pushdown(ll p, ll l, ll r) { ll mid = (l + r) >> 1; ans[ls(p)] += (mid - l + 1) * tag[p] % mod; tag[ls(p)] += tag[p] % mod; ans[rs(p)] += (r - mid) * tag[p] % mod; tag[rs(p)] += tag[p] % mod; tag[p] = 0; } void build(ll p, ll l, ll r) { if(l == r) { ans[p] = a[rk[l]]; return; } ll mid = (l + r) >> 1; build(ls(p), l, mid); build(rs(p), mid + 1, r); pushup(p); } void update(ll p, ll l, ll r, ll ul, ll ur, ll k) { if(ul <= l && r <= ur) { ans[p] += (r - l + 1) * k % mod; tag[p] += k % mod; return; } if(tag[p]) pushdown(p, l, r); ll mid = (l + r) >> 1; if(ul <= mid) update(ls(p), l, mid, ul, ur, k); if(ur > mid) update(rs(p), mid + 1, r, ul, ur, k); pushup(p); } ll query(ll p, ll l, ll r, ll ql, ll qr) { if(ql <= l && r <= qr) return ans[p]; if(tag[p]) pushdown(p, l, r); ll mid = (l + r) >> 1, res = 0; if(ql <= mid) res = (res + query(ls(p), l, mid, ql, qr)) % mod; if(qr > mid) res = (res + query(rs(p), mid + 1, r, ql, qr)) % mod; return res % mod; }}T;struct lianpou{ void dfs1(int u, int f, int depth) { father[u] = f; deep[u] = depth; size[u] = 1; for(int i = head[u]; i; i = e[i].Next) { int v = e[i].to; if(v == f) continue; dfs1(v, u, depth + 1); size[u] += size[v]; if(size[v] > size[son[u]]) son[u] = v; } } void dfs2(int u, int tp) { top[u] = tp; id[u] = ++cnt; rk[cnt] = u; if(!son[u]) return; dfs2(son[u], tp); for(int i = head[u]; i; i = e[i].Next) { int v = e[i].to; if(v != son[u] && v != father[u]) dfs2(v, v); } } ll sum(int x, int y) { ll ans = 0; int fx = top[x], fy = top[y]; while(fx != fy) { if(deep[fx] >= deep[fy]) { ans = (ans + T.query(1, 1, n, id[fx], id[x])) % mod; x = father[fx], fx = top[x]; } else { ans = (ans + T.query(1, 1, n, id[fy], id[y])) % mod; y = father[fy], fy = top[y]; } } if(id[x] > id[y]) swap(x, y); ans = (ans + T.query(1, 1, n, id[x], id[y])) % mod; return ans % mod; } void update(int x, int y, int z) { int fx = top[x], fy = top[y]; while(fx != fy) { if(deep[fx] >= deep[fy]) { T.update(1, 1, n, id[fx], id[x], z); x = father[fx], fx = top[x]; } else { T.update(1, 1, n, id[fy], id[y], z); y = father[fy], fy = top[y]; } } if(id[x] > id[y]) swap(x, y); T.update(1, 1, n, id[x], id[y], z); }}L;int main(){ scanf("%d%d%d%d", &n, &m, &root, &mod); for(int i = 1; i <= n; i++) scanf("%lld", &a[i]); for(int i = 1, u, v; i < n; i++) { scanf("%d%d", &u, &v); add(u,v); add(v,u); } L.dfs1(root, 0, 1); L.dfs2(root, root); T.build(1, 1, n); for(int i = 1, opt, x, y, z; i <= m; i++) { scanf("%d", &opt); if(opt == 1) { scanf("%d%d%d", &x, &y, &z); L.update(x, y, z); } else if(opt == 2) { scanf("%d%d", &x, &y); printf("%lld\n", L.sum(x, y)); } else if(opt == 3) { scanf("%d%d", &x, &z); T.update(1, 1, n, id[x], id[x] + size[x] - 1, z); } else if(opt == 4) { scanf("%d", &x); printf("%lld\n", T.query(1, 1, n, id[x], id[x] + size[x] - 1)); } } return 0;}
