题目链接：
https://www.lydsy.com/JudgeOnline/problem.php?id=1036
题目大意：
一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成
一些操作：
I. CHANGE u t : 把结点u的权值改为t
II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I
II. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身
思路：
树链剖分。
一直没看树链剖分，刚刚看了一下，发现不难，两个dfs预处理出轻重链，然后用线段树维护即可。
查询的时候用LCA查询。时间复杂度为两个log
推荐博文：https://www.cnblogs.com/George1994/p/7821357.html
模板：
struct edge
{
int next;//指向下一个节点
int u, v, w;
};
edge e[maxn];
int head[maxn], node;//node记录节点的数目，head[i]记录连接着i的第一条边
void addedge(int u, int v)
{
e[node].u = u;
e[node].v = v;
//e[node].w = w;
e[node].next = head[u];
head[u] = node++;
e[node].u = v;
e[node].v = u;
//e[node].w = w;
e[node].next = head[v];
head[v] = node++;
}
int siz[maxn];//以u为根节点的子树的结点个数
int top[maxn];//节点u所在链的顶端节点
int son[maxn];//节点u重儿子
int dep[maxn];//节点u的深度
int faz[maxn];//节点u的父节点
int tid[maxn];//节点u的dfs编号
int rnk[maxn];//rnk[i]表示dfs编号为i的原始编号
int cnt;//dfs序号
void init()
{
memset(head, -, sizeof(head));
node = ;
Mem(siz);
Mem(top);
memset(son, -, sizeof(son));
Mem(dep);
Mem(faz);
Mem(tid);
Mem(rnk);
cnt = ;
}
void dfs1(int u, int father, int depth)
{
// u当前节点 father 父节点 depth深度
dep[u] = depth;
faz[u] = father;
siz[u] = ;
for(int i = head[u]; i != -; i = e[i].next)
{
int v = e[i].v;
if(v != faz[u])
{
dfs1(v, u, depth + );
siz[u] += siz[v];//更新子树节点数目
if(son[u] == - || siz[v] > siz[son[u]])
son[u] = v;//更新重儿子
}
}
}
void dfs2(int u, int t)
{
//u当前节点 t起始的重节点
top[u] = t;
tid[u] = ++cnt;
rnk[cnt] = u;
if(son[u] == -)return;//不在重链上
dfs2(son[u], t);//将这条重链上的所有点设置成起始的重节点
for(int i = head[u]; i != -; i = e[i].next)
{
int v = e[i].v;
if(v != son[u] && v != faz[u])
{
dfs2(v, v);//v不是u的重儿子 也不是u的父节点 将v的top设置成自己 进一步递归
}
}
}
LCA的方法来查询：
int solve_sum(int x, int y)//LCA top加速
{
int ans = ;
int fx = top[x], fy = top[y];
while(fx != fy)
{
if(dep[fx] >= dep[fy])
{
//计算x到其链的起点的路径和
ans += query_sum(, tid[fx], tid[x]);
//将x设置成起始节点的父节点，走轻边，继续循环
x = faz[fx];
}
else
{
ans += query_sum(, tid[fy], tid[y]);
y = faz[fy];
}
fx = top[x], fy = top[y];
}
//此时x和y在同一条重链上
if(tid[x] <= tid[y])ans += query_sum(, tid[x], tid[y]);
else ans += query_sum(, tid[y], tid[x]);
return ans;
}
题目完整代码：
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);//不可再使用scanf printf
#define Max(a, b) ((a) > (b) ? (a) : (b))//禁用于函数，会超时
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Mem(a) memset(a, 0, sizeof(a))
#define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1))
#define MID(l, r) ((l) + ((r) - (l)) / 2)
#define lson ((o)<<1)
#define rson ((o)<<1|1)
#pragma comment(linker, "/STACK:102400000,102400000")//栈外挂
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} typedef long long ll;
const int maxn = + ;
const int mod = ;//const引用更快，宏定义也更快
const int INF = 1e9; struct edge
{
int next;//指向下一个节点
int u, v, w;
};
edge e[maxn];
int head[maxn], node;//node记录节点的数目，head[i]记录连接着i的第一条边
void addedge(int u, int v)
{
e[node].u = u;
e[node].v = v;
//e[node].w = w;
e[node].next = head[u];
head[u] = node++;
e[node].u = v;
e[node].v = u;
//e[node].w = w;
e[node].next = head[v];
head[v] = node++;
}
int siz[maxn];//以u为根节点的子树的结点个数
int top[maxn];//节点u所在链的顶端节点
int son[maxn];//节点u重儿子
int dep[maxn];//节点u的深度
int faz[maxn];//节点u的父节点
int tid[maxn];//节点u的dfs编号
int rnk[maxn];//rnk[i]表示dfs编号为i的原始编号
int cnt;//dfs序号
void init()
{
memset(head, -, sizeof(head));
node = ;
Mem(siz);
Mem(top);
memset(son, -, sizeof(son));
Mem(dep);
Mem(faz);
Mem(tid);
Mem(rnk);
cnt = ;
}
void dfs1(int u, int father, int depth)
{
// u当前节点 father 父节点 depth深度
dep[u] = depth;
faz[u] = father;
siz[u] = ;
for(int i = head[u]; i != -; i = e[i].next)
{
int v = e[i].v;
if(v != faz[u])
{
dfs1(v, u, depth + );
siz[u] += siz[v];//更新子树节点数目
if(son[u] == - || siz[v] > siz[son[u]])
son[u] = v;//更新重儿子
}
}
}
void dfs2(int u, int t)
{
//u当前节点 t起始的重节点
top[u] = t;
tid[u] = ++cnt;
rnk[cnt] = u;
if(son[u] == -)return;//不在重链上
dfs2(son[u], t);//将这条重链上的所有点设置成起始的重节点
for(int i = head[u]; i != -; i = e[i].next)
{
int v = e[i].v;
if(v != son[u] && v != faz[u])
{
dfs2(v, v);//v不是u的重儿子 也不是u的父节点 将v的top设置成自己 进一步递归
}
}
}
struct node{
int l, r, x, sum;
}tree[maxn];
int value[maxn];
void build(int o, int l, int r)
{
tree[o].l = l, tree[o].r = r;
if(l == r)
{
tree[o].x = tree[o].sum = value[rnk[l]];//rnk[i]表示dfs编号为i，原始编号为rnk[i]
return;
}
int m = MID(l, r);
build(lson, l, m);
build(rson, m + , r);
tree[o].sum = tree[lson].sum + tree[rson].sum;
tree[o].x = Max(tree[lson].x, tree[rson].x);
}
void update(int o, int p, int v)
{
if(tree[o].l == tree[o].r){tree[o].sum = tree[o].x = v;return;}
if(p <= tree[lson].r)update(lson, p, v);
else update(rson, p, v);
tree[o].sum = tree[lson].sum + tree[rson].sum;
tree[o].x = Max(tree[lson].x, tree[rson].x);
}
int query_sum(int o, int ql, int qr)
{
if(ql <= tree[o].l && qr >= tree[o].r)return tree[o].sum;
int ans = ;
if(ql <= tree[lson].r)ans += query_sum(lson, ql, qr);
if(qr >= tree[rson].l)ans += query_sum(rson, ql, qr);
return ans;
}
int query_max(int o, int ql, int qr)
{
//cout<<o<<endl;
if(ql <= tree[o].l && qr >= tree[o].r)return tree[o].x;
int ans = -INF, tmp;
if(ql <= tree[lson].r)tmp = query_max(lson, ql, qr), ans = Max(ans, tmp);
if(qr >= tree[rson].l)tmp = query_max(rson, ql, qr), ans = Max(ans, tmp);
return ans;
}
int solve_sum(int x, int y)//LCA top加速
{
int ans = ;
int fx = top[x], fy = top[y];
while(fx != fy)
{
if(dep[fx] >= dep[fy])
{
//计算x到其链的起点的路径和
ans += query_sum(, tid[fx], tid[x]);
//将x设置成起始节点的父节点，走轻边，继续循环
x = faz[fx];
}
else
{
ans += query_sum(, tid[fy], tid[y]);
y = faz[fy];
}
fx = top[x], fy = top[y];
}
//此时x和y在同一条重链上
if(tid[x] <= tid[y])ans += query_sum(, tid[x], tid[y]);
else ans += query_sum(, tid[y], tid[x]);
return ans;
}
int solve_max(int x, int y)//LCA top加速
{
int ans = -INF, tmp;
int fx = top[x], fy = top[y];
while(fx != fy)
{
if(dep[fx] >= dep[fy])
{
//计算x到其链的起点的路径和
tmp = query_max(, tid[fx], tid[x]);
//将x设置成起始节点的父节点，走轻边，继续循环
x = faz[fx];
}
else
{
tmp = query_max(, tid[fy], tid[y]);
y = faz[fy];
}
ans = Max(ans, tmp);
fx = top[x], fy = top[y];
}
//此时x和y在同一条重链上
if(tid[x] <= tid[y])tmp = query_max(, tid[x], tid[y]);
else tmp = query_max(, tid[y], tid[x]);
ans = Max(ans, tmp);
return ans;
} int main()
{
init();
int n, u, v;
scanf("%d", &n);
for(int i = ; i < n; i++)
{
scanf("%d%d", &u, &v);
addedge(u, v);
}
for(int i = ; i <= n; i++)scanf("%d", &value[i]);
dfs1(, , );
dfs2(, );
build(, , n);
int m, a, b;
char s[];
scanf("%d", &m);
while(m--)
{
scanf("%s%d%d", s, &a, &b);
if(s[] == 'C')update(, tid[a], b);//更新的时候下标必须使用dfs编号的
else if(s[] == 'S')printf("%d\n", solve_sum(a, b));
else printf("%d\n", solve_max(a, b));
}
return ;
}
