Codeforces 1192B 全dfs序 + 线段树-蒲公英云

Codeforces 1192B 全dfs序 + 线段树

小咪咪 2023-08-17 17:22 224阅读 0赞

题意：给你一颗树，每次会修改一条边的边权，问修改之后的树的直径是多少？

思路：来源于：https://www.cnblogs.com/TinyWong/p/11260601.html

得到树的全序dfs序之后，我们考虑用线段树维护x - 2 * y + z。维护方法和2017, 2016那道题差不多，对于每个区间维护:x, -y, z, x - 2 * y, -2 * y + z, x - 2 * y + z6个部分的最大值，然后区间合并。

代码：

#include <bits/stdc++.h>
#define ls (o << 1)
#define rs (o << 1 | 1)
#define LL long long
#define INF 1e18
using namespace std;
const int maxn = 100010;
int lp[maxn], rp[maxn], mp[maxn * 2], tot;
vector<pair<int, long long> > G[maxn];
LL d[maxn];
void add(LL x, LL y, LL z) {
    G[x].push_back(make_pair(y, z));
    G[y].push_back(make_pair(x, z));
}
struct edge {
    int u, v;
    LL w;
};
edge a[maxn];
struct Seg {
    LL v[6], lz;
    //0: a
    //1: b
    //2: c
    //3: a + 2 * b
    //4: 2 * c + b
    //5: a + b + 2 * c
};
Seg tr[maxn * 8];
void pushup(int o) {
    //0:
    tr[o].v[0] = max(tr[ls].v[0], tr[rs].v[0]);
    //1:
    tr[o].v[1] = max(tr[ls].v[1], tr[rs].v[1]);
    //2:
    tr[o].v[2] = max(tr[ls].v[2], tr[rs].v[2]);
    //3:
    tr[o].v[3] = max(tr[ls].v[3], tr[rs].v[3]);
    tr[o].v[3] = max(tr[o].v[3], tr[ls].v[0] + 2ll * tr[rs].v[1]);
    //4:
    tr[o].v[4] = max(tr[ls].v[4], tr[rs].v[4]);
    tr[o].v[4] = max(tr[o].v[4], 2ll * tr[ls].v[1] + tr[rs].v[2]);
    //: 5
    tr[o].v[5] = max(tr[ls].v[5], tr[rs].v[5]);
    tr[o].v[5] = max(tr[o].v[5], tr[ls].v[3] + tr[rs].v[2]);
    tr[o].v[5] = max(tr[o].v[5], tr[ls].v[0] + tr[rs].v[4]);
}
void maintain(int o, LL x) {
    tr[o].lz += x;
    tr[o].v[0] += x;
    tr[o].v[1] -= x;
    tr[o].v[2] += x;
    tr[o].v[3] -= x;
    tr[o].v[4] -= x;
}
void pushdown(int o) {
    if(tr[o].lz) {
        maintain(ls, tr[o].lz);
        maintain(rs, tr[o].lz);
        tr[o].lz = 0;
    } 
}
void build(int o, int l, int r) {
    tr[o].lz = 0;
    if(l == r) {
        tr[o].v[0] = tr[o].v[2] = d[mp[l]];
        tr[o].v[4] = tr[o].v[3] = tr[o].v[1] = -d[mp[l]];
        tr[o].v[5] = 0; 
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(o);
}
void update(int o, int l, int r, int ql, int qr, LL val) {
    if(l >= ql && r <= qr) {
        maintain(o, val);
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(o);
    if(ql <= mid) update(ls, l, mid, ql, qr, val);
    if(qr > mid) update(rs, mid + 1, r, ql, qr, val);
    pushup(o);
}
void dfs(int x, int fa, LL dis) {
    mp[++tot] = x;
    lp[x] = tot;
    rp[x] = tot;
    d[x] = dis;
    for (auto y : G[x]) {
        if(y.first == fa) continue;
        dfs(y.first, x, dis + y.second);
        mp[++tot] = x;
        rp[x] = tot;
    }
}
int main() {
    int n, m;
    LL w, x, y, z;
    scanf("%d%d%lld", &n, &m, &w);
    for (int i = 1; i < n; i++) {
        scanf("%lld%lld%lld", &x, &y, &z);
        add(x, y, z);
        a[i].u = x, a[i].v = y, a[i].w = z;
    }
    dfs(1, 0, 0);
    build(1, 1, tot);
    LL ans = 0;
    while(m--) {
        scanf("%lld%lld", &x, &y);
        x = (x + ans) % (n - 1) + 1;
        y = (y + ans) % w;
        int p;
        if(lp[a[x].u] < lp[a[x].v]) p = a[x].v;
        else p = a[x].u;
        update(1, 1, tot, lp[p], rp[p], y - a[x].w);
        a[x].w = y;
        ans = tr[1].v[5];
        printf("%lld\n", ans);
    }
}