本文主要是介绍HDU 3966 Aragorn's Story 树链剖分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
入门题
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 50010;
struct edge
{int v, next;
}e[maxn*2];int n, m, q;int first[maxn], cnt;
int top[maxn], tid[maxn], rank[maxn], sz[maxn], f[maxn], son[maxn], dep[maxn], tim;
int d[maxn][2], a[maxn];void AddEdge(int u, int v)
{e[cnt].v = v;e[cnt].next = first[u];first[u] = cnt++;e[cnt].v = u;e[cnt].next = first[v];first[v] = cnt++;
}void dfs1(int u, int fa, int d)
{sz[u] = 1;f[u] = fa;dep[u] = d;for(int i = first[u]; i != -1; i = e[i].next){int v = e[i].v;if(v == f[u])continue;dfs1(v, u, d+1);sz[u] += sz[v];if(son[u] == -1 || sz[son[u]] < sz[v])son[u] = v;}
}void dfs2(int u, int tp)
{top[u] = tp;tid[u] = ++tim;rank[tid[u]] = u;if(son[u] == -1)return;dfs2(son[u], tp);for(int i = first[u]; i != -1; i = e[i].next){int v = e[i].v;if(v != son[u] && v != f[u])dfs2(v, v);}
}
void init()
{memset(first, -1, sizeof(first));cnt = 0;memset(son, -1, sizeof(son));tim = 0;
}int st[maxn<<2];
int lz[maxn<<2];
void build(int l, int r, int rt)
{st[rt] = lz[rt] = 0;if(l == r){lz[rt] = a[rank[l]];return;}int m = (l + r) >> 1;build(l, m, rt<<1);build(m+1, r, rt<<1|1);
}void pushdown(int l, int r, int rt)
{if(lz[rt]){lz[rt<<1] += lz[rt];lz[rt<<1|1] += lz[rt];lz[rt] = 0;}
}
void update(int x, int y, int l, int r, int rt, int w)
{if(x == l && y == r){lz[rt] += w;return;}pushdown(l, r, rt);int m = (l + r) >> 1;if(y <= m)update(x, y, l, m, rt<<1, w);else if(x > m)update(x, y, m+1, r, rt<<1|1, w);else{update(x, m, l, m, rt<<1, w);update(m+1, y, m+1, r, rt<<1|1, w);}
}int query(int l, int r, int rt, int x)
{if(l == r)return lz[rt];pushdown(l, r, rt);int m = (l + r) >> 1;if(x <= m)return query(l, m, rt<<1, x);elsereturn query(m+1, r, rt<<1|1, x);
}
void change(int u, int v, int w)
{while(top[u] != top[v]){if(dep[top[u]] < dep[top[v]])swap(u, v);update(tid[top[u]], tid[u], 1, n, 1, w);u = f[top[u]];}if(dep[u] > dep[v])swap(u, v);update(tid[u], tid[v], 1, n, 1, w);
}
int main()
{while(scanf("%d %d %d", &n, &m, &q) != EOF){init();for(int i = 1; i <= n; i++)scanf("%d", &a[i]);for(int i = 1; i <= m; i++){int u, v;scanf("%d %d", &u, &v);AddEdge(u, v);}dfs1(1, -1, 0);dfs2(1, 1);build(1, n, 1);while(q--){char s[10];scanf("%s", s);if(s[0] == 'I'){int u, v, w;scanf("%d %d %d", &u, &v, &w);change(u, v, w);}else if(s[0] == 'D'){int u, v, w;scanf("%d %d %d", &u, &v, &w);change(u, v, -w);}else{int x;scanf("%d", &x);printf("%d\n", query(1, n, 1, tid[x]));}}}return 0;
}这篇关于HDU 3966 Aragorn's Story 树链剖分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
