Description
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
Input
第一行包含两个整数 N, M 。表示点数和操作数。
接下来一行 N 个整数，表示树中节点的初始权值。
接下来 N-1 行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。
再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操
作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ）
Output
对于每个询问操作，输出该询问的答案。答案之间用换行隔开
HINT
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不会超过 10^6 。
很久没有写过树剖了……找个板子题出来熟悉一下。
树链剖分可以把树上的问题转化为序列上的问题，然后就可以用线段树等数据结构维护了。像这种不需要标记的区间修改、求值直接用树状数组就可以了。
贴一个板子：
#include#include #include #include #include #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)#define maxn 100010using namespace std;typedef long long llg;int n,m,a[maxn],le[maxn],ri[maxn];int head[maxn],to[maxn<<1],next[maxn<<1],tt;int fa[maxn],top[maxn],siz[maxn],son[maxn],fc[maxn];llg c1[maxn],c2[maxn];int getint(){ int w=0;bool q=0; char c=getchar(); while((c>'9'||c<'0')&&c!='-') c=getchar(); if(c=='-') c=getchar(),q=1; while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;}void link(int x,int y){ to[++tt]=y;next[tt]=head[x];head[x]=tt; to[++tt]=x;next[tt]=head[y];head[y]=tt;}inline void add(int x,int y){for(int i=x;i<=n;i+=i&(-i)) c1[i]+=y,c2[i]+=(llg)x*y;}inline llg sum(int x){ llg ans(0); for(int i=x;i;i-=i&(-i)) ans+=(llg)(x+1)*c1[i]-c2[i]; return ans;}void dfs(int u){ siz[u]=1; for(int i=head[u],v;v=to[i],i;i=next[i]) if(v!=fa[u]){ fa[v]=u; dfs(v); siz[u]+=siz[v]; if(siz[v]>siz[son[u]]) son[u]=v; }}void dfs(int u,int dd){ top[u]=dd; le[u]=fc[u]=++tt; add(tt,a[u]),add(tt+1,-a[u]); if(son[u]) dfs(son[u],dd); for(int i=head[u],v;v=to[i],i;i=next[i]) if(!top[v]) dfs(v,v); ri[u]=tt;}llg work(int u){ llg ans=0; while(u){ int L=fc[top[u]],R=fc[u]; ans+=sum(R)-sum(L-1); u=fa[top[u]]; } return ans;}int main(){ File("a"); n=getint(); m=getint(); for(int i=1;i<=n;i++) a[i]=getint(); for(int i=1;i