题目意思很明白：
给你一棵有n个节点的树，对树有下列操作：
I c1 c2 k 意思是把从c1节点到c2节点路径上的点权值加上k
D c1 c2 k 意思是把从c1节点到c2节点路径上的点权值减去k
Q a 查询节点a的权值
数据大小 节点个数 n[1,50000], 操作次数 op[0,30000];
不会树链剖分 故只有想其他的方法。
这道题有点类似今年上海网络赛的1003 ，不过那题我没做；
算法思路：
以节点1 为根，求出节点i 的 dfs序列 tim[i][2];
其中tim[i][0]存的是进入节点i的时间 ，tim[i][1]存的是离开节点i的时间
看操作： I a b k， 节点a到b的路径上所有点+k；最朴素的算法首先找到他们的最近公共祖先（LCA）（我用RMQ）写的；然后在路径上的每一个节点都+k；
假设树根是1
从a到树根的每一个节点x都满足tim[x][0]<=tim[a][0]<=tim[x][1];如此 如果引入一个数列nt，如果nt（tim[a][0]）+=k,那么 nt数列从tim[x][0]到tim[x][1]项的和就加了k，这就相当于把从a到根节点的每一个节点的权值加上了k；
如果节点x不在a到根的路径上呢？那么只有可能是tim[x][0]>tim[a][0] or tim[x][1]<tim[a][0] 故上面的这种做法对其他的点没有影响
根据这种思路 ，那解法就相对简单了：
加上差分数列的思想
a b的LCA是t，把 a b节点都加上k，然后把t的父节点-2；当然 t节点是加了两遍的 所以需要减去一遍 也就是把t节点-1，父节点当然也要+1了
如果有了dfs序，就可以很清晰的看出来 如果一个节点x在这条路径上 那么tim[x][0]<=one of (tim[a][0],tim[b][0])<=tim[x][1];
附上代码渣渣：
// hdu 3966
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<stdlib.h>
#include <vector>
using namespace std; #define ll __int64
#define CL(a,b) memset(a,b,sizeof(a))
#define MAX_NODE 50010 int n,m,q; int log_2(int x)
{
return (int)(log((double)x)/log(2.0));
} int tim[MAX_NODE][],ti;
int rmq[MAX_NODE*][],cq,fv[MAX_NODE];
int pre[MAX_NODE];
int value[]; typedef struct myedge
{
int v,next;
}E; E edge[];
int head[],ce; void inithead()
{
CL(head,-);
ce=;
}
void addedge(int s,int e)
{
edge[ce].v=e;edge[ce].next=head[s];head[s]=ce++;
edge[ce].v=s;edge[ce].next=head[e];head[e]=ce++;
} void initrmq()
{
int i,j;
for(j=;(<<j)<=cq;j++)
{
for(i=;i+(<<j)-<=cq;i++)
{
rmq[i][j]=min(rmq[i][j-],rmq[i+(<<(j-))][j-]);
}
}
}
int quermq(int s,int e)
{
int i=log_2(e-s+);
return min(rmq[s][i],rmq[e-(<<i)+][i]);
} ll nt[]; int lowbit(int i)
{
return i&(-i);
} void modify(int i,ll v)
{
if(i==)return ;
for(i;i<=n;i+=lowbit(i))
{
nt[i]+=v;
}
} ll sum(int i)
{
ll rem=;
for(i;i>;i-=lowbit(i))
rem+=nt[i];
return rem;
} int dfs(int i,int pr)
{
ti++;
tim[i][]=ti;
// cout<<i<<" tim "<<ti<<endl;
rmq[++cq][]=tim[i][];
fv[i]=cq;
pre[ti]=pr;
int p=head[i];
while(p!=-)
{
int v=edge[p].v;
if(tim[v][]==)
{
dfs(v,tim[i][]);
rmq[++cq][]=tim[i][];
}
p=edge[p].next;
}
tim[i][]=ti;
return ;
} void inc(int s,int e,int k)
{
int rs=fv[s];
int re=fv[e];
int rt=quermq(min(rs,re),max(rs,re));
re=tim[e][];
rs=tim[s][];
// cout<<rs<<' '<<re<<' '<<rt<<' '<<pre[rt]<<endl;
if(s==e)
{
value[s]+=k;
return ;
}
modify(rs,k);
modify(re,k);
modify(rt,-k);
modify(pre[rt],-k);
} void dec(int s,int e,int k)
{
k=-k;
int rs=fv[s];
int re=fv[e];
int rt=quermq(min(rs,re),max(rs,re));
re=tim[e][];
rs=tim[s][];
if(s==e)
{
value[s]+=k;
return ;
}
modify(rs,k);
modify(re,k);
modify(rt,-k);
modify(pre[rt],-k);
} ll que(int k)
{
int rl=tim[k][];
int rr=tim[k][];
// cout<<rl<<' '<<rr<<endl;
return (ll)value[k]+sum(rr)-sum(rl-);
} char op[]; int main()
{
while(scanf("%d %d %d",&n,&m,&q)!=EOF)
{
CL(nt,);
CL(rmq,);cq=;
CL(fv,);
CL(pre,);
CL(tim,);ti=;
inithead();
int i,j,k;
int a,b,c;
for(i=;i<=n;i++)
{
scanf("%d",value+i);
}
for(i=;i<n;i++)
{
scanf("%d %d",&a,&b);
addedge(a,b);
}
dfs(,);
/*
for(i=1;i<=cq;i++)
{
printf("%d ",rmq[i][0]);
}cout<<endl;
*/
initrmq();
for(i=;i<q;i++)
{
scanf("%s",op);
if(op[]=='I')
{
scanf("%d %d %d",&a,&b,&c);
inc(a,b,c);
}
else if(op[]=='D')
{
scanf("%d %d %d",&a,&b,&c);
dec(a,b,c);
}
else if(op[]=='Q')
{
scanf("%d",&a);
printf("%I64d\n",que(a));
}
} } return ;
}