http://www.lydsy.com/JudgeOnline/problem.php?id=4765
很nice的一道题啊（可能是因为卡了n久终于做出来了
题意就是给你一棵带点权的有根树，sum(i)表示以i为根的这颗子树中所有节点的权值和。有两种操作，一种是修改某个点的权值，另一种是给出l,r,求sum(l)+sum(l+1)...+sum(r)。
首先考虑一个简单的问题，如果单求其中一个sum(i)，我们可以怎样做。
很明显我们画个图，我们可以看到每个点打上dfs序之后，每个sum就变成了一个区间，那就是单点更新，区间求和了，树状数组可以很好的解决掉。
那现在我们要解决原问题了，因为没学过树套树的玩意，所以我觉得有了上面那个东西之后，是不是可以用树套树来搞呢，查了好久，没发现什么资料，也不知道能不能搞，反正我是不会了= =，然后就尝试莫队的东西，发现更新我也不会啊，于是就傻逼了。
对大佬说了很多傻逼想法然后全被自己否决了，比如说分块一下sum啊（然而这个我自己否决了的就是最后A掉的做法），或者是，之后，突然感觉有几个不可行的合起来好像复杂度很对啊。再瞎画一下，得出了个想法。
就是上面说的分块一下sum，分块，看起来复杂度很支持啊，但是我们要考虑到，修改一个点，会使得很多个sum发生改变，我一开始否决就是把这里的复杂度算错了。那其实这里我们可以用一个贡献一样的数组来求，gx[i][j]表示修改j对第i块会产生多大影响（就是说j在第i块出现过几次），这个只需要nsqrtn就可以求出来。一开始我以为要n^2？？？我别是*吧！
但是除了整块之外的，还有其它那些，这里我们就暴力用树状数组同时维护起来，于是整体复杂度就变成了优美的nsqrtnlogn！
回忆一下貌似自己想到简化的那个问题之后，就不应该想其他东西啊，来个暴力分块就好了，不过还好总算是A掉了，另外此题答案爆longlong。。
/**************************************************************
Problem: 4765
User: caobao
Language: C++
Result: Accepted
Time:13716 ms
Memory:136396 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <time.h>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
#define MP make_pair
#define PB push_back
#define ms(a,b) memset((a),(b),sizeof(a))
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> Pii;
typedef vector<int> Vi;
typedef vector<Pii> Vii;
const int inf = 0x3f3f3f3f;
const LL INF = (1uLL << ) - ;
const LL mod = ;
const int N = + ;
const double Pi = acos(-1.0);
const int maxn = ;
int head[maxn];
int w[maxn];
int bl[maxn];
uLL Vsum[];
int tol;
int g;
int n, m;
int root;
int sz;
struct Edge {
int to, nx;
} edge[maxn << ];
void init() {
memset(head, -, sizeof head);
}
inline void add_edge(int u, int v) {
edge[tol].to = v;
edge[tol].nx = head[u];
head[u] = tol++;
}
inline int lowbit(int x) {
return x & (-x);
}
inline void OT(uLL x) {
if(x > ) {
OT(x / );
}
putchar(x % + '');
}
uLL tree[maxn];
struct Ds {
int l, r;
} S[maxn];
inline uLL sum(int pos) {
uLL res = ;
for(; pos; pos -= lowbit(pos))res += tree[pos];
return res;
}
inline void fix(int pos, uLL x) {
x = x - sum(pos) + sum(pos - );
for(; pos < maxn; pos += lowbit(pos))tree[pos] += x;
}
void dfs(int u, int fa) {
S[u].l = ++g;
for(int i = head[u]; ~i; i = edge[i].nx) {
int v = edge[i].to;
if(v == fa)continue;
dfs(v, u);
}
S[u].r = g;
}
int line[maxn + ];
int gx[][maxn];
inline int id(int x) {
return S[x].l;
}
inline void udate(int pos, uLL x) {
fix(id(pos), x);
uLL add = x - w[pos];
w[pos] = x;
for(int i = ; i <= bl[n]; i++) {
Vsum[i] += gx[i][id(pos)] * add;
}
}
inline uLL ask(int l, int r) {
uLL res = ;
if(bl[l] == bl[r]) {
for(int i = l; i <= r; i++) {
res += sum(S[i].r) - sum(S[i].l - );
}
return res;
}
for(int i = l; bl[i] == bl[l]; i++) {
res += sum(S[i].r) - sum(S[i].l - );
}
for(int i = bl[l] + ; i < bl[r]; i++) {
res += Vsum[i];
}
for(int i = (bl[r] - ) * sz + ; i <= r; i++) {
res += sum(S[i].r) - sum(S[i].l - );
}
return res;
}
int main() {
#ifdef local
freopen("in", "r", stdin);
// freopen("w","w",stdout);
#endif
//ios::sync_with_stdio(false);
// cin.tie(0);
init();
scanf("%d%d", &n, &m);
sz = sqrt(n);
for(int i = ; i <= n; ++i)scanf("%d", &w[i]);
for(int i = ; i <= n; ++i) {
bl[i] = (i - ) / sz + ;
}
for(int i = ; i < n; ++i) {
int a, b;
scanf("%d%d", &a, &b);
if(a)add_edge(a, b), add_edge(b, a);
else root = b;
}
dfs(root, -);
for(int i = ; i <= n; ++i)fix(S[i].l, w[i]);
for(int i = ; i <= bl[n]; ++i) {
memset(line, , sizeof line);
for(int j = (i - ) * sz + ; j <= min(i * sz , n); j++) {
line[S[j].l]++, line[S[j].r + ]--;
Vsum[i] += sum(S[j].r) - sum(S[j].l - );
}
int tmp = ;
for(int j = ; j < maxn; j++) {
tmp += line[j];
gx[i][j] = tmp;
}
}
for(int i = ; i < m; i++) {
int d, l, r;
scanf("%d%d%d", &d, &l, &r);
if(d == ) {
udate(l, r);
} else OT(ask(l, r)), putchar('\n');
}
}
-------另外，发现数据的修改权值都是往大修改的，因为里面修改的时候，我传得都是uLL，但ac，懒得改了，看的人注意就可以了。-------