两个更新操作，一个将第i条路径权值改为w，一个是将a-b之间所有路径权值取反。

一个查询操作，求a-b之间路径中权值最大的边。

 

很容易想到维护一个最大最小值，取反就是把最大最小取反交换一下。

 

开始遇到一个问题就是我把根节点赋值0，上一道题求和没问题，但是这道题会出问题，于是线段树建树的时候从2开始建的，第一次尝试这么写，不过也没什么问题。

 

wa了一天。。。。

 

一开始的错是pushdown的时候没有把子节点的fg更新，于是我改了fg[lson]=fg[rson]=1。。。。。。。。

 

就这样。。。。我对着这份代码看了几个小时。。。。。找数据。。。后来自己写了发对拍。。。。

后来终于忍不了了。。。。找了别人的代码。。。。

 

哦，应该是fg[lson] ^= 1;  fg[rson] ^= 1;

我果然不会线段树。。。。。

 

mdzz

 

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 100005;//struct Edge {    int to, next, cost, id;} edge[N*2];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] = 1; 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+1);            sz[u] += sz[v];            if (son[u] == -1 || 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] == -1) 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<<2], fg[N<<2], mi[N<<2];#define lson o<<1#define rson o<<1|1void pushdown(int o) {    if (fg[o]) {        fg[lson] ^= 1;        fg[rson] ^= 1;        int tmp = mx[lson];        mx[lson] = -mi[lson];        mi[lson] = -tmp;        tmp = mx[rson];        mx[rson] = -mi[rson];        mi[rson] = -tmp;        fg[o] = 0;    }}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] = 0;    if (l == r) {        mx[o] = a[l];        mi[o] = a[l];    } else {        int mid = (l+r) >> 1;        build(lson, l, mid);        build(rson, mid+1, 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) >> 1;        if (mid >= v) CHANGE(lson, l, mid, v, w);        else CHANGE(rson, mid+1, r, v, w);        pushup(o);    }}void nega(int o, int l, int r, int L, int R) {    if (l >= L && r <= R) {        fg[o] ^= 1;        int tmp = mx[o];        mx[o] = -mi[o];        mi[o] = -tmp;        return;    }    pushdown(o);    int mid = (l+r) >> 1;    if (mid >= L) nega(lson, l, mid, L, R);    if (mid < R) nega(rson, mid+1, 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(1, 2, n, dfn[top[x]], dfn[x]);        x = fa[top[x]];    }    if (x == y) return ;    if (dep[x] > dep[y]) swap(x, y);    nega(1, 2, 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) >> 1;    int ans = -(1<<30);    if (L <= mid) ans = max(ans, query(lson, l, mid, L, R));    if (R > mid) ans = max(ans, query(rson, mid+1, r, L, R));    pushup(o);    return ans;}int QUERY(int x, int y, int n) {    if (x == y) return 0;    int ans = -(1<<30);    while (top[x] != top[y]) {        if (dep[top[x]] < dep[top[y]]) swap(x, y);        ans = max(ans, query(1, 2, 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(1, 2, n, dfn[son[x]], dfn[y])); // 注意这里是son[x]    return ans;}void init() {    idx = cntE = 0;    memset(head, -1, sizeof head);    memset(son, -1, sizeof son);}// 区间更新 点更新 区间查询int main() {    int n, T;    scanf("%d",&T);    int cas = 0;    while (T--) {        scanf("%d", &n); init();        int u, v, w;        for (int i = 1; i < n; ++i) scanf("%d%d%d", &u, &v, &w), addedge(u, v, w, i);        dfs1(1, 0, 0); dfs2(1, 1, 0); build(1, 2, n);        char op[10];        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(1, 2, n, dfn[road[u]], v);            else NEGATE(u, v, n);        }    }    return 0;}
        
       
      
     

 

一组数据

/**

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

*/