题目描述

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：操作 1 ：把某个节点 x 的点权增加 a 。操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

输入输出格式

输入格式：

第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值。接下来 N-1 行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。

输出格式：

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

输入输出样例

5 51 2 3 4 51 21 42 32 53 31 2 13 52 1 23 3

6913

说明

对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不

会超过 10^6 。

吐槽

　　今晚真是填坑之夜呀！一连填了3个一个月以上的老坑！

　　这题和我上一篇博文说的悲惨程度差不多——

　　是的，你没有看错，还有[Next Page]这种东西……5月初我就开始做这题了……

　　人越急越写不出东西，所以遇到某些题卡住了，可以搁置一下，过段时间再来写，但是如果第二次冷静下来还是写错，那么就是脑子里的东西错了……

　　我观察洛谷给的错误情况，除了CE之类的，剩下的错误都是在50行以后，这说明我写的程序的持久性出了问题(不是可持久，是持久)，一些维护修改的东西出错了。

　　　　树剖方面

　　　　　　两个dfs第一次调用之后就不再用它了，还有询问时opt3轻重链向上跳的过程，前50个询问都能处理的挺好，不太可能出问题。

　　　　　　就剩修改操作了，opt1和opt2两个函数里都只有一句话，反复检查没有问题我为什么一句话都要反复检查……，于是bug被限定到了线段树部分——

　　　　线段树方面

　　　　　　首先是建树，按照dfs序获取轻重链相连组成的序列是在树剖的dfs2部分实现的，获取序列a之后maketree只调用了一次，建出来的线段树毕竟也坚持了50个询问，基本排除出bug的可能。

　　　　　　然后是含有修改的一堆函数，极有可能出bug。询问函数query，表面上不修改线段树，但是其中有一个pushdown啊，可能出错；更新函数change，这个就直接是更改线段树啊！高危！最后是前面两者都调用了的pushdown，简简单单6行，好像没毛——不对，前天写这题的时候，它的双lazy和我预想的不太一样啊，嗯，极危！先从它查起！

　　大概确定了出bug范围，剩下的就好搞了，直接找原来写的模板对比。

　　（一段时间后）

　　”他丫的我半年前学的线段树lazy是假的，更重要的是我还用它A了不知道多少水题，越错越深，查错时完全忽略了这里……“

　　我就不把错误的pushdown放上来误导大家了。

　　非常兴奋地改了这里，迫不及待地交了上去，50分。我居然忘了加long long！为了省事。大家在我的代码开头可以看到一个神奇的define……

解题思路

　　就是裸的树剖，可以看。

　　这题的询问比较方便跳链，于是我偷了个小懒，opt3没套模板，做了个小优化，省时省力。

源代码

#include
     
      #include
      
       #include
       
        #define int long long using namespace std;int n,m;struct Edge{    int next,to;}e[200010];int cnt=1,head[100010]={
   0};void add(int u,int v){    e[cnt]={head[u],v};    head[u]=cnt++;}struct Tree{    int w;    int fa;    vector
        
          son;    int num_to;    int wson;    int top;    int id;}t[100010];long long a[100010]={
   0};int dfs1(int fa,int u){    t[u].fa=fa;    t[u].num_to=1;    for(int i=head[u],maxn=-1;i;i=e[i].next)    {        int v=e[i].to;        if(v==fa) continue;        t[u].son.push_back(v);        int temp=dfs1(u,v);        t[u].num_to+=temp;        if(temp>maxn)        {            maxn=temp;            t[u].wson=v;        }    }    return t[u].num_to;}int id=1;void dfs2(int top,int u){    t[u].top=top;    t[u].id=id;    a[id]=t[u].w;    int sz=t[u].son.size();    if(!sz)        return;    id++;    dfs2(top,t[u].wson);    for(int i=0;i
         
          >1;    maketree(node<<1,l,mid);    maketree(node<<1|1,mid+1,r);    s[node]={l,r,s[node<<1].sum+s[node<<1|1].sum};}void change(int x,int l,int r,int k){    if(r