洛谷 P3384 【模板】树链剖分

洛谷 P3384 【模板】树链剖分

#include using namespace std;typedef long long ll;const int maxn = 1e5 + 10;int n, m, r, p, a[maxn];int mem, head[maxn], id[maxn], idr[maxn];struct Edge { int to, next; } edges[maxn<<1];void init_edges() { mem = 0; for (int i = 0; i <= n; i++) head[i] = 0; for (int i = 0; i <= n; i++) id[i] = idr[i] = 0;}void addedge(int from, int to) { edges[mem].to = to; edges[mem].next = head[from]; head[from] = mem++;}struct Tree { int l, r; ll sum, tag;}tree[maxn<<2];void pushup(int root) { tree[root].sum = (tree[root<<1].sum + tree[root<<1|1].sum)%p;}void pushdown(int root) { if (tree[root].tag == 0) return; int l = root<<1, r = root<<1|1; tree[l].tag = (tree[l].tag + tree[root].tag)%p; tree[r].tag = (tree[r].tag + tree[root].tag)%p; tree[l].sum = (tree[l].sum + (tree[l].r-tree[l].l+1)*tree[root].tag)%p; tree[r].sum = (tree[r].sum + (tree[r].r-tree[r].l+1)*tree[root].tag)%p; tree[root].tag = 0;}void build(int root, int l, int r) { tree[root].l = l, tree[root].r = r; tree[root].sum = tree[root].tag = 0; if (l == r) { tree[root].sum = a[idr[l]]; return; } int mid = (l + r) >> 1; build(root<<1, l, mid); build(root<<1|1, mid+1, r); pushup(root);}void update(int root, int x, int y, ll z) { if (y < tree[root].l || tree[root].r < x) return; if (x <= tree[root].l && tree[root].r <= y) { tree[root].sum = (tree[root].sum + (tree[root].r-tree[root].l+1)*z)%p; tree[root].tag = (tree[root].tag + z)%p; return; } pushdown(root); update(root<<1, x, y, z); update(root<<1|1, x, y, z); pushup(root);}ll query(int root, int x, int y) { if (y < tree[root].l || tree[root].r < x) return 0; if (x <= tree[root].l && tree[root].r <= y) return tree[root].sum; pushdown(root); return (query(root<<1, x, y)+query(root<<1|1, x, y))%p;}int dcnt;struct Node { int fa, son, sz, dep, top, s, e;}node[maxn];void init_node() { dcnt = 0; for (int i = 1; i <= n; i++) node[i].fa = node[i].son = 0;}void dfs1(int u) { node[u].sz = 1; for (int i = head[u]; i; i = edges[i].next) { int v = edges[i].to; if (v == node[u].fa) continue; node[v].fa = u; node[v].dep = node[u].dep + 1; dfs1(v); node[u].sz += node[v].sz; if (node[v].sz > node[node[u].son].sz) node[u].son = v; }}void dfs2(int u, int top) { node[u]- = top; id[u] = ++dcnt; idr[dcnt] = u; node[u].s = id[u]; if (node[u].son) { dfs2(node[u].son, top); for (int i = head[u]; i; i = edges[i].next) { int v = edges[i].to; if (v != node[u].fa && v != node[u].son) dfs2(v, v); } } node[u].e = dcnt;}void update_path(int x, int y, ll z) { int tx = node[x]-, ty = node[y]-; while (tx != ty) { if (node[tx].dep < node[ty].dep) swap(tx, ty), swap(x, y); update(1, id[tx], id[x], z); x = node[tx].fa; tx = node[x]-; } if (node[x].dep < node[y].dep) update(1, id[x], id[y], z); else update(1, id[y], id[x], z);}ll query_path(int x, int y) { int tx = node[x]-, ty = node[y]-; ll ans = 0; while (tx != ty) { if (node[tx].dep < node[ty].dep) swap(tx, ty), swap(x, y); ans = (ans + query(1, id[tx], id[x]))%p; x = node[tx].fa; tx = node[x]-; } if (node[x].dep < node[y].dep) ans = (ans + query(1, id[x], id[y]))%p; else ans = (ans + query(1, id[y], id[x]))%p; return ans;}int main() { scanf("%d%d%d%d", &n, &m, &r, &p); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n-1; i++) { int u, v; scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } dfs1(r); dfs2(r, r); build(1, 1, n); while (m--) { int op, x, y; ll z; scanf("%d", &op); if (op == 1) { scanf("%d%d%lld", &x, &y, &z); update_path(x, y, z); } else if (op == 2) { scanf("%d%d", &x, &y); printf("%lld\n", query_path(x, y)); } else if (op == 3) { scanf("%d%lld", &x, &z); update(1, node[x].s, node[x].e, z); } else { scanf("%d", &x); printf("%lld\n", query(1, node[x].s, node[x].e)); } } return 0;}

模板get，160行写完了0w0e一遍过有点吓人。。。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。