测试地址：Aragorn's Story
题目大意：有一棵树，树上每个点有一个权值，要求支持以下操作：1.将某两点之间路径上的点权值增加（或减少）一个数；2.询问某点的权值。
做法：这题用树链剖分做，就是很简单的区间修改裸题了，这里不再赘述。
而用LCT做虽然也是挺裸的，但是由于我是小白，所以一开始路径修改的时候想错了，以为是求个LCA然后乱搞......然后突然醒悟：这可是动态树啊！完全可以makeroot其中一个点，然后access另一个点，再进行修改不就很简单了吗？其他操作没什么可讲的，注意维护信息即可。要维护以下几个信息：修改时打的临时标记，翻转标记，以及这个点的权值，在这道题目中就没有必要维护区间和了。
以下是本人代码：
树链剖分（2016.7.31）：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,m,p,a[50010],x,y,d,k,tot;
int first[50010],f[50010],siz[50010],son[50010],dep[50010];
int pos[50010],qpos[50010],top[50010];
long long seg[200010],c[200010];
char op;
struct {int v,next;} e[100010];
void insert(int x,int y)
{
e[++tot].v=y;
e[tot].next=first[x];
first[x]=tot;
}
void dfs1(int v)
{
siz[v]=1;son[v]=0;
for(int i=first[v];i>0;i=e[i].next)
if (e[i].v!=f[v])
{
dep[e[i].v]=dep[v]+1;
f[e[i].v]=v;
dfs1(e[i].v);
if (siz[e[i].v]>siz[son[v]]) son[v]=e[i].v;
siz[v]+=siz[e[i].v];
}
}
void dfs2(int v,int chain)
{
pos[v]=++k;
qpos[k]=v;
top[v]=chain;
if (son[v]) dfs2(son[v],chain);
for(int i=first[v];i>0;i=e[i].next)
if (e[i].v!=f[v]&&e[i].v!=son[v])
dfs2(e[i].v,e[i].v);
}
void buildtree(int no,int l,int r)
{
int mid=(l+r)>>1;
if (l==r) {seg[no]=a[qpos[l]];return;}
buildtree(no<<1,l,mid);
buildtree((no<<1)+1,mid+1,r);
seg[no]=seg[no<<1]+seg[(no<<1)+1];
}
void add(int no,int l,int r,int s,int t,int a)
{
int mid=(l+r)>>1;
if (l>=s&&r<=t) {seg[no]+=a*(r-l+1);c[no]+=a;return;}
c[no<<1]+=c[no];c[(no<<1)+1]+=c[no];
seg[no<<1]+=c[no]*(mid-l+1);seg[(no<<1)+1]+=c[no]*(r-mid);
c[no]=0;
if (s<=mid) add(no<<1,l,mid,s,t,a);
if (t>mid) add((no<<1)+1,mid+1,r,s,t,a);
seg[no]=seg[no<<1]+seg[(no<<1)+1];
}
void modify(int x,int y,int val)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if (dep[fx]<dep[fy]) {swap(x,y);swap(fx,fy);}
add(1,1,n,pos[fx],pos[x],val);
x=f[fx];fx=top[x];
}
if (dep[x]>dep[y]) swap(x,y);
add(1,1,n,pos[x],pos[y],val);
}
long long query(int no,int l,int r,int x)
{
int mid=(l+r)>>1;
if (l==r) return seg[no];
c[no<<1]+=c[no];c[(no<<1)+1]+=c[no];
seg[no<<1]+=c[no]*(mid-l+1);seg[(no<<1)+1]+=c[no]*(r-mid);
c[no]=0;
if (x<=mid) return query(no<<1,l,mid,x);
else return query((no<<1)+1,mid+1,r,x);
}
int main()
{
siz[0]=0;
while(scanf("%d%d%d",&n,&m,&p)!=EOF)
{
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
f[1]=dep[1]=tot=k=0;
memset(first,0,sizeof(first));
memset(c,0,sizeof(c));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
insert(x,y);insert(y,x);
}
dfs1(1);
dfs2(1,1);
buildtree(1,1,n);
for(int i=1;i<=p;i++)
{
scanf("%c",&op);
while(op<'A'||op>'Z') scanf("%c",&op);
if (op=='I'||op=='D')
{
scanf("%d%d%d",&x,&y,&d);
if (op=='I') modify(x,y,d);
else modify(x,y,-d);
}
else
{
scanf("%d",&x);
printf("%lld
",query(1,1,n,pos[x]));
}
}
}
return 0;
}
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,q,ch[50010][2]={0},first[50010],pre[50010]={0},tot;
long long val[50010]={0},p[50010]={0},siz[50010]={0};
bool rt[50010]={0},rev[50010]={0};
struct edge {int v,next;} e[100010];
void insert(int a,int b)
{
e[++tot].v=b,e[tot].next=first[a],first[a]=tot;
}
void dfs(int v)
{
for(int i=first[v];i;i=e[i].next)
if (e[i].v!=pre[v])
{
pre[e[i].v]=v;
dfs(e[i].v);
}
}
void reverse(int x)
{
rev[x]^=1;
swap(ch[x][0],ch[x][1]);
}
void pushdown(int x)
{
if (p[x]!=0)
{
p[ch[x][0]]+=p[x];
p[ch[x][1]]+=p[x];
val[ch[x][0]]+=p[x];
val[ch[x][1]]+=p[x];
p[x]=0;
}
if (rev[x])
{
reverse(ch[x][0]);
reverse(ch[x][1]);
rev[x]=0;
}
}
void pushup(int x)
{
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
}
void update(int x,long long d)
{
p[x]+=d;
val[x]+=d;
}
void rotate(int x,bool f)
{
int y=pre[x];
ch[y][!f]=ch[x][f];
pre[ch[y][!f]]=y;
ch[x][f]=y;
if (!rt[y]) ch[pre[y]][ch[pre[y]][1]==y]=x;
else rt[y]=0,rt[x]=1;
pre[x]=pre[y];
pre[y]=x;
pushup(y);
}
void Push(int x)
{
if (!rt[x]) Push(pre[x]);
pushdown(x);
}
void Splay(int x)
{
Push(x);
while(!rt[x])
{
if (rt[pre[x]]) rotate(x,ch[pre[x]][0]==x);
else
{
int y=pre[x],z=pre[pre[x]];
bool f=(ch[z][1]==y);
if (ch[y][f]==x) rotate(y,!f),rotate(x,!f);
else rotate(x,f),rotate(x,!f);
}
}
pushup(x);
}
void access(int x)
{
int y=0;
do
{
Splay(x);
rt[ch[x][1]]=1,rt[ch[x][1]=y]=0;
pushup(x);
x=pre[y=x];
}while(x);
}
void makeroot(int x)
{
access(x);
Splay(x);
reverse(x);
}
void modify(int x,int y,long long d)
{
makeroot(x);
access(y);
Splay(y);
update(y,d);
}
long long query(int x)
{
access(x);
Splay(x);
return val[x];
}
int main()
{
while(scanf("%d%d%d",&n,&m,&q)!=EOF)
{
tot=0;
memset(first,0,sizeof(first));
for(int i=1;i<=n;i++)
{
scanf("%lld",&val[i]);
rt[i]=1;
ch[i][0]=ch[i][1]=pre[i]=p[i]=0;
siz[i]=1;
}
for(int i=1,a,b;i<n;i++)
{
scanf("%d%d",&a,&b);
insert(a,b),insert(b,a);
}
dfs(1);
for(int i=1;i<=q;i++)
{
char op[5];
int x,y;long long z;
scanf("%s",op);
if (op[0]=='I')
{
scanf("%d%d%lld",&x,&y,&z);
modify(x,y,z);
}
if (op[0]=='D')
{
scanf("%d%d%lld",&x,&y,&z);
modify(x,y,-z);
}
if (op[0]=='Q')
{
scanf("%d",&x);
printf("%lld
",query(x));
}
}
}
return 0;
}