三种操作：
I. CHANGE u t : 把结点u的权值改为t
II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值
III. QSUM u v: 询问从点u到点v的路径上的节点的权值和
简单树剖w（天天刷水的(1e3+7)）
其实就是树剖板子多配一个线段树维护区间最值
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define MAXN 30233
int n,m,r;
int tot=0,cnt=0;
int ans[MAXN<<2],umax[MAXN<<2];
struct qwq
{
int nex,to;
}e[MAXN<<1];
int h[MAXN];
int w1[MAXN],w2[MAXN];
int dep[MAXN],top[MAXN],siz[MAXN],fa[MAXN],id[MAXN],son[MAXN];
void add(int x,int y)
{
e[++tot].to=y;
e[tot].nex=h[x];
h[x]=tot;
}
//dfs_str
inline void dfs1(int x,int f,int dept)
{
dep[x]=dept;
fa[x]=f;
siz[x]=1;
int mx=-1;
for (int i=h[x],y;i;i=e[i].nex)
{
y=e[i].to;
if (y==f) continue;
dfs1(y,x,dept+1);
siz[x]+=siz[y];
if (siz[y]>mx)
{
son[x]=y;
mx=siz[y];
}
}
}
inline void dfs2(int x,int ft)
{
id[x]=++cnt;
w2[cnt]=w1[x];
top[x]=ft;
if (!son[x]) return;
dfs2(son[x],ft);
for (int i=h[x],y;i;i=e[i].nex)
{
y=e[i].to;
if (y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
//dfs_end.
//segment_tree
#define inf -2000000000
#define mid ((l+r)>>1)
#define leftson cur<<1
#define rightson cur<<1|1
#define push_up umax[cur]=max(umax[leftson],umax[rightson]); ans[cur]=ans[leftson]+ans[rightson]
inline void build(int cur,int l,int r)
{
if (l==r)
{
umax[cur]=ans[cur]=w2[l];
return;
}
build(leftson,l,mid);
build(rightson,mid+1,r);
push_up;
}
inline void change(int cur,int l,int r,int qcur,int del)
{
if (l==r)
{
ans[cur]=umax[cur]=del;
return;
}
if (qcur<=mid) change(leftson,l,mid,qcur,del);
else change(rightson,mid+1,r,qcur,del);
push_up;
}
inline int queryans(int cur,int l,int r,int ql,int qr)
{
if (ql<=l&&r<=qr)
{
return ans[cur];
}
int answ=0;
if (ql<=mid) answ+=queryans(leftson,l,mid,ql,qr);
if (qr>mid) answ+=queryans(rightson,mid+1,r,ql,qr);
push_up;
return answ;
}
inline int querymax(int cur,int l,int r,int ql,int qr)
{
if (ql<=l&&r<=qr)
{
return umax[cur];
}
int answ=inf;
if (ql<=mid) answ=max(answ,querymax(leftson,l,mid,ql,qr));
if (qr>mid) answ=max(answ,querymax(rightson,mid+1,r,ql,qr));
push_up;
return answ;
}
//seg_tree_end.
int query_ans(int x,int y)
{
int answ=0;
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
answ+=queryans(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
answ+=queryans(1,1,n,id[x],id[y]);
return answ;
}
int query_max(int x,int y)
{
int answ=inf;
// printf("qwq1
");
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
// printf("qwq2
");
answ=max(answ,querymax(1,1,n,id[top[x]],id[x]));
// printf("
::::::%d %d
",id[top[x]],id[x]);
// printf("qwq3
");
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
answ=max(answ,querymax(1,1,n,id[x],id[y]));
// printf(":::qwqwqwqwqwq::;%d %d
",id[x],id[y]);
return answ;
}
int main()
{
scanf("%d",&n);
for (int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for (int i=1;i<=n;i++)
{
scanf("%d",&w1[i]);
}
dfs1(1,1,1); dfs2(1,1);
build(1,1,n);
/* for (int i=1;i<=n;i++)
{
printf("%d ",id[i]);
}
printf("
");*/
int q;
scanf("%d",&q);
string s;
int x,y;
// printf("
:qwq:: %d
",querymax(1,1,n,2,4));
while (q--)
{
cin>>s;
scanf("%d%d",&x,&y);
if (s[1]=='H')
{
change(1,1,n,id[x],y);
// printf("：：：：：：：：：：：：%d
",id[x]);
continue;
}
if (s[1]=='M')
{//printf("qwq????
");
printf("%d
",query_max(x,y));
continue;
}
printf("%d
",query_ans(x,y));
}
return 0;
}
自我吐槽：写完整(leftson)和(rightson)（似乎别人一般写ls/rs/lson/rson）的线段树，以及大片宏定义，加上毒瘤递归(inline)，这(segment-tree)码风可能永远改不掉了（写的很舒服）