题目链接
题目描述
Ray 乐忠于旅游，这次他来到了T 城。T 城是一个水上城市，一共有 N 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有N − 1 座桥。
Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度w，也就是说，Ray 经过这座桥会增加w 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。
现在，Ray 想让你帮他计算从u 景点到v 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。
输入的第一行包含一个整数N，表示T 城中的景点个数。景点编号为 0...N − 1。
接下来N − 1 行，每行三个整数u、v 和w，表示有一条u 到v，使 Ray 愉悦度增加w 的桥。桥的编号为1...N − 1。|w| <= 1000。 输入的第N + 1 行包含一个整数M，表示Ray 的操作数目。
接下来有M 行，每行描述了一个操作，操作有如下五种形式：
- C i w，表示Ray 对于经过第i 座桥的愉悦度变成了w。
- N u v，表示Ray 对于经过景点u 到v 的路径上的每一座桥的愉悦度都变成原来的相反数。
- SUM u v，表示询问从景点u 到v 所获得的总愉悦度。
- MAX u v，表示询问从景点u 到v 的路径上的所有桥中某一座桥所提供的最大愉悦度。
- MIN u v，表示询问从景点u 到v 的路径上的所有桥中某一座桥所提供的最小愉悦度。
测试数据保证，任意时刻，Ray 对于经过每一座桥的愉悦度的绝对值小于等于1000。
题解
思路比较简单的树链剖分，但是码量实现起来比较烦，足足写了180+行。
一个一个操作分析过来：
操作1 修改边权
我们都知道，树链剖分可以修改点权，那么同理也可以修改边权。
观察一棵树会发现，一条边有且仅有一个独立的儿子，那么我们就可以把这个信息放到这个儿子上，就变成了维护点权的问题了。
但是需要注意，两个点的lca上的信息并不是两个点之间的路径的信息。
回忆一下我们树链剖分求lca的过程，会发现我们是最后查找的lca。那么同理，如果两个点在一个重链上，那么深度较小的点就是lca，那么我们就操作这个节点的编号\(+1\)的点到深度较大的点。
具体实现差不多是这个样的一个模板：
void Orz(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
segment_tree_Orz(1, idx[top[u]], idx[u]);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
segment_tree_Orz(1, idx[u] + 1, idx[v]);
} 操作2 路径信息取反
很容易可以得到，如果我们用线段树维护区间最大值和最小值、和。
那么取反后，最大值的相反数变成了最小值，最小值的相反数变成了最大值，然后和就只需要取反就可以了一开始WA了好几发就是因为取反的时候顺序写错了（大雾
操作3&4&5 区间最大最小和
这些操作都是线段树的基本操作。不做赘述。
复杂度分析
时间复杂度：\(O(nlogm)\)
空间复杂度：\(O(4\times n)\)
代码复杂度：较复杂，细节比较多。
思路难度：简单。
代码
#include <bits/stdc++.h>
#define ms(a, b) memset(a, b, sizeof(a))
#define ll long long
#define ull unsigned long long
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
#define db double
#define Pi acos(-1)
#define eps 1e-8
#define N 100005
using namespace std;
template <typename T> void read(T &x) {
x = 0; T fl = 1; char ch = 0;
for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') fl = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
x *= fl;
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10); putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) { write(x); puts(""); }
struct Segment_Tree {
#define lc (nod << 1)
#define rc (nod << 1 | 1)
struct node {
int mx, mi, l, r, tag, s;
}tr[N << 2];
void pushup(int nod) { tr[nod].mx = max(tr[lc].mx, tr[rc].mx); tr[nod].s = tr[lc].s + tr[rc].s; tr[nod].mi = min(tr[lc].mi, tr[rc].mi); }
void pushdown(int nod) {
int tmp;
if (tr[nod].tag) {
tr[lc].tag ^= 1; tr[rc].tag ^= 1;
tmp = tr[lc].mi; tr[lc].mi = -tr[lc].mx; tr[lc].mx = -tmp;
tmp = tr[rc].mi; tr[rc].mi = -tr[rc].mx; tr[rc].mx = -tmp;
tr[lc].s *= -1; tr[rc].s *= -1;
tr[nod].tag ^= 1;
}
}
void build(int nod, int l, int r, int *a) {
tr[nod].l = l, tr[nod].r = r; tr[nod].mi = inf, tr[nod].mx = -inf, tr[nod].s = 0; tr[nod].tag = 0;
if (l == r) { tr[nod].mx = tr[nod].mi = tr[nod].s = a[l]; return ; }
int mid = (l + r) >> 1;
build(lc, l, mid, a); build(rc, mid + 1, r, a);
pushup(nod);
}
void update1(int nod, int k, int val) { // 单点修改
int l = tr[nod].l, r = tr[nod].r;
if (l == r) { tr[nod].s = tr[nod].mx = tr[nod].mi = val; return; }
pushdown(nod);
int mid = (l + r) >> 1;
if (k <= mid) update1(lc, k, val); else update1(rc, k, val);
pushup(nod);
}
void update2(int nod, int ql, int qr) { // 相反数
int l = tr[nod].l, r = tr[nod].r;
pushdown(nod);
if (ql <= l && r <= qr) {int tmp = tr[nod].mi; tr[nod].mi = -tr[nod].mx; tr[nod].mx = -tmp; tr[nod].s *= -1; tr[nod].tag ^= 1; return; }
int mid = (l + r) >> 1;
if (ql <= mid) update2(lc, ql, qr);
if (qr > mid) update2(rc, ql, qr);
pushup(nod);
}
int query_sec_min(int nod, int ql, int qr) { // 取最小值
int l = tr[nod].l, r = tr[nod].r;
pushdown(nod);
if (ql <= l && r <= qr) return tr[nod].mi;
int mid = (l + r) >> 1, res = inf;
if (ql <= mid) res = min(res, query_sec_min(lc, ql, qr));
if (qr > mid) res = min(res, query_sec_min(rc, ql, qr));
return res;
}
int query_sec_max(int nod, int ql, int qr) { // 取最大值
int l = tr[nod].l, r = tr[nod].r;
pushdown(nod);
if (ql <= l && r <= qr) return tr[nod].mx;
int mid = (l + r) >> 1, res = -inf;
if (ql <= mid) res = max(res, query_sec_max(lc, ql, qr));
if (qr > mid) res = max(res, query_sec_max(rc, ql, qr));
return res;
}
int query_sec_sum(int nod, int ql, int qr) { // 区间求和
int l = tr[nod].l, r = tr[nod].r;
pushdown(nod);
if (ql <= l && r <= qr) return tr[nod].s;
int mid = (l + r) >> 1, res = 0;
if (ql <= mid) res += query_sec_sum(lc, ql, qr);
if (qr > mid) res += query_sec_sum(rc, ql, qr);
return res;
}
}sgt;
struct edge {
int to, nt, w;
}E[N << 1];
char opt[5];
int fa[N], sz[N], son[N], dep[N], top[N], H[N], a[N], val[N], idx[N], U[N], V[N];
int tot, cnt, n, m;
void add_edge(int u, int v, int w) {
E[++ cnt] = (edge){v, H[u], w};
H[u] = cnt;
}
void dfs1(int u, int ft, int dp) {
fa[u] = ft; dep[u] = dp; sz[u] = 1;
int maxson = -1;
for (int e = H[u]; e; e = E[e].nt) {
int v = E[e].to; if (v == ft) continue;
dfs1(v, u, dp + 1);
a[v] = E[e].w; sz[u] += sz[v];
if (maxson < sz[v]) son[u] = v, maxson = sz[v];
}
}
void dfs2(int u, int tp) {
top[u] = tp; idx[u] = ++ tot; val[tot] = a[u];
if (!son[u]) return; dfs2(son[u], tp);
for (int e = H[u]; e; e = E[e].nt) {
int v = E[e].to; if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
void update_chain_1(int x, int val) {
int u = U[x], v = V[x];
if (u == fa[v]) swap(u, v);
sgt.update1(1, idx[u], val);
}
void update_chain_2(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
sgt.update2(1, idx[top[u]], idx[u]);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
sgt.update2(1, idx[u] + 1, idx[v]);
}
int query_chain_sum(int u, int v) {
int res = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
res += sgt.query_sec_sum(1, idx[top[u]], idx[u]);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
res += sgt.query_sec_sum(1, idx[u] + 1, idx[v]);
return res;
}
int query_chain_min(int u, int v) {
int res = inf;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
res = min(res, sgt.query_sec_min(1, idx[top[u]], idx[u]));
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
res = min(res, sgt.query_sec_min(1, idx[u] + 1, idx[v]));
return res;
}
int query_chain_max(int u, int v) {
int res = -inf;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
res = max(res, sgt.query_sec_max(1, idx[top[u]], idx[u]));
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
res = max(res, sgt.query_sec_max(1, idx[u] + 1, idx[v]));
return res;
}
int main() {
read(n);
for (int i = 1; i < n; i ++) {
int u, v, w; read(u); read(v); read(w); u ++, v ++;
add_edge(u, v, w); add_edge(v, u, w);
U[i] = u; V[i] = v;
}
dfs1(1, 0, 1); dfs2(1, 1);
sgt.build(1, 1, n, val);
read(m);
while (m --) {
scanf("%s", opt);
if (opt[0] == 'C') { int i, w; read(i); read(w); update_chain_1(i, w); }
if (opt[0] == 'N') { int u, v; read(u); read(v); ++ u, ++ v; update_chain_2(u, v); }
if (opt[0] == 'S') { int u, v; read(u); read(v); ++ u, ++ v; writeln(query_chain_sum(u, v)); }
if (opt[1] == 'I') { int u, v; read(u); read(v); ++ u, ++ v; writeln(query_chain_min(u, v)); }
if (opt[1] == 'A') { int u, v; read(u); read(v); ++ u, ++ v; writeln(query_chain_max(u, v)); }
}
return 0;
}