【LG4175】[CTSC2008]网络管理

题面

洛谷

题解

感觉就和普通的整体二分差不太多啊。。。

树上修改就按时间添加，用树状数组维护一下即可

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

namespace IO {

    const int BUFSIZE = 1 << 20;

    char ibuf[BUFSIZE], *is = ibuf, *it = ibuf;

    inline char gc() {

        if (is == it) it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);

        return *is++;

    }

}

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (!isdigit(ch) && ch != '-') ch = IO::gc();

    if (ch == '-') w = -1, ch = IO::gc();

    while (isdigit(ch)) data = 10 * data + ch - '0', ch = IO::gc();

    return w * data;

}

const int MAX_N = 80005;

struct Node { int u, v, k, id; } q[MAX_N << 1], lq[MAX_N << 1], rq[MAX_N << 1];

int N, Q, a[MAX_N], cnt, ans[MAX_N];

struct Graph { int to, next; } e[MAX_N << 1]; int fir[MAX_N], e_cnt;

void clearGraph() { memset(fir, -1, sizeof(fir)); e_cnt = 0; }

void Add_Edge(int u, int v) { e[e_cnt] = (Graph){v, fir[u]}; fir[u] = e_cnt++; }

int dep[MAX_N], fa[MAX_N], top[MAX_N], size[MAX_N], son[MAX_N], L[MAX_N], tim;

void dfs1(int x) {

    dep[x] = dep[fa[x]] + 1; size[x] = 1;

    for (int i = fir[x]; ~i; i = e[i].next) {

        int v = e[i].to; if (v == fa[x]) continue;

        fa[v] = x; dfs1(v);

        size[x] += size[v];

        if (size[v] > size[son[x]]) son[x] = v;

    }

}

void dfs2(int x, int tp) {

    top[x] = tp, L[x] = ++tim;

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

    for (int i = fir[x]; ~i; i = e[i].next) {

        int v = e[i].to;

        if (v == son[x] || v == fa[x]) continue;

        dfs2(v, v);

    }

}

int c[MAX_N];

inline int lb(int x) { return x & -x; }

void Add(int x, int v) { while (x <= N) c[x] += v, x += lb(x); }

int sum(int x) { int res = 0; while (x > 0) res += c[x], x -= lb(x); return res; }

int Sum(int u, int v) {

    int res = 0;

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

        if (dep[top[u]] < dep[top[v]]) swap(u, v);

        res += sum(L[u]) - sum(L[top[u]] - 1);

        u = fa[top[u]];

    }

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

    return res + sum(L[u]) - sum(L[v] - 1);

}

void Div(int lval, int rval, int st, int ed) {

    if (st > ed) return ;

    if (lval == rval) {

        for (int i = st; i <= ed; i++) if (q[i].id) ans[q[i].id] = lval;

        return ;

    }

    int mid = (lval + rval) >> 1, lt = 0, rt = 0;

    for (int i = st; i <= ed; i++) {

        if (q[i].id == 0) {

            if (q[i].k > 0 && q[i].k > mid) Add(L[q[i].u], 1), rq[++rt] = q[i];

            else if (q[i].k < 0 && -q[i].k > mid) Add(L[q[i].u], -1), rq[++rt] = q[i];

            else lq[++lt] = q[i];

        } else {

            int res = Sum(q[i].u, q[i].v);

            if (res < q[i].k) q[i].k -= res, lq[++lt] = q[i];

            else rq[++rt] = q[i];

        }

    }

    for (int i = st; i <= ed; i++)

        if (q[i].id == 0) {

            if (q[i].k > 0 && q[i].k > mid) Add(L[q[i].u], -1);

            else if (q[i].k < 0 && -q[i].k > mid) Add(L[q[i].u], 1);

        }

    for (int i = 1; i <= lt; i++) q[st + i - 1] = lq[i];

    for (int i = 1; i <= rt; i++) q[st + lt + i - 1] = rq[i];

    Div(lval, mid, st, st + lt - 1);

    Div(mid + 1, rval, st + lt, ed);

}

int main () {

    clearGraph();

    N = gi(), Q = gi();

    fill(&ans[1], &ans[N + 1], 1e9);

    for (cnt = 1; cnt <= N; cnt++) q[cnt] = (Node){cnt, cnt, a[cnt] = gi(), 0};

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

        int u = gi(), v = gi();

        Add_Edge(u, v), Add_Edge(v, u);

    }

    int q_cnt = 0;

    for (int i = 1; i <= N; i++) Add(i, 1);

    dfs1(1); dfs2(1, 1);

    while (Q--) {

        int k = gi(), u = gi(), v = gi();

        if (k == 0) {

            q[++cnt] = (Node){u, u, -a[u], 0};

            q[++cnt] = (Node){u, u, a[u] = v, 0};

        } else {

            q_cnt++;

            if (Sum(u, v) < k) continue;

            q[++cnt] = (Node){u, v, k, q_cnt};

        }

    }

    for (int i = 1; i <= N; i++) Add(i, -1);

    Div(1, 1e8, 1, cnt);

    for (int i = 1; i <= q_cnt; i++) (ans[i] != 1e9) ? printf("%d\n", ans[i]) : puts("invalid request!");

    return 0;

}