POJ - 3237 题解（树链剖分）

题目传送门

题意

给n个点，有n-1条边连起来，每条边有自己的权值，多个操作：改变第i条边的权值；将a到b的链的边的权值取相反数；查询a到b的链上最大的权值。

题解

树链剖分，维护最大最小值，要取相反数的时候，最大最小值交换，再取相反数即可。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
const int MAXN = 100005;
int w[MAXN], rk[MAXN];
int n;
struct sgm {
    int l, r;
    long long minn;
    long long maxn;
    int lazy;
    void _swap() {
        swap ( minn, maxn );
        minn = -minn;
        maxn = -maxn;
    }
} sgmt[MAXN << 2];
inline void push_up ( int rt ) {
    sgmt[rt].minn = min ( sgmt[rt << 1].minn, sgmt[rt << 1 | 1].minn );
    sgmt[rt].maxn = max ( sgmt[rt << 1].maxn, sgmt[rt << 1 | 1].maxn );
}
inline void push_down ( int rt ) {
    if ( sgmt[rt].lazy ) {
        sgmt[rt << 1].lazy ^= 1;
        sgmt[rt << 1]._swap();
        sgmt[rt << 1 | 1].lazy ^= 1;
        sgmt[rt << 1 | 1]._swap();
        sgmt[rt].lazy = 0;
    }
}
void build ( int rt, int l, int r ) {
    sgmt[rt].l = l;
    sgmt[rt].r = r;
    sgmt[rt].lazy = 0;
    if ( l == r ) {
        if ( l == 1 ) {
            sgmt[rt].minn = sgmt[rt].maxn = 0;
        } else {
            sgmt[rt].minn = sgmt[rt].maxn = w[l];
        }
        return;
    }
    int mid = ( l + r ) >> 1;
    build ( rt << 1, l, mid );
    build ( rt << 1 | 1, mid + 1, r );
    push_up ( rt );
}
void change ( int rt, int l, int c ) {
    if ( l == sgmt[rt].l && l == sgmt[rt].r ) {
        sgmt[rt].minn = sgmt[rt].maxn = c;
        sgmt[rt].lazy = 0;
        return;
    }
    push_down ( rt );
    int mid = ( sgmt[rt].l + sgmt[rt].r ) >> 1;
    if ( l <= mid ) {
        change ( rt << 1, l, c );
    }
    if ( mid < l ) {
        change ( rt << 1 | 1, l, c );
    }
    push_up ( rt );
}
void update ( int rt, int l, int r ) {
    if ( l <= sgmt[rt].l && sgmt[rt].r <= r ) {
        sgmt[rt]._swap();
        sgmt[rt].lazy ^= 1;
        return;
    }
    push_down ( rt );
    int mid = ( sgmt[rt].l + sgmt[rt].r ) >> 1;
    if ( l <= mid ) {
        update ( rt << 1, l, r );
    }
    if ( mid < r ) {
        update ( rt << 1 | 1, l, r );
    }
    push_up ( rt );
}
long long query ( int rt, int l, int r ) {
    if ( l <= sgmt[rt].l && sgmt[rt].r <= r ) {
        return sgmt[rt].maxn;
    }
    push_down ( rt );
    long long ans = -0x3f3f3f3f;
    int mid = ( sgmt[rt].l + sgmt[rt].r ) >> 1;
    if ( l <= mid ) {
        ans = max ( ans, query ( rt << 1, l, r ) );
    }
    if ( mid < r ) {
        ans = max ( ans, query ( rt << 1 | 1, l, r ) );
    }
    return ans;
}
int Head[MAXN << 1], ver[MAXN << 1], nxt[MAXN << 1];
int E;
void addedge ( int u, int v ) {
    ver[E] = v;
    nxt[E] = Head[u];
    Head[u] = E++;
}
int cnt;
int son[MAXN], size[MAXN], d[MAXN], fa[MAXN], top[MAXN], id[MAXN];
void dfs1 ( int f, int u, int depth ) {
    size[u] = 1;
    son[u] = 0;
    d[u] = depth;
    fa[u] = f;
    for ( int i = Head[u]; ~i; i = nxt[i] ) {
        int v = ver[i];
        if ( v == f ) {
            continue;
        }
        dfs1 ( u, v, depth + 1 );
        size[u] += size[v];
        if ( size[v] > size[son[u]] ) {
            son[u] = v;
        }
    }
}
void dfs2 ( int f, int u ) {
    top[u] = f;
    id[u] = ++cnt;
    rk[cnt] = u;
    if ( !son[u] ) {
        return;
    }
    dfs2 ( f, son[u] );
    for ( int i = Head[u]; ~i; i = nxt[i] ) {
        int v = ver[i];
        if ( v == fa[u] || v == son[u] ) {
            continue;
        }
        dfs2 ( v, v );
    }
}
void pathinv ( int x, int y ) {
    int fx = top[x], fy = top[y];
    while ( id[fx] != id[fy] ) {
        if ( d[fx] > d[fy] ) {
            update ( 1, id[fx], id[x] );
            x = fa[fx];
            fx = top[x];
        } else {
            update ( 1, id[fy], id[y] );
            y = fa[fy];
            fy = top[y];
        }
    }
    if ( id[x] > id[y] ) {
        update ( 1, id[son[y]], id[x] );
    } else if ( id[x] < id[y] ) {
        update ( 1, id[son[x]], id[y] );
    }
    return;
}
long long pathmax ( int x, int y ) {
    long long ans = -0x3f3f3f3f;
    int fx = top[x], fy = top[y];
    if ( x == y ) {
        return 0;
    }
    while ( id[fx] != id[fy] ) {
        if ( d[fx] > d[fy] ) {
            ans = max ( ans, query ( 1, id[fx], id[x] ) );
            x = fa[fx];
            fx = top[x];
        } else {
            ans = max ( ans, query ( 1, id[fy], id[y] ) );
            y = fa[fy];
            fy = top[y];
        }
    }
    if ( id[x] > id[y] ) {
        ans = max ( ans, query ( 1, id[son[y]], id[x] ) );
    } else if ( id[x] < id[y] ) {
        ans = max ( ans, query ( 1, id[son[x]], id[y] ) );
    }
    return ans;
}
struct edge {
    int u, v, w;
    void input() {
        scanf ( "%d%d%d", &u, &v, &w );
        addedge ( u, v );
        addedge ( v, u );
    }
} e[MAXN];
int x, y, k;
char s[10];
int main() {
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    int t;
    scanf ( "%d", &t );
    while ( t-- ) {
        E = 0;
        cnt = 0;
        memset ( Head, -1, sizeof ( Head ) );
        scanf ( "%d", &n );
        for ( int i = 1; i < n; i++ ) {
            e[i].input();
        }
        dfs1 ( 0, 1, 1 );
        dfs2 ( 1, 1 );
        for ( int i = 1; i < n; i++ ) {
            if ( d[e[i].u] > d[e[i].v] ) {
                swap ( e[i].u, e[i].v );
            }
            w[id[e[i].v]] = e[i].w;
        }
        w[1] = 0;
        build ( 1, 1, n );
        while ( ~scanf ( "%s", s ) ) {
            if ( s[0] == 'D' ) {
                break;
            } else if ( s[0] == 'C' ) {
                scanf ( "%d %d", &x, &k );
                change ( 1, id[e[x].v], k );
            } else if ( s[0] == 'N' ) {
                scanf ( "%d %d", &x, &y );
                pathinv ( x, y );
            } else if ( s[0] == 'Q' ) {
                scanf ( "%d %d", &x, &y );
                printf ( "%lld\n", pathmax ( x, y ) );
            }
        }
    }
    return 0;
}