題意：要求在一棵N（<=50000）個(gè)帶權(quán)節(jié)點(diǎn)的樹(shù)上支持3種操作

（1）I u v w，u到v的路徑上每個(gè)節(jié)點(diǎn)權(quán)值增加w

（2）D u v w，u到v的路徑上每個(gè)節(jié)點(diǎn)權(quán)值減少w

（3）Q u，求u點(diǎn)的權(quán)值

思路：

將樹(shù)剖分成若干條鏈，然后用區(qū)間數(shù)據(jù)結(jié)構(gòu)來(lái)維護(hù)，這就是樹(shù)鏈剖分。樹(shù)鏈剖分后，這個(gè)題可以轉(zhuǎn)化為一個(gè)“區(qū)間修改，單點(diǎn)查詢”的問(wèn)題，樹(shù)狀數(shù)組或線段樹(shù)即可。

樹(shù)狀數(shù)組（1100ms）：

#pragma comment(linker, "/STACK:10240000,10240000")#include <iostream> #include <cstdio> #include <ctime> #include <cstring> using namespace std; #define X first #define Y second #define pb(x) push_back(x) #define mp(x, y) make_pair(x, y) #define all(a) (a).begin(), (a).end() #define mset(a, x) memset(a, x, sizeof(a)) #define mcpy(a, b) memcpy(a, b, sizeof(b)) #define cas() int T, cas = 0; cin >> T; while (T --) template<typename T>bool umax(T&a, const T&b){return a<b?(a=b,true):false;} template<typename T>bool umin(T&a, const T&b){return b<a?(a=b,true):false;} typedef long long ll; typedef pair<int, int> pii;#ifndef ONLINE_JUDGE#include "local.h" #endifconst int N = 5e4 + 7; const int M = N;namespace Edge {int last[N], to[M << 1], next[M << 1], cntE;void init() {cntE = 0;memset(last, -1, sizeof(last));}void addEdge(int u, int v) {to[cntE] = v;next[cntE] = last[u];last[u] = cntE ++;} }namespace TreeChain {int dep[N], top[N], w[N], son[N], siz[N], fa[N];int id[N], rnk[N], cntID;void init() {cntID = 0;memset(son, -1, sizeof(son));}void dfs1(int u, int f, int d) {dep[u] = d;fa[u] = f;siz[u] = 1;for (int i = Edge::last[u]; ~i; i = Edge::next[i]) {int v = Edge::to[i];if (v != f) {dfs1(v, u, d + 1);siz[u] += siz[v];if (son[u] == -1 || siz[v] > siz[son[u]])son[u] = v;}}}void dfs2(int u, int t) {top[u] = t;id[u] = ++ cntID;rnk[id[u]] = u;if (son[u] == -1) return;dfs2(son[u], t);for (int i = Edge::last[u]; ~i; i = Edge::next[i]) {int v = Edge::to[i];if (v != son[u] && v != fa[u])dfs2(v, v);}} }int a[N];namespace TreeArray {int c[N], n;void init(int n) {memset(c, 0, sizeof(c));TreeArray::n = n;}int lowbit(int x) { return x & -x; }void add(int p, int x) {while (p <= n) {c[p] += x;p += lowbit(p);}}void add(int l, int r, int x) {add(l, x);add(r + 1, -x);}int query(int p) {int ans = 0;while (p) {ans += c[p];p -= lowbit(p);}return ans;}void change(int u, int v, int w) {using namespace TreeChain;while (top[u] != top[v]) {if (dep[top[u]] < dep[top[v]]) swap(u, v);add(id[top[u]], id[u], w);u = fa[top[u]];}if (dep[u] > dep[v]) swap(u, v);add(id[u], id[v], w);} }int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout); #endif // ONLINE_JUDGEint n, m, p, u, v, w;char s[2];while (cin >> n >> m >> p) {Edge::init();TreeChain::init();for (int i = 1; i <= n; i ++) {scanf("%d", a + i);}for (int i = 0; i < m; i ++) {scanf("%d%d", &u, &v);Edge::addEdge(u, v);Edge::addEdge(v, u);}TreeChain::dfs1(1, 0, 0);TreeChain::dfs2(1, 1);TreeArray::init(n);for (int i = 1; i <= n; i ++) {TreeArray::add(i, i, a[TreeChain::rnk[i]]);}for (int i = 0; i < p; i ++) {scanf("%s", s);if (*s == 'Q') {scanf("%d", &u);printf("%d\n", TreeArray::query(TreeChain::id[u]));}else {scanf("%d%d%d", &u, &v, &w);if (*s == 'D') w = -w;TreeArray::change(u, v, w);}}}return 0; }

線段樹(shù)（1900ms）：

