題目大意

樹剖裸題，支持路徑上加，單點修改

題目鏈接

傳送門

代碼

要注意有多組輸入，每次都要初始化，測試樣例只給了一組，有些迷惑性。

#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cctype> #define mid (l + r >> 1) using namespace std; const int N = 5e4 + 10; int n, m, q, tot, cnt; int head[N], w[N]; int siz[N],dep[N], par[N], son[N]; int dfn[N], pre[N], top[N]; inline int read(){int x = 0, op = 1;char ch = getchar();while (!isdigit(ch)){if (ch == '-') op = -1;ch = getchar();}while (isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}return x * op; }struct edge{int to, nxt; }e[N << 1];inline void add_edge(int u, int v){e[++tot] = {v, head[u]};head[u] = tot; }void dfs1(int u, int fa){siz[u] = 1;par[u] = fa;dep[u] = dep[fa] + 1;for (int i = head[u]; i; i = e[i].nxt) {int v = e[i].to;if (v == fa) continue;dfs1(v, u);siz[u] += siz[v];if (siz[son[u]] < siz[v])son[u] = v;} }void dfs2(int u, int tp){dfn[u] = ++cnt;pre[cnt] = u;top[u] = tp;if (son[u])dfs2(son[u], tp);for (int i = head[u]; i; i = e[i].nxt) {int v = e[i].to;if (v != par[u] && v != son[u])dfs2(v, v);} }int sum[N << 2], add[N << 2];void push_up(int i){sum[i] = sum[i << 1] + sum[i << 1|1]; }void push_down(int i, int l, int r){if (add[i] == 0)return;add[i << 1] += add[i];add[i << 1|1] += add[i];sum[i << 1] += add[i] * (mid - l + 1);sum[i << 1|1] += add[i] * (r - mid);add[i] = 0; }void buildTree(int i, int l, int r){if (l == r){sum[i] = w[pre[l]];return;}buildTree(i << 1, l, mid);buildTree(i << 1|1, mid + 1, r);push_up(i); }void add_interval(int i, int l, int r, int crtl, int crtr, int val){if (l > crtr || r < crtl)return;if (l >= crtl && r <= crtr){sum[i] += (r - l + 1) * val;add[i] += val;return;}push_down(i, l, r);if (mid >= crtl)add_interval(i << 1, l, mid, crtl, crtr, val);if (mid < crtr)add_interval(i << 1|1, mid + 1, r, crtl, crtr, val);push_up(i); }int query_point(int i, int l, int r, int pos){if (l == r)return sum[i];push_down(i, l, r);if (pos <= mid)return query_point(i << 1, l, mid, pos);elsereturn query_point(i << 1|1, mid + 1, r, pos); }inline void add_tree(int u, int v, int val){while (top[u] != top[v]){if (dep[top[u]] < dep[top[v]])swap(u, v);add_interval(1, 1, n, dfn[top[u]], dfn[u], val);u = par[top[u]];}if (dep[u] > dep[v])swap(u, v);add_interval(1, 1, n, dfn[u], dfn[v], val); }void init(){memset(head, 0, sizeof head);memset(siz, 0, sizeof siz);memset(dep, 0, sizeof dep);memset(son, 0, sizeof son);memset(dfn, 0, sizeof dfn);memset(pre, 0, sizeof pre);memset(sum, 0, sizeof sum);memset(add, 0, sizeof add);int i = 1;while (e[i].to != 0)e[i++] = {0, 0}; }int main() {while (scanf("%d%d%d", &n, &m, &q) == 3) {init();for (int i = 1; i <= n; ++i) {w[i] = read();}tot = cnt = 0;for (int i = 1, x, y; i <= m; ++i) {x = read(), y = read();add_edge(x, y);add_edge(y, x);}dfs1(1, 0);dfs2(1, 1);buildTree(1, 1, n);int a = 0, b = 0, c = 0;char op[2];while (q--) {scanf("%s", op);if (op[0] == 'I') {a = read(), b = read(), c = read();add_tree(a, b, c);} else if (op[0] == 'D') {a = read(), b = read(), c = read();add_tree(a, b, -c);} else {a = read();printf("%d\n", query_point(1, 1, n, dfn[a]));}}}return 0; }

總結

以上是生活随笔為你收集整理的【hud3966】树剖模板05的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。