树链剖分学习
参考代码：
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
typedef long long ll;
const int N = 1005;
const int maxn = 1e6 + 5;
struct node
{int v, nex;
} edge[maxn << 1];
int head[maxn], w[maxn], son[maxn], deep[maxn];
int pre[maxn], sizx[maxn], dfn[maxn], top[maxn], a[maxn];
int cnt, cnx;
void add(int u, int v)
{edge[cnt].v = v, edge[cnt].nex = head[u];head[u] = cnt++;
}
void dfs1(int u, int fa)
{pre[u] = fa;deep[u] = deep[fa] + 1;sizx[u] = 1;int maxson = -1;for (int i = head[u]; ~i; i = edge[i].nex){int v = edge[i].v;if (v != fa){dfs1(v, u);sizx[u] += sizx[v];if (maxson < sizx[v]){son[u] = v;maxson = sizx[v];}}}
}
void dfs2(int u, int t)
{top[u] = t;dfn[u] = ++cnx;a[cnx] = w[u];if (!son[u])return;dfs2(son[u], t);for (int i = head[u]; ~i; i = edge[i].nex){int v = edge[i].v;if (v != pre[u] && v != son[u]){dfs2(v, v);}}
}
struct vain
{int l, r, p, lazy;
} tr[maxn << 2];
void pushdown(int k)
{if (tr[k].lazy){tr[k << 1].p += tr[k].lazy;tr[k << 1 | 1].p += tr[k].lazy;tr[k << 1].lazy += tr[k].lazy;tr[k << 1 | 1].lazy += tr[k].lazy;tr[k].lazy = 0;}
}
void build(int k, int l, int r)
{tr[k].l = l, tr[k].r = r, tr[k].lazy = 0;if (l == r){tr[k].p = a[l];return;}int mid = l + r >> 1;build(k << 1, l, mid);build(k << 1 | 1, mid + 1, r);
}
void modify(int k, int ql, int qr, int w)
{if (tr[k].l >= ql && tr[k].r <= qr){tr[k].p += w;tr[k].lazy += w;return;}pushdown(k);int mid = tr[k].l + tr[k].r >> 1;if (ql <= mid){modify(k << 1, ql, qr, w);}if (qr > mid){modify(k << 1 | 1, ql, qr, w);}
}
int query(int k, int pos)
{if (tr[k].l == tr[k].r){return tr[k].p;}pushdown(k);int mid = tr[k].l + tr[k].r >> 1;if (mid >= pos)return query(k << 1, pos);elsereturn query(k << 1 | 1, pos);
}
void swap(int &x, int &y)
{int tep = x;x = y, y = tep;
}
void mtre(int x, int y, int z)
{while (top[x] != top[y]){if (deep[top[x]] < deep[top[y]])swap(x, y);modify(1, dfn[top[x]], dfn[x], z);x = pre[top[x]];}if (deep[x] > deep[y])swap(x, y);modify(1, dfn[x], dfn[y], z);
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int n, m, q;while (cin >> n >> m >> q){memset(son, 0, sizeof son);memset(head, -1, sizeof head);cnx = cnt = 0;int u, v;for (int i = 1; i <= n; i++)cin >> w[i];for (int i = 0; i < m; i++){cin >> u >> v;add(u, v), add(v, u);}dfs1(1, 0);dfs2(1, 1);build(1, 1, n);while (q--){char c;cin >> c;if (c == 'I'){int u, v, w;cin >> u >> v >> w;mtre(u, v, w);}if (c == 'D'){int u, v, w;cin >> u >> v >> w;mtre(u, v, -w);}if (c == 'Q'){int p;cin >> p;cout << query(1, dfn[p]) << endl;}}}
}