题目大意：
对一颗树上进行路径加减，然后询问单点的值。
思路分析：
简单的树链剖分模板题。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#pragma comment(linker,"/STACk:10240000,10240000")
#define maxn 50005
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
using namespace std;
int next[maxn<<1],to[maxn<<1],head[maxn],tot;//临界表
int pre[maxn],root[maxn],siz[maxn],son[maxn],w[maxn],dep[maxn],id;//原树的父亲 链上的根 siz 有最大siz的子树 重新分配的id 深度 getid中来计数的
int sum[maxn<<2],add[maxn<<2];//线段树变量
int n;
void init()
{
pre[1]=0;
dep[1]=0;
tot=0;id=0;
memset(head,0,sizeof head);
memset(sum,0,sizeof sum);
memset(add,0,sizeof add);
}
void addedge(int u,int v)
{
tot++;
next[tot]=head[u];
to[tot]=v;
head[u]=tot;
}
void dfs(int now)
{
son[now]=0;
siz[now]=1;
for(int p =head[now]; p ; p=next[p])
{
int t=to[p];
if(t!=pre[now])
{
pre[t]=now;
dep[t]=dep[now]+1;
dfs(t);
if(siz[t]>siz[son[now]])son[now]=t;
siz[now]+=siz[t];
}
}
}
void getid(int now,int rt)
{
w[now]=++id;
root[now]=rt;
if(son[now])getid(son[now],rt);
for(int p = head[now] ; p ; p=next[p])
{
int t=to[p];
if(t!=son[now]&&t!=pre[now])
getid(t,t);
}
}
void pushdown(int num,int s,int e)
{
if(add[num])
{
int mid=(s+e)>>1;
sum[num<<1]+=(mid-s+1)*add[num];
sum[num<<1|1]+=(e-mid)*add[num];
add[num<<1]+=add[num];
add[num<<1|1]+=add[num];
add[num]=0;
}
}
void update(int num,int s,int e,int l,int r,int val)
{
if(l<=s && r>=e)
{
sum[num]+=(e-s+1)*val;
add[num]+=val;
return;
}
pushdown(num,s,e);
int mid=(s+e)>>1;
if(l<=mid)update(lson,l,r,val);
if(r>mid)update(rson,l,r,val);
}
int query(int num,int s,int e,int pos)
{
if(s==e)return sum[num];
pushdown(num,s,e);
int mid=(s+e)>>1;
if(pos<=mid)return query(lson,pos);
else return query(rson,pos);
}
void work(int x,int y,int val)
{
while(root[x]!=root[y])
{
if(dep[root[x]]<dep[root[y]])swap(x,y);
update(1,1,n,w[root[x]],w[x],val);
x=pre[root[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,1,n,w[x],w[y],val);
}
int save[maxn];
int main()
{
int m,Q;
while(scanf("%d%d%d",&n,&m,&Q)!=EOF)
{
init();
for(int i=1;i<=n;i++)
scanf("%d",&save[i]);
for(int i=1;i<=m;i++)
{
int s,e;
scanf("%d%d",&s,&e);
addedge(s,e);
addedge(e,s);
}
dfs(1);
getid(1,1);
for(int i=1;i<=n;i++)
update(1,1,n,w[i],w[i],save[i]);
char str[5];
while(Q--)
{
scanf("%s",str);
if(str[0]=='I')
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
work(a,b,c);
}
else if(str[0]=='D')
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
work(a,b,-c);
}
else
{
int a;
scanf("%d",&a);
printf("%d\n",query(1,1,n,w[a]));
}
}
}
return 0;
}
Hdu 3699 Aragorn's Story (树链剖分),布布扣,bubuko.com
Hdu 3699 Aragorn's Story (树链剖分)
原文：http://blog.csdn.net/u010709592/article/details/38713067