P4069 [SDOI2016] 游戏

思路

首先，我们可以将一条要标记的路线 \((s, t)\) 分成 \((s, lca)\) 和 \((lca, t)\) 两个部分，这两个部分分别对应一种 \(y = kx + b\)。

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;
using i64 = long long;

const int N = 100010;
const i64 INF = 123456789123456789;

int n, q, tot;
i64 k[N], b[N];

struct edge {
    int to, next, w;
} e[N * 2];

int head[N], idx = 1;

void add(int u, int v, int w) {
    idx++;
    e[idx].to = v;
    e[idx].next = head[u];
    e[idx].w = w;
    head[u] = idx;
}

int dep[N], sz[N], son[N], fa[N];

void dfs(int u, int f) {
    sz[u] = 1, fa[u] = f;
    for (int i = head[u]; i; i = e[i].next) {
        int to = e[i].to;
        if (to == f) continue;
        dep[to] = dep[u] + e[i].w;
        dfs(to, u);
        sz[u] += sz[to];
        if (sz[son[u]] < sz[to]) son[u] = to;
    }
}

int top[N], dfn[N], rk[N], cnt;

void dfs2(int u, int t) {
    dfn[u] = ++cnt, rk[cnt] = u, top[u] = t;
    if (son[u]) dfs2(son[u], t);
    for (int i = head[u]; i; i = e[i].next) {
        int to = e[i].to;
        if (to == fa[u] || to == son[u]) continue;
        dfs2(to, to);
    }
}

int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return x;
}

struct node {
    int id;
    i64 val = INF;
} tr[N << 2];

i64 gety(int id, int x) {
    return k[id] * x + b[id];
}

bool compare(int id1, int id2, int x) {
    i64 y1 = gety(id1, dep[rk[x]]);
    i64 y2 = gety(id2, dep[rk[x]]);
    return y1 < y2;
}

void pushup(int u, int l, int r) {
    if (l != r) tr[u].val = min(tr[u].val, min(tr[u << 1].val, tr[u << 1 | 1].val));
    tr[u].val = min(tr[u].val, min(gety(tr[u].id, dep[rk[l]]), gety(tr[u].id, dep[rk[r]])));
}

void modify(int u, int l, int r, int pl, int pr, int c) {
    int mid = l + r >> 1;
    if (l > r) return;
    if (pl <= l && r <= pr) {
        if (compare(c, tr[u].id, mid)) swap(c, tr[u].id);
        if (compare(c, tr[u].id, l)) modify(u << 1, l, mid, pl, pr, c);
        if (compare(c, tr[u].id, r)) modify(u << 1 | 1, mid + 1, r, pl, pr, c);
        pushup(u, l, r);
        return;
    }
    if (pl <= mid) modify(u << 1, l, mid, pl, pr, c);
    if (pr > mid) modify(u << 1 | 1, mid + 1, r, pl, pr, c);
    pushup(u, l, r);
}

i64 query(int u, int l, int r, int pl, int pr) {
    if (pl <= l && r <= pr) return tr[u].val;
    int mid = l + r >> 1;
    i64 ans = min(gety(tr[u].id, dep[rk[max(l, pl)]]), gety(tr[u].id, dep[rk[min(r, pr)]]));
    if (pl <= mid) ans = min(ans, query(u << 1, l, mid, pl, pr));
    if (pr > mid) ans = min(ans, query(u << 1 | 1, mid + 1, r, pl, pr));
    return ans;
}

void update(int u, int v, int add) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        modify(1, 1, N - 10, dfn[top[u]], dfn[u], add);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    modify(1, 1, N - 10, dfn[u], dfn[v], add);
}

i64 ask(int u, int v) {
    i64 ans = INF;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        ans = min(ans, query(1, 1, N - 10, dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    ans = min(ans, query(1, 1, N - 10, dfn[u], dfn[v]));
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }

    b[0] = INF;
    dfs(1, 0);
    dfs2(1, 1);

    int opt, s, t, x, y;
    for (int i = 1; i <= q; i++) {
        cin >> opt;
        if (opt == 1) {
            cin >> s >> t >> x >> y;
            int l = lca(s, t);
            tot++;
            k[tot] = -x, b[tot] = x * dep[s] + y;
            update(s, l, tot);
            tot++;
            k[tot] = x, b[tot] = x * dep[s] - 2 * x * dep[l] + y;
            update(l, t, tot);
        }
        else {
            cin >> s >> t;
            cout << ask(s, t) << '\n';
        }
    }
    return 0;
}