第一道树的点分治。
感谢：
http://blog.csdn.net/u013368721/article/details/40887575
首先，找出原图的重心（最大子树大小最小的点（如果作为根）），去掉它后原图就分成了若干的森林，再在对应的森林中找出重心，递归这个过程（只有一个点时返回）。
这样，我们就可以根据重心的所属关系，建立出一棵树，显然原图的重心就是这颗树的重心，每个重心对应一些点（就是去掉该重心前，该重心联通块中的所有点）。
容易看出，因为每次选的是重心，所以树每次至少会分成两块（最坏情况），考虑我们根据重心所属关系建立出的树，最多有O(logn)层，每层找重心总的复杂度是O(n)（因为每层重心对应的点是O(n)级别的），所以建立这个关系是O(nlogn)的复杂度。
应前辈的称呼，我们就叫建立出的这颗很多重心的树为重心树。
对于这道题，我们可以给重心树的每个节点建立一个树状数组，树状数组下标为到重心的距离，值为点的权值，将重心对应的点都放到这个树状数组中（因为最大距离就是该重心对应的点数-1，所以树状数组的大小就设成该重心对应的点数），因为一层对应的所有重心对应的点数最多为O(n)，所以总共占用的空间为O(nlogn)。然后还要根据这个重心的不同子重心分开记录一下这个东西，用于去重。
#include <cstdio>
#include <vector>
#include <map>
#define N 100010
using namespace std; struct Stat {
int r, d, s;
Stat( int r, int d, int s ):r(r),d(d),s(s){}
};
struct Bit {
int n;
vector<int> vv;
void init( int n ) {
this->n = n;
vv.resize( n+ );
for( int t=; t<=n; t++ ) vv[t] = ;
}
void modify( int pos, int delta ) {
pos++;
for( int i=pos; i<=n; i+=i&-i )
vv[i]+=delta;
}
int query( int pos ) {
int rt = ;
pos++;
if( pos>n ) pos=n;
for( int i=pos; i; i-=i&-i )
rt += vv[i];
return rt;
}
}; int n, m;
vector<int> g[N];
vector<Stat> st[N];
map<int,Bit > bit[N];
int ww[N];
int vis[N], siz[N], anc[N], bac[N], dis[N];
int qu[N], beg, tail; void init( int n ) {
for( int i=; i<=n; i++ ) {
g[i].clear();
st[i].clear();
bit[i].clear();
vis[i] = false;
}
}
void build( int root ) {
qu[beg=tail=] = root;
anc[root] = root;
siz[root] = bac[root] = ;
while( tail>=beg ) {
int u=qu[beg++];
for( int t=; t<g[u].size(); t++ ) {
int v=g[u][t];
if( v==anc[u] || vis[v] ) continue;
qu[++tail] = v;
anc[v] = u;
siz[v] = bac[v] = ;
}
}
for( int i=tail; i; i-- ) {
int v=qu[i];
int u=anc[v];
siz[v]++;
siz[u]+=siz[v];
if( siz[v]>bac[u] ) bac[u]=siz[v];
}
for( int i=; i<=tail; i++ ) {
int u = qu[i];
if( siz[root]-siz[u]>bac[u] ) bac[u]=siz[root]-siz[u];
}
for( int i=; i<=tail; i++ ) {
int u = qu[i];
if( bac[u]<bac[root] ) root=u;
}
//---------------- found the core -------------------//
bit[root][].init( tail+ );
bit[root][].modify( , ww[root] );
st[root].push_back( Stat(root,,) );
vis[root] = true; anc[root] = root;
for( int t=; t<g[root].size(); t++ ) {
int sr = g[root][t];
if( vis[sr] ) continue;
qu[beg=tail=] = sr;
dis[sr] = ;
anc[sr] = root;
while( tail>=beg ) {
int u=qu[beg++];
for( int t=; t<g[u].size(); t++ ) {
int v=g[u][t];
if( vis[v] || v==anc[u] ) continue;
qu[++tail] = v;
dis[v] = dis[u]+;
anc[v] = u;
}
}
bit[root][sr].init( tail+ );
for( int i=; i<=tail; i++ ) {
int u=qu[i];
bit[root][].modify( dis[u], ww[u] );
bit[root][sr].modify( dis[u], ww[u] );
st[u].push_back( Stat(root,dis[u],sr) );
}
}
for( int t=; t<g[root].size(); t++ ) {
int v=g[root][t];
if( vis[v] ) continue;
build(g[root][t]);
}
}
void modify( int u, int d ) {
for( int t=; t<st[u].size(); t++ ) {
Stat &s = st[u][t];
bit[s.r][].modify( s.d, d );
if( s.s ) bit[s.r][s.s].modify( s.d, d );
}
}
int query( int u, int d ) {
int rt = ;
for( int t=; t<st[u].size(); t++ ) {
Stat &s = st[u][t];
if( d<s.d ) continue;
int v = bit[s.r][].query( d-s.d );
rt += v;
if( s.s ) {
v = bit[s.r][s.s].query( d-s.d );
rt -= v;
}
}
return rt;
} int main() {
while() {
if( scanf( "%d%d", &n, &m )!= ) return ;
init(n);
for( int i=; i<=n; i++ )
scanf( "%d", ww+i );
for( int i=,u,v; i<n; i++ ) {
scanf( "%d%d", &u, &v );
g[u].push_back( v );
g[v].push_back( u );
}
build();
for( int i=; i<=m; i++ ) {
char ch[];
int u, d;
scanf( "%s%d%d", ch, &u, &d );
if( ch[]=='!' ) {
modify( u, d-ww[u] );
ww[u] = d;
} else {
printf( "%d\n", query(u,d) );
}
}
}
}