POJ3237 Tree 树链剖分 边权

传送门：http://poj.org/problem?id=3237

题意：

n个点的，n-1条边

修改单边边权

将a->b的边权取反

查询a->b边权最大值

题解：

修改边权就查询点的深度大的点，用大的点去存这条边的边权，其余的就和点权的是一样的了

取反操作用线段树维护，区间最大值取反就是区间最小值，区间最小值取反就是区间最大值

所以维护两颗线段树即可，lazy标记表示覆盖单边的边权

代码：

#include <set>

#include <map>

#include <cmath>

#include <cstdio>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define ls rt<<1

#define rs rt<<1|1

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define bug printf("*********\n")

#define FIN freopen("input.txt","r",stdin);

#define FON freopen("output.txt","w+",stdout);

#define IO ios::sync_with_stdio(false),cin.tie(0)

#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"

#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"

#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"

const int maxn = 1e5 + 5;

const int INF = 0x3f3f3f3f;

struct EDGE {

    int v, nxt, w;

} edge[maxn << 1];

int head[maxn], tot;

void add_edge(int u, int v, int w) {

    edge[tot].v = v;

    edge[tot].w = w;

    edge[tot].nxt = head[u];

    head[u] = tot++;

}

int sz[maxn], dep[maxn], son[maxn], id[maxn], Rank[maxn], cnt, fa[maxn], top[maxn];

int d[maxn];

void dfs1(int u, int f, int cnt) {

    fa[u] = f;

    dep[u] = cnt;

    sz[u] = 1;

    son[u] = 0;

    int tmp = 0;

    for(int i = head[u]; i != -1; i = edge[i].nxt) {

        int v = edge[i].v;

        if(v != f) {

            dfs1(v, u, cnt + 1);

            if(tmp < sz[v]) {

                son[u] = v;

                tmp = sz[v];

            }

            sz[u] += sz[v];

        }

    }

}

void dfs2(int u, int tp) {

    top[u] = tp;

    id[u] = ++cnt;

    Rank[cnt] = u;

    if(son[u]) dfs2(son[u], tp);

    for(int i = head[u]; i != -1; i = edge[i].nxt) {

        int v = edge[i].v;

        if(v == fa[u]) continue;

        if(v == son[u]) {

            d[id[v]] = edge[i].w;

            continue;

        }

        dfs2(v, v);

        d[id[v]] = edge[i].w;

    }

}

void prebuild() {

    dfs1(1, 0, 0);

    dfs2(1, 1);

}

int Max[maxn << 2];

int Min[maxn << 2];

// int sum[maxn<<2];

int lazy[maxn];

void push_up(int rt) {

    Max[rt] = max(Max[ls], Max[rs]);

    Min[rt] = min(Min[ls], Min[rs]);

}

void build(int l, int r, int rt) {

    lazy[rt] = 1;

    if(l == r) {

        Max[rt] = Min[rt] = d[l];

        return;

    }

    int mid = (l + r) >> 1;

    build(lson);

    build(rson);

    push_up(rt);

}

void push_down(int rt) {

    if(lazy[rt] == -1) {

        lazy[ls] = -lazy[ls];

        lazy[rs] = -lazy[rs];

        lazy[rt] = 1;

        swap(Max[ls], Min[ls]);

        Max[ls] *= -1;

        Min[ls] *= -1;

        swap(Max[rs], Min[rs]);

        Max[rs] *= -1;

        Min[rs] *= -1;

    }

}

void update_pos(int pos, int val, int l, int r, int rt) {

    if(l == r) {

        lazy[rt] = 1;

        Max[rt] = Min[rt] = val;

        return;

    }

    push_down(rt);

    int mid = (l + r) >> 1;

    if(pos <= mid) update_pos(pos, val, lson);

    else update_pos(pos, val, rson);

    push_up(rt);

}

void update(int L, int R, int l, int r, int rt) {

    if(L <= l && r <= R) {

        lazy[rt] = -lazy[rt];

        swap(Max[rt], Min[rt]);

        Max[rt] *= -1;

        Min[rt] *= -1;

        return;

    }

    push_down(rt);

    int mid = (l + r) >> 1;

    if(L <= mid) update(L, R, lson);

    if(R > mid) update(L, R, rson);

    push_up(rt);

}

int query(int L, int R, int l, int r, int rt) {

    if(L <= l && r <= R) {

        return Max[rt];

    }

    push_down(rt);

    int mid = (l + r) >> 1;

    int ans = -INF;

    if(L <= mid) ans = max(ans, query(L, R, lson));

    if(R > mid) ans = max(ans, query(L, R, rson));

    return ans;

}

void change(int u, int v) {

    while(top[u] != top[v]) {

        if(dep[top[u]] < dep[top[v]]) {

            swap(u, v);

        }

        update(id[top[u]], id[u], 1, cnt, 1);

        u = fa[top[u]];

    }

    if(u != v) {

        if(dep[u] > dep[v]) swap(u, v);

        update(id[son[u]], id[v], 1, cnt, 1);

    }

}

void Query(int u, int v) {

    int ans = -INF;

    while(top[u] != top[v]) {

        if(dep[top[u]] < dep[top[v]]) {

            swap(u, v);

        }

        ans = max(ans, query(id[top[u]], id[u], 1, cnt, 1));

        u = fa[top[u]];

    }

    if(u != v) {

        if(dep[u] > dep[v]) swap(u, v);

        ans = max(ans, query(id[son[u]], id[v], 1, cnt, 1));

    }

    printf("%d\n", ans);

}

int u[maxn], v[maxn], c[maxn];

int main() {

#ifndef ONLINE_JUDGE

    FIN

#endif

    int n, T;

    scanf("%d", &T);

    while(T--) {

        scanf("%d", &n);

        memset(head, -1, sizeof(head));

        tot = cnt = 0;

        for(int i = 1; i < n; i++) {

            scanf("%d%d%d", &u[i], &v[i], &c[i]); //要用数组保存

            add_edge(u[i], v[i], c[i]);

            add_edge(v[i], u[i], c[i]);

        }

        prebuild();

        build(1, cnt, 1);

        char op[20];

        int a, b;

        while(1) {

            scanf("%s", op);

            if(op[0] == 'D') break;

            scanf("%d%d", &a, &b);

            if(op[0] == 'C') {

                int tmp = dep[u[a]] > dep[v[a]] ? u[a] : v[a]; //找出深度大的那个点

                update_pos(id[tmp], b, 1, cnt, 1); //更新进入深度大的点那条边

            } else if(op[0] == 'N') change(a, b);

            else if(op[0] == 'Q') Query(a, b);

        }

    }

    return 0;

}