题目传送门：

　　这道题已经攒了半年多了。。。因为懒，一直没去写。。。所以今天才把这道题写出来。。。

　　如果是要维护区间权值和、子树权值和，都可以用线段树/树状数组轻松解决。但是这道题要维护的是子树权值和的区间和，这就比较难搞了。

　　当需要维护一些看起来很难直接维护的信息时，我们一般会想到分块。于是考虑这样的分块：按编号把每√n个节点划分为一块，维护每一块所有节点的sum值的和，然后再维护每个节点的sum值。单节点的sum可以用树状数组/线段树维护，但为了降低时间复杂度，我们可以用分块维护dfs序的区间和的前缀和，这样的单节点修改复杂度为O(√n)，单节点查询复杂度为O(1)。

　　时间复杂度：修改操作O(√n)，查询操作O(√n)，总时间复杂度O((n+m)√n)。

　　具体实现细节：维护第一层分块（即sum值的和）时可以在dfs遍历树时一个数组记录每个节点修改时对每个块的贡献，然后修改时直接统计贡献修改块的值就行了；第二层分块（即单节点的sum）时可以分别维护块的前缀和与每个节点在所在块内的前缀和，查询时把两部分加起来就行了。

　　另外，答案要开unsigned long long！

　　代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #define ll long long#define ull unsigned long long#define max(a,b) (a>b?a:b)#define min(a,b) (a