Problem
acm.hdu.edu.cn/showproblem.php?pid=3966
Reference
树链剖分
树链剖分原理
树链剖分详解及模板
HDU3966(树链剖分)
Meaning
一棵 n 个点的树，每给结点有个值。三种操作：
-
I C1 C2 K：将从结点 C1 到 结点 C2 的路径上的所有点的值都加上 k
-
D C1 C2 K：将从结点 C1 到 结点 C2 的路径上的所有点的值都减去 k
-
Q C：讯问结点 C 的值
Analysis
树链剖分模板。
Notes
树链剖分，是把一棵树拆成若干条链，一条链就可以理解成一个区间。把这些链依次铺在线段树（或其它数据结构）上，那维护树上的信息就转化成维护区间信息。
把树剖成链有很多种剖法，分轻重链地剖（即第一个参考链接中的“启发式剖分”）比较优。
一些概念
记size(t)为以节点 t 为根的子树的大小。
对任意一个非叶子节点，在它所有的子节点中，称size最大的那个为重儿子，其它的叫轻儿子。
节点与它的重儿子的那条连边称为重边，其它边称为轻边。
从某个结点开始，一路沿着重边拓展到叶子，就得到一条链，称为重链，链上的边全都是重边。（好像没有叫轻边的？）
那种启发式剖分就是从树根开始，先一路沿重边拓展下去，得到重链，对于轻儿子，则分别以它们为新的链头，又沿着它的重边拓展，又得到重链。递归这个过程，直到剖完整棵树。
几个数组
-
depth[]：节点的深度
-
tsz[]：以 i 为根的子数的大小
-
fa[]：节点的父节点
-
son[]：节点的重儿子，i 与 son[i] 的连边就是重边
-
top[]：节点所在重链的链头节点
-
pos[]：节点在剖分后的新编号，其实就是把链放进线段树后，这个节点对应线段树的第几片叶子
-
tid[]：跟pos[]是反映射，表示线段树第 i 片叶子对应到原树上的哪一个节点
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50000, M = N;
int head[N+1], to[M<<1], nxt[M<<1];
void add_edge(int f, int t, int id)
{
to[id] = t;
nxt[id] = head[f];
head[f] = id;
}
/*--- 树链剖分部分 ---*/
int dep[N+1], tsz[N+1], fa[N+1], son[N+1];
// 分轻、重链
void heavy_light(int v, int f, int d)
{
dep[v] = d;
tsz[v] = 1;
fa[v] = f;
for(int i = head[v]; ~i; i = nxt[i])
if(to[i] != f)
{
heavy_light(to[i], v, d + 1);
tsz[v] += tsz[to[i]];
if(son[v] == -1 || tsz[to[i]] > tsz[son[v]])
son[v] = to[i];
}
}
int top[N+1], pos[N+1], tid[N+1], tm;
// 剖分
void decompose(int v, int tp)
{
top[v] = tp;
pos[v] = ++tm;
tid[pos[v]] = v;
if(son[v] == -1)
return;
// 先沿重边拓展
decompose(son[v], tp);
// 轻儿子作为新的链头，新开一条重链
for(int i = head[v]; ~i; i = nxt[i])
if(to[i] != fa[v] && to[i] != son[v])
decompose(to[i], to[i]);
}
/*--- 线段树部分 ---*/
int tree[N+1<<2], lazy[N+1<<2];
inline void pushup(int rt)
{
tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}
void pushdown(int rt, int len)
{
if(lazy[rt])
{
lazy[rt<<1] += lazy[rt];
lazy[rt<<1|1] += lazy[rt];
tree[rt<<1] += (len + 1 >> 1) * lazy[rt];
tree[rt<<1|1] += (len >> 1) * lazy[rt];
lazy[rt] = 0;
}
}
void update(int ul, int ur, int v, int l, int r, int id)
{
if(ul <= l && r <= ur)
{
lazy[id] += v;
tree[id] += (r - l + 1) * v;
return;
}
pushdown(id, r - l + 1);
int m = l + r >> 1;
if(ul <= m)
update(ul, ur, v, l, m, id<<1);
if(ur > m)
update(ul, ur, v, m+1, r, id<<1|1);
pushup(id);
}
void change(int l, int r, int v, int n)
{
// 不在同一条重链
while(top[l] != top[r])
{
// 用 l 表示链头比较低的那条链
if(dep[top[l]] < dep[top[r]])
swap(l, r);
update(pos[top[l]], pos[l], v, 1, n, 1);
l = fa[top[l]];
}
// 此时已经处于同一条链
if(dep[l] > dep[r])
swap(l, r);
update(pos[l], pos[r], v, 1, n, 1);
}
int query(int p, int l, int r, int id)
{
if(l == r)
return tree[id];
pushdown(id, r - l + 1);
int m = l + r >> 1, res;
if(p > m)
res = query(p, m+1, r, id<<1|1);
else
res = query(p, l, m, id<<1);
pushup(id);
return res;
}
int a[N+1];
void build(int l, int r, int id)
{
lazy[id] = 0;
if(l == r)
{
tree[id] = a[tid[l]];
return;
}
int m = l + r >> 1;
build(l, m, id<<1);
build(m+1, r, id<<1|1);
pushup(id);
}
int main()
{
int n, m, p;
while(~scanf("%d%d%d", &n, &m, &p))
{
for(int i = 1; i <= n; ++i)
scanf("%d", a+i);
memset(head, -1, sizeof head);
for(int i = 0, f, t, sz = 0; i < m; ++i)
{
scanf("%d%d", &f, &t);
add_edge(f, t, sz++);
add_edge(t, f, sz++);
}
memset(son, -1, sizeof son);
heavy_light(1, 0, 1);
tm = 0;
decompose(1, 1);
build(1, n, 1);
for(int q, x, y, k; p--; )
{
char op;
scanf(" %c", &op);
if(op == 'Q')
{
scanf("%d", &q);
printf("%d\n", query(pos[q], 1, n, 1));
}
else
{
scanf("%d%d%d", &x, &y, &k);
if(op == 'D')
k = -k;
change(x, y, k, n);
}
}
}
return 0;
}