#pragma comment(linker, "/STACK:10240000,10240000")#include <iostream> #include <cstdio> #include <ctime> #include <cstring> using namespace std; #define X first #define Y second #define pb(x) push_back(x) #define mp(x, y) make_pair(x, y) #define all(a) (a).begin(), (a).end() #define mset(a, x) memset(a, x, sizeof(a)) #define mcpy(a, b) memcpy(a, b, sizeof(b)) #define cas() int T, cas = 0; cin >> T; while (T --) template<typename T>bool umax(T&a, const T&b){return a<b?(a=b,true):false;} template<typename T>bool umin(T&a, const T&b){return b<a?(a=b,true):false;} typedef long long ll; typedef pair<int, int> pii;#ifndef ONLINE_JUDGE#include "local.h" #endifconst int N = 5e4 + 7; const int M = N;namespace Edge {int last[N], to[M << 1], next[M << 1], cntE;void init() {cntE = 0;memset(last, -1, sizeof(last));}void addEdge(int u, int v) {to[cntE] = v;next[cntE] = last[u];last[u] = cntE ++;} }namespace TreeChain {int dep[N], top[N], w[N], son[N], siz[N], fa[N];int id[N], rnk[N], cntID;void init() {cntID = 0;memset(son, -1, sizeof(son));}void dfs1(int u, int f, int d) {dep[u] = d;fa[u] = f;siz[u] = 1;for (int i = Edge::last[u]; ~i; i = Edge::next[i]) {int v = Edge::to[i];if (v != f) {dfs1(v, u, d + 1);siz[u] += siz[v];if (son[u] == -1 || siz[v] > siz[son[u]])son[u] = v;}}}void dfs2(int u, int t) {top[u] = t;id[u] = ++ cntID;rnk[id[u]] = u;if (son[u] == -1) return;dfs2(son[u], t);for (int i = Edge::last[u]; ~i; i = Edge::next[i]) {int v = Edge::to[i];if (v != son[u] && v != fa[u])dfs2(v, v);}} }int a[N];namespace SegTree {#define lson l, m, rt << 1#define rson m + 1, r, rt << 1 | 1int sum[N << 2], mark[N << 2];void up(int rt) {sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}void down(int rt, int len) {int rlen = len >> 1, llen = len - rlen;if (mark[rt]) {sum[rt << 1] += llen * mark[rt];mark[rt << 1] += mark[rt];sum[rt << 1 | 1] += rlen * mark[rt];mark[rt << 1 | 1] += mark[rt];mark[rt] = 0;}}void build(int l, int r, int rt) {mark[rt] = 0;if (l == r) {sum[rt] = a[TreeChain::rnk[l]];return;}int m = (l + r) >> 1;build(lson);build(rson);up(rt);}void update(int L, int R, int x, int l, int r, int rt) {if (L <= l && r <= R) {sum[rt] += (r - l + 1) * x;mark[rt] += x;return;}int m = (l + r) >> 1;down(rt, r - l + 1);if (L <= m) update(L, R, x, lson);if (R > m) update(L, R, x, rson);up(rt);}int query(int p, int l, int r, int rt) {if (l == r) return sum[rt];int m = (l + r) >> 1;down(rt, r - l + 1);if (p <= m) return query(p, lson);else return query(p, rson);}void change(int u, int v, int w, int n) {using namespace TreeChain;while (top[u] != top[v]) {if (dep[top[u]] < dep[top[v]]) swap(u, v);update(id[top[u]], id[u], w, 1, n, 1);u = fa[top[u]];}if (dep[u] > dep[v]) swap(u, v);update(id[u], id[v], w, 1, n, 1);}#undef lson#undef rson }int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout); #endif // ONLINE_JUDGEint n, m, p, u, v, w;char s[2];while (cin >> n >> m >> p) {Edge::init();TreeChain::init();for (int i = 1; i <= n; i ++) {scanf("%d", a + i);}for (int i = 0; i < m; i ++) {scanf("%d%d", &u, &v);Edge::addEdge(u, v);Edge::addEdge(v, u);}TreeChain::dfs1(1, 0, 0);TreeChain::dfs2(1, 1);SegTree::build(1, n, 1);for (int i = 0; i < p; i ++) {scanf("%s", s);if (*s == 'Q') {scanf("%d", &u);printf("%d\n", SegTree::query(TreeChain::id[u], 1, n, 1));}else {scanf("%d%d%d", &u, &v, &w);if (*s == 'D') w = -w;SegTree::change(u, v, w, n);}}}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/jklongint/p/4950641.html

總結(jié)

以上是生活随笔為你收集整理的[hdu3966 Aragorn's Story]树链剖分的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。