题解

【国家集训队】旅游

题意

给定一棵树,边有边权,要求实现以下五种操作。

  1. 修改一条边的权值。
  2. 把一条路径的边的权值取反。
  3. 求一条路径的边权和。
  4. 求一条路径的最大边权。
  5. 求一条路径的最小边权。

题目链接

LuoguP1505

题解

树剖模板题,剖一下就变成了线段树的区间操作,十分基础。大部分地方粘贴一下改一改就写完了。
边权转点权,跳到 $lca$ 的时候判断一下就可以了。
区间取相反数,只需要把区间最大值和区间最小值取反然后交换就可以了。
PS:代码好久之前写的了,刚才瞅了一眼甚至没看出来我在写啥。。。

代码

#include <cstdio>
#include <climits>
#include <cstring>
#include <iostream>
#include <cmath>
const int MAXN = 1e5 + 7;
struct Edge {
    int t, w, next;
} edge[MAXN << 1];
int head[MAXN], cnt;
int fa[MAXN], deep[MAXN], size[MAXN], dfn[MAXN], son[MAXN], val[MAXN], pos[MAXN], ts = 0, top[MAXN];
int x[MAXN], y[MAXN];
struct Node {
    int l, r, mid;
    Node *lc, *rc;
    int sum, min, max;
    int tag;
    Node() {}
    Node(int l, int r, Node *lc, Node *rc) : l(l), r(r), mid((l + r) / 2), lc(lc), rc(rc),
        sum(0), min(INT_MAX), max(INT_MIN), tag(1) {}
    static Node *build(int l, int r) {
        Node *ret;
        if (l == r) {
            ret = new Node(l, r, NULL, NULL);
            if (l != 1) ret->sum = ret->max = ret->min = val[pos[l]];
        } else {
            int mid = (l + r) / 2;
            ret = new Node(l, r, build(l, mid), build(mid + 1, r));
            ret->pushUp();
        }
        return ret;
    }
    void pushUp() {
        sum = lc->sum + rc->sum;
        max = std::max(lc->max, rc->max);
        min = std::min(lc->min, rc->min);
    }
    void pushDown() {
        if (tag == -1) {
            lc->neg(), rc->neg();
            tag = 1;
        }
    }
    void neg() {
        sum = -sum;
        max = -max, min = -min, std::swap(max, min);
        tag *= -1;
    }
    void Change(int pos, int delta) {
        if (l == pos && r == pos) {
            sum = max = min = delta;
            tag = 1;
            return;
        }
        pushDown();
        if (pos <= mid) lc->Change(pos, delta);
        else rc->Change(pos, delta);
        pushUp();
    }
    void Negate(int left, int right) {
        if (l == left && r == right) return neg();
        pushDown();
        if (right <= mid) lc->Negate(left, right);
        else if (left > mid) rc->Negate(left, right);
        else lc->Negate(left, mid), rc->Negate(mid + 1, right);
        pushUp();
    }
    int Sum(int left, int right) {
        if (l == left && r == right) return sum;
        pushDown();
        if (right <= mid) return lc->Sum(left, right);
        else if (left > mid) return rc->Sum(left, right);
        else return lc->Sum(left, mid) + rc->Sum(mid + 1, right);
    }
    int Max(int left, int right) {
        if (l == left && r == right) return max;
        pushDown();
        if (right <= mid) return lc->Max(left, right);
        else if (left > mid) return rc->Max(left, right);
        else return std::max(lc->Max(left, mid), rc->Max(mid + 1, right));
    }
    int Min(int left, int right) {
        if (l == left && r == right) return min;
        pushDown();
        if (right <= mid) return lc->Min(left, right);
        else if (left > mid) return rc->Min(left, right);
        else return std::min(lc->Min(left, mid), rc->Min(mid + 1, right));
    }
} *root;
void dfs1(int u, int pre) {
    fa[u] = pre;
    deep[u] = deep[pre] + 1;
    size[u] = 1;
    int maxSize = 0;
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (v == pre) continue;
        val[v] = edge[e].w;
        dfs1(v, u);
        size[u] += size[v];
        if (!son[u] || maxSize < size[v]) {
            maxSize = size[v];
            son[u] = v;
        }
    }
}
void dfs2(int u, int tp) {
    dfn[u] = ++ts;
    pos[ts] = u;
    top[u] = tp;
    if (son[u]) dfs2(son[u], tp);
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
void Negate(int u, int v) {
    while (top[u] != top[v]) {
        if (deep[top[u]] < deep[top[v]]) std::swap(u, v);
        root->Negate(dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (dfn[u] > dfn[v]) std::swap(u, v);
    if (dfn[u] < dfn[v]) root->Negate(dfn[u] + 1, dfn[v]);
}
int sum(int u, int v) {
    int ans = 0;
    while (top[u] != top[v]) {
        if (deep[top[u]] < deep[top[v]]) std::swap(u, v);
        ans += root->Sum(dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (dfn[u] > dfn[v]) std::swap(u, v);
    if (dfn[u] < dfn[v]) ans += root->Sum(dfn[u] + 1, dfn[v]);
    return ans;
}
int max(int u, int v) {
    int ans = INT_MIN;
    while (top[u] != top[v]) {
        if (deep[top[u]] < deep[top[v]]) std::swap(u, v);
        ans = std::max(ans, root->Max(dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if (dfn[u] > dfn[v]) std::swap(u, v);
    if (dfn[u] < dfn[v]) ans = std::max(ans, root->Max(dfn[u] + 1, dfn[v]));
    return ans;
}
int min(int u, int v) {
    int ans = INT_MAX;
    while (top[u] != top[v]) {
        if (deep[top[u]] < deep[top[v]]) std::swap(u, v);
        ans = std::min(ans, root->Min(dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if (dfn[u] > dfn[v]) std::swap(u, v);
    if (dfn[u] < dfn[v]) ans = std::min(ans, root->Min(dfn[u] + 1, dfn[v]));
    return ans;
}
inline void add(int u, int v, int w) {
    edge[++cnt] = (Edge) {v, w, head[u]}; head[u] = cnt;
}
int main(int argc, char *argv[]) {
    int n, m;
    scanf("%d", &n);
    int w;
    for (int i = 1; i < n; i++) {
        scanf("%d %d %d", x + i, y + i, &w);
        x[i]++;
        y[i]++;
        add(x[i], y[i], w);
        add(y[i], x[i], w);
    }
    deep[1] = 1;
    dfs1(1, 0);
    dfs2(1, 1);
    root = Node::build(1, n);
    char o[10];
    int u, v;
    scanf("%d", &m);
    while (m--) {
        scanf("%s %d %d", o, &u, &v);
        if (o[0] == 'C') {
            int tmp = deep[x[u]] > deep[y[u]] ? x[u] : y[u];
            root->Change(dfn[tmp], v);
        } else if (o[0] == 'N') {
            u++; v++;
            Negate(u, v);
        } else if (o[0] == 'S') {
            u++; v++;
            printf("%d\n", sum(u, v));
        } else if (o[0] == 'M') {
            u++; v++;
            if (o[1] == 'A') printf("%d\n", max(u, v));
            else printf("%d\n", min(u, v));
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注