Snacks

题目链接：

dfs序+线段树

这道题涉及到对整棵树的值修改，考虑将树状结构用dfs序转化成线性结构，将树的修改转化为区间修改以降低时间复杂度（之前组队赛的时候遇到一道类似的没调出来...代码能力太缺乏了...）

代码如下：

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #pragma comment(linker, "/STACK:1024000000,1024000000")  6 #define LL long long  7 #define N 100100  8 #define lson (x<<1)  9 #define rson (x<<1|1) 10 #define mid ((l+r)>>1) 11 using namespace std; 12 struct node{ 13     LL sum,lazy; 14 }a[N<<2]; 15 LL val[N]; 16 int L[N],R[N]; 17 LL spre[N]; 18 int index; 19 bool vis[N]; 20 vector
         
          e[N]; 21 void init(){ 22     //for(int i=0;i