树上链加
这里说的是点权的树上链加。
离线
差分套在序列中可以用数据结构来维护以达到在线的目的。虽然没有树上的低等数据结构（高等数据结构似乎可以树套树？），但是这个思想是可以用于一个离线算法的。
令Sum[x]=V[x]-sigma(V[son])，V[x]为变化值。
那么在树上u到v的路径上链加，相当于将Sum[u]+w,Sum[v]+w,Sum[LCA(u,v)]-w,Sum[Father[LCA(u,v)]]-w
所以最后再求一趟前缀和（从叶子到根）即可得出最后变化了多少。
代码如下：
type
inf=record
x,next:longint;
end;
var
tree,value,Sum,Father,Depth,Chain,Size,Maxn,Putin,Putout:array[0..100010] of longint;
etree:array[0..100010] of inf;//一堆堆数组为树链剖分的数组（用树链剖分做Lca），Sum[x]表示V[x]-sigma(V[son])，V为变化值（不需要维护），Value[x]为x的原来的权值
n,q,i,u,v,w,top,root:longint;
//一些大众程序就不写上来了
procedure swap(var a,b:longint);//交换两个元素
procedure ins(f,s:longint);//插入一条边，注意更新Father与tree
procedure SizeDepthDFS(x,d:longint);//树链剖分求Size,Depth与欧拉序列
var
v,maxsize:longint;
begin
inc(top);
Putin[x]:=top;
Depth[x]:=d;
v:=tree[x];
maxsize:=0;
while v<>0 do
begin
SizeDepthDFS(etree[v].x,d+1);
if maxsize<Size[etree[v].x] then
begin
maxsize:=Size[etree[v].x];
maxn[x]:=etree[v].x;
end;
inc(Size[x],Size[etree[v].x]);
v:=etree[v].next;
end;
inc(Size[x]);
inc(top);
Putout[x]:=top;
end;
procedure ChainDFS(x,r:longint);//求重链顶端
var
v:longint;
begin
Chain[x]:=r;
v:=tree[x];
while v<>0 do
begin
if etree[v].x=maxn[x] then ChainDFS(etree[v].x,r)
else ChainDFS(etree[v].x,etree[v].x);
v:=etree[v].next;
end;
end;
function Subtree(s,f:longint):boolean;//判断是否为子树
begin
if (Putin[f]<=Putin[s]) and (Putout[s]<=Putout[f]) then exit(true)
else exit(false);
end;
function Lca(u,v:longint):longint;//求最近公共祖先
var
fu,fv:longint;
begin
if Subtree(u,v) then exit(v);
if Subtree(v,u) then exit(u);
while true do
begin
fu:=Chain[u];
fv:=Chain[v];
if Depth[Father[fu]]<Depth[father[fv]] then
begin
swap(fu,fv);
swap(u,v);
end;
u:=Father[fu];
if Subtree(v,u) then exit(u);
end;
end;
procedure Plus(u,v,data:longint);//树上链加
var
l:longint;
begin
l:=Lca(u,v);
inc(Sum[u],data);
inc(Sum[v],data);
dec(Sum[l],data);
dec(Sum[Father[l]],data);
end;
procedure Count(x:longint);//统计前缀和，得到最后的权值变化数组
var
v:longint;
begin
v:=tree[x];
while v<>0 do
begin
Count(etree[v].x);
inc(Sum[x],Sum[etree[v].x]);
v:=etree[v].next;
end;
end;
begin
read(n);//读入
for i:=1 to n do
read(value[i]);
for i:=1 to n-1 do
begin
read(u,v);
ins(u,v);
end;
root:=1;//默认根为1
top:=0;
SizeDepthDFS(root,1);
ChainDFS(root,root);//树链剖分
read(q);
for i:=1 to q do
begin
read(u,v,w);
Plus(u,v,w);//树上链加
end;
Count(root);//统计答案
for i:=1 to n do
inc(value[i],Sum[i]);//得到现在的值
for i:=1 to n do
begin
write(value[i]);//输出
if i<>n then write(' ');
end;
end.
离线算法我就写了这么长（主要是树链剖分丑）……
在线
显然一个离线算法还是不太强大。
记得ZJOI2008就考过一道原题，好像叫做“树的统计”来着？
具体题意是这样的——给出一棵树，要求支持三个操作：树上链加、树上路径求和、树上路径求最大值。
这个时候就只能用在线算法来解决了（也许CDQ分治可以？）。
考虑用树链剖分。
首先把这棵树进行树链剖分，之后就会得到一些重链。接下来把重链首尾相接放在一个序列中。这样保证了一段重链只会在一段连续的区间上。
树上链加相当于修改对应的区间。
树上路径求和相当于查询对应的区间和。
树上路径求最大值相当于查询对应区间的最大值。
而这三个操作均可以用线段树来实现。
所以就可以这样解决了。
至于怎么找对应的区间，可以参考树链剖分求LCA的做法——
如果u与v在同一条重链上，那么直接修改u到v的一段区间就可以了。
对于两个点u与v，找到其所在的重链顶端fu与fv。
取出Father[fu]与Father[fv]中深度更大的一个点。（假设是u）
对u到fu对应的一段区间进行操作（修改或查询），之后将u跳到Father[fu]上。不断操作直到u与v在用一条重链上，之后转到情况1。
我们需要维护一些什么数组呢？
Father（原来的树中每一个节点的父亲节点）、Chain（原来的树中每一个节点所在重链的顶端）、Chainarr（重链首尾相接形成的数组（里面储存的应该是特征值，如上题中就是储存点的权值））、PIC（即“pos in Chainarr”记录节点在Chainarr中对应的位置）、SEGtree（维护Chainarr的线段树）、Depth（节点深度）。
对于一次操作，由于一棵树上最多只有logn条重链，所以最多进行logn次修改（查询）。每一次修改（查询）为logn，所以总的时间复杂度为O(q(logn)^2)。
代码如下（只写了树上链加与树上路径求和）：
const
pnum=100010;
pnumshl2=400040;
type
treenode=record
l,r,sum,tag:longint;//线段树节点
end;
Rec=record
x,next:longint;//原树边
end;
var
SEGtree:array[0..pnumshl2] of Treenode;
//线段树
Depth,Size,Value,Chain,Father,Maxn:array[0..pnum] of longint;
//Depth为节点深度，Size为子树大小，Value为点权，Chain为重链顶端、Father为父亲节点、Maxn记录Size最大的儿子节点。
Chainarr,PIC:array[0..pnum] of longint;
//Chainarr为重链首尾相接组成的数组，PIC为节点在Chainarr中的位置
tree:array[0..pnum] of longint; etree:array[0..pnum] of Rec;
//tree与etree用链表形式储存树
n,q,i,ifdo,u,v,w,root,top:longint;
procedure swap(var a,b:longint);//交换两个值
var
c:longint;
begin
c:=a;
a:=b;
b:=c;
end;
procedure ins(f,s:longint);//插入一条树边（更新tree和etree）
begin
inc(top);
etree[top].x:=s;
etree[top].next:=tree[f];
tree[f]:=top;
Father[s]:=f;
end;
procedure DFS1(x,d:longint);//第一次DFS，更新depth、size、DFSarr、Father与maxn
var
v,maxsize:longint;
begin
maxsize:=0;
Depth[x]:=d;
v:=tree[x];
while v<>0 do
begin
DFS1(etree[v].x,d+1);
inc(Size[x],Size[etree[v].x]);
if Size[etree[v].x]>maxsize then
begin
maxsize:=Size[etree[v].x];
Maxn[x]:=etree[v].x;
end;
v:=etree[v].next;
end;
inc(Size[x]);
end;
procedure DFS2(x,d:longint);//第二次DFS，更新chain
var
v:longint;
begin
Chain[x]:=d;
v:=tree[x];
while v<>0 do
begin
if etree[v].x=Maxn[x] then DFS2(etree[v].x,d)
else DFS2(etree[v].x,etree[v].x);
v:=etree[v].next;
end;
end;
procedure DFS3(x:longint);//第三次DFS，更新Chainarr与PIC
var
v:longint;
begin
inc(top);
Chainarr[top]:=Value[x];
PIC[x]:=top;
v:=tree[x];
while v<>0 do
begin
if Chain[etree[v].x]=Chain[x] then DFS3(etree[v].x);
v:=etree[v].next;
end;
v:=tree[x];
while v<>0 do
begin
if Chain[etree[v].x]<>Chain[x] then DFS3(etree[v].x);
v:=etree[v].next;
end;
end;
procedure Build(p,l,r:longint);//建一棵线段树
var
m:longint;
begin
SEGtree[p].l:=l;
SEGtree[p].r:=r;
if l=r then
begin
SEGtree[p].sum:=Chainarr[l];
exit;
end;
m:=(l+r) shr 1;
Build(p shl 1,l,m);
Build(p shl 1+1,m+1,r);
SEGtree[p].sum:=SEGtree[p shl 1].sum+SEGtree[p shl 1+1].sum;
end;
procedure Pushdown(p:longint);//下传标记
var
li,ri:longint;
begin
if SEGtree[p].tag=0 then exit;
li:=p shl 1;
ri:=p shl 1+1;
inc(SEGtree[li].sum,SEGtree[p].tag*(SEGtree[li].r-SEGtree[li].l+1));
inc(SEGtree[ri].sum,SEGtree[p].tag*(SEGtree[ri].r-SEGtree[ri].l+1));
inc(SEGtree[li].tag,SEGtree[p].tag);
inc(SEGtree[ri].tag,SEGtree[p].tag);
SEGtree[p].tag:=0;
end;
procedure SEGchange(p,l,r,data:longint);//线段树区间修改
var
m:longint;
begin
if (SEGtree[p].l=l) and (SEGtree[p].r=r) then
begin
inc(SEGtree[p].sum,data*(r-l+1));
inc(SEGtree[p].tag,data);
exit;
end;
Pushdown(p);
m:=(SEGtree[p].l+SEGtree[p].r) shr 1;
if r<=m then SEGchange(p shl 1,l,r,data)
else
if m+1<=l then SEGchange(p shl 1+1,l,r,data)
else
begin
SEGchange(p shl 1,l,m,data);
SEGchange(p shl 1+1,m+1,r,data);
end;
SEGtree[p].sum:=SEGtree[p shl 1].sum+SEGtree[p shl 1+1].sum;
end;
function SEGgetsum(p,l,r:longint):longint;//线段树区间求和
var
m,tmp:longint;
begin
if (SEGtree[p].l=l) and (SEGtree[p].r=r) then exit(SEGtree[p].sum);
PUshdown(p);
m:=(SEGtree[p].l+SEGtree[p].r) shr 1;
if r<=m then exit(SEGgetsum(p shl 1,l,r))
else
if m+1<=l then exit(SEGgetsum(p shl 1+1,l,r))
else
exit(SEGgetsum(p shl 1,l,m)+SEGgetsum(p shl 1+1,m+1,r));
end;
procedure chainadd(u,v,w:longint);//树上链加
var
fu,fv,li,ri:longint;
begin
while true do
begin
if Chain[u]=Chain[v] then
begin
li:=PIC[u];
ri:=PIC[v];
if li>ri then swap(li,ri);
SEGchange(1,li,ri,w);
exit;
end;
fu:=Chain[u];
fv:=Chain[v];
if Depth[father[fu]]<Depth[Father[fv]] then
begin
swap(u,v);
swap(fu,fv);
end;
li:=PIC[fu];
ri:=PIC[u];
SEGchange(1,li,ri,w);
u:=Father[fu];
end;
end;
function chainsum(u,v:longint):longint;//树上路径求和
var
fu,fv,li,ri,tmp:longint;
begin
tmp:=0;
while true do
begin
if Chain[u]=Chain[v] then
begin
li:=PIC[u];
ri:=PIC[v];
if li>ri then swap(li,ri);
inc(tmp,SEGgetsum(1,li,ri));
exit(tmp);
end;
fu:=Chain[u];
fv:=Chain[v];
if Depth[father[fu]]<Depth[father[fv]] then
begin
swap(u,v);
swap(fu,fv);
end;
li:=PIC[fu];
ri:=PIC[u];
inc(tmp,SEGgetsum(1,li,ri));
u:=Father[fu];
end;
end;
begin
read(n);//读入
for i:=1 to n do
begin
read(u,Value[i]);//u为其父亲，若为0则说明其为根节点，此处更新value
if u<>0 then ins(u,i)
else root:=i;
end;
DFS1(root,1);
DFS2(root,root);
top:=0;
DFS3(root);//三次DFS
Build(1,1,n);//建一棵线段树
read(q);
for i:=1 to q do//操作
begin
read(ifdo,u,v);
if ifdo=1 then
begin
read(w);
chainadd(u,v,w);//树上链加
end
else
begin
w:=chainsum(u,v);//树上路径求和
writeln(w);
end;
end;
end.
嗯代码有点丑——权当是做一下笔记吧。不过算是又明白了树链剖分的一个用途，也算是一个进步吧。