树链剖分，点权，单点更改，路径查询。学树链剖分下面这个博文不错
http://blog.csdn.net/y990041769/article/details/40348013
线段树必须写的很熟练才行。注意负数
#include <cstdio>
#include <vector>
#include <algorithm> using namespace std; const int maxn = 3e4+;
const int INF = 0x3f3f3f3f; /////////////////////////////////////
int topw;
int son[maxn],top[maxn],fa[maxn],siz[maxn],id[maxn],dep[maxn];
int val[maxn],pre_val[maxn]; vector<int> G[maxn]; void dfs_1(int u,int f,int d)
{
son[u] = ;
dep[u] = d;
fa[u] = f;
siz[u] = ;
for(int i=;i<G[u].size();i++)
{
int v = G[u][i];
if(v == f) continue;
dfs_1(v,u,d+);
siz[u] += siz[v];
if(siz[son[u]] < siz[v])
{
son[u] = v;
}
}
} void dfs_2(int u,int tp)
{
top[u] = tp;
id[u] = ++topw;
if(son[u]) dfs_2(son[u],tp);
for(int i=;i<G[u].size();i++)
{
int v = G[u][i];
if(v == fa[u] || v == son[u]) continue;
dfs_2(v,v);
}
} ////////////////////////////////////
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define root 1,topw,1 int sum[maxn<<];
int mx[maxn<<]; void push_up(int rt)
{
sum[rt] = sum[rt<<]+sum[rt<<|];
mx[rt] = max(mx[rt<<],mx[rt<<|]);
} void build(int l,int r,int rt)
{
sum[rt] = ;
mx[rt] = ;
if(l == r)
{
sum[rt] = val[l];
mx[rt] = val[l];
return ;
}
int m = (l+r)>>;
build(lson);
build(rson);
push_up(rt);
} void update(int pos,int add,int l,int r,int rt)
{
if(l == r)
{
sum[rt] = add;
mx[rt] = add;
return ;
}
int m = (l+r)>>;
if(pos <= m) update(pos,add,lson);
else update(pos,add,rson);
push_up(rt);
} int query_sum(int L,int R,int l,int r,int rt)
{
if(L <= l && R >= r)
{
return sum[rt];
}
int m = (l+r)>> , ans = ;
if(L <= m) ans += query_sum(L,R,lson);
if(R > m) ans += query_sum(L,R,rson);
return ans;
} int query_max(int L,int R,int l,int r,int rt)
{
if(L <= l && R >= r)
{
//printf("[%d,%d] rt:%d mx:%d\n",l,r,rt,mx[rt]);
return mx[rt];
}
int m = (l+r)>> , ans = -INF;
if(L <= m) ans = max(ans,query_max(L,R,lson));
if(R > m) ans = max(ans,query_max(L,R,rson));
return ans;
} int Find_sum(int u,int v)
{
int fu = top[u],fv = top[v];
int ans = ;
while(fu != fv)
{
//printf("ans:%d %d %d %d %d\n",ans,u,fu,v,fv);
if(dep[fu] < dep[fv])
{
swap(u,v);
swap(fu,fv);
}
ans += query_sum(id[fu],id[u],root);
u = fa[fu];
fu = top[u];
}
if(u == v)
{
return ans+query_sum(id[u],id[v],root);
}
else{
if(dep[u] < dep[v]) swap(u,v);
return ans+query_sum(id[v],id[u],root);
}
} int Find_max(int u,int v)
{
int fu = top[u],fv = top[v];
int ans = -INF;
while(fu != fv)
{
if(dep[fu] < dep[fv])
{
swap(u,v);
swap(fu,fv);
}
//printf("ans:%d %d %d %d %d\n",ans,u,fu,v,fv);
//printf("q:%d\n",query_max(id[fu],id[u],root));
ans = max(ans,query_max(id[fu],id[u],root));
u = fa[fu];
fu = top[u];
}
if(u == v)
{
return max(ans,query_max(id[u],id[v],root));
}
else{
if(dep[u] < dep[v]) swap(u,v);
return max(ans,query_max(id[v],id[u],root));
}
} ////////////////////////////////////////// int N,Q;
int main()
{
freopen("input.in","r",stdin);
while(~scanf("%d",&N))
{
for(int i=,u,v;i<N;i++)
{
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=;i<=N;i++) scanf("%d",&pre_val[i]);
topw = ;
dfs_1(,,);
dfs_2(,);
for(int i=;i<=N;i++) val[id[i]] = pre_val[i];
build(root); scanf("%d",&Q);
char op[];
int a,b;
while(Q--)
{
scanf("%s%d%d",op,&a,&b);
if(op[] == 'Q')
{
if(op[] == 'M')
{
printf("%d\n",Find_max(a,b));
}else
{
printf("%d\n",Find_sum(a,b));
}
}else
{
update(id[a],b,root);
}
}
for(int i=;i<=N;i++) G[i].clear();
}
}