两个更新操作，一个将第i条路径权值改为w，一个是将a-b之间所有路径权值取反。
一个查询操作，求a-b之间路径中权值最大的边。
很容易想到维护一个最大最小值，取反就是把最大最小取反交换一下。
开始遇到一个问题就是我把根节点赋值0，上一道题求和没问题，但是这道题会出问题，于是线段树建树的时候从2开始建的，第一次尝试这么写，不过也没什么问题。
wa了一天。。。。
一开始的错是pushdown的时候没有把子节点的fg更新，于是我改了fg[lson]=fg[rson]=1。。。。。。。。
就这样。。。。我对着这份代码看了几个小时。。。。。找数据。。。后来自己写了发对拍。。。。
后来终于忍不了了。。。。找了别人的代码。。。。
哦，应该是fg[lson] ^= 1; fg[rson] ^= 1;
我果然不会线段树。。。。。
mdzz
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = ; //
struct Edge {
int to, next, cost, id;
} edge[N*];
int head[N], cntE;
void addedge(int u, int v, int w, int id) {
edge[cntE].to = v; edge[cntE].next = head[u]; edge[cntE].cost = w; edge[cntE].id = id; head[u] = cntE++;
edge[cntE].to = u; edge[cntE].next = head[v]; edge[cntE].cost = w; edge[cntE].id = id; head[v] = cntE++;
}
//
int dep[N], sz[N], fa[N], son[N], son_cost[N];
int road[N];
void dfs1(int u, int par, int d) {
dep[u] = d; sz[u] = ; fa[u] = par;
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if (v != par) {
road[edge[i].id] = v;
dfs1(v, u, d+);
sz[u] += sz[v];
if (son[u] == - || sz[v] > sz[son[u]]) {
son[u] = v;
son_cost[u] = edge[i].cost;
}
}
}
}
int top[N], dfn[N], rk[N], idx;
int a[N];
void dfs2(int u, int rt, int cost) {
top[u] = rt; dfn[u] = ++idx; a[idx] = cost;
if (son[u] == -) return;
dfs2(son[u], rt, son_cost[u]);
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if (v != fa[u] && v != son[u]) dfs2(v, v, edge[i].cost);
}
} //
int mx[N<<], fg[N<<], mi[N<<];
#define lson o<<1
#define rson o<<1|1 void pushdown(int o) {
if (fg[o]) {
fg[lson] ^= ;
fg[rson] ^= ;
int tmp = mx[lson];
mx[lson] = -mi[lson];
mi[lson] = -tmp;
tmp = mx[rson];
mx[rson] = -mi[rson];
mi[rson] = -tmp;
fg[o] = ;
}
} void pushup(int o) {
mx[o] = max(mx[lson], mx[rson]);
mi[o] = min(mi[lson], mi[rson]);
} void build(int o, int l, int r) {
fg[o] = ;
if (l == r) {
mx[o] = a[l];
mi[o] = a[l];
} else {
int mid = (l+r) >> ;
build(lson, l, mid);
build(rson, mid+, r);
pushup(o);
}
} void CHANGE(int o, int l, int r, int v, int w) {
if (l == r) {
mi[o] = mx[o] = w;
} else {
pushdown(o);
int mid = (l + r) >> ;
if (mid >= v) CHANGE(lson, l, mid, v, w);
else CHANGE(rson, mid+, r, v, w);
pushup(o);
}
} void nega(int o, int l, int r, int L, int R) {
if (l >= L && r <= R) {
fg[o] ^= ;
int tmp = mx[o];
mx[o] = -mi[o];
mi[o] = -tmp;
return;
}
pushdown(o);
int mid = (l+r) >> ;
if (mid >= L) nega(lson, l, mid, L, R);
if (mid < R) nega(rson, mid+, r, L, R);
pushup(o);
} void NEGATE(int x, int y, int n) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
nega(, , n, dfn[top[x]], dfn[x]);
x = fa[top[x]];
}
if (x == y) return ;
if (dep[x] > dep[y]) swap(x, y);
nega(, , n, dfn[son[x]], dfn[y]);
} int query(int o, int l ,int r, int L, int R) {
if (l >= L && r <= R) {
return mx[o];
}
pushdown(o);
int mid = (l+r) >> ;
int ans = -(<<);
if (L <= mid) ans = max(ans, query(lson, l, mid, L, R));
if (R > mid) ans = max(ans, query(rson, mid+, r, L, R));
pushup(o);
return ans;
} int QUERY(int x, int y, int n) {
if (x == y) return ;
int ans = -(<<);
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
ans = max(ans, query(, , n, dfn[top[x]], dfn[x]));
x = fa[top[x]];
}
if (x == y) return ans;
if (dep[x] > dep[y]) swap(x, y);
ans = max(ans, query(, , n, dfn[son[x]], dfn[y])); // 注意这里是son[x]
return ans;
} void init() {
idx = cntE = ;
memset(head, -, sizeof head);
memset(son, -, sizeof son);
} // 区间更新 点更新 区间查询
int main() {
int n, T;
scanf("%d",&T);
int cas = ;
while (T--) {
scanf("%d", &n); init();
int u, v, w;
for (int i = ; i < n; ++i) scanf("%d%d%d", &u, &v, &w), addedge(u, v, w, i);
dfs1(, , ); dfs2(, , ); build(, , n);
char op[];
while (~scanf("%s", op)) {
if (*op == 'D') break;
scanf("%d%d", &u, &v);
if (*op == 'Q') printf("%d\n", QUERY(u, v, n));
else if (*op == 'C') CHANGE(, , n, dfn[road[u]], v);
else NEGATE(u, v, n);
}
}
return ;
}
一组数据
/**
2
7
1 2 1
2 3 7
3 4 8
4 5 6
5 6 9
6 7 1
N 4 7
C 2 3
N 1 7
C 2 7
N 1 5
C 4 7
D
6
1 2 8
2 3 8
3 4 7
4 5 2
5 6 10
N 6 1
C 1 2
N 3 6
N 4 1
N 1 6
Q 2 6
D
Output:
8
1
7
8
10
-10
7
*/