Chlience

【题解】BZOJ 4712 洪水
Problem给定一棵 $n$ 个节点的树,每个节点有点权 $a[i]$接下来有 $m$ 个操作:Q x 询问以 ...
扫描右侧二维码阅读全文
22
2019/02

【题解】BZOJ 4712 洪水

Problem

给定一棵 $n$ 个节点的树,每个节点有点权 $a[i]$
接下来有 $m$ 个操作:

  1. Q x 询问以 $x$ 为根的子树与 $x$ 完全断开需要的最小费用
  2. C x to 将点 $x$ 的权值加上 $to$

Thought

显然有 $DP$ 方程:

$$ f[x]=min(val[x],\sum_{y\in son[x]}f[y]) $$

我们记录每个点的 $sum[x]=\sum_{y\in son[x]}f[y]$
那么每次修改有对于一段连续的节点有

$$ \begin{cases} f[x]=val[x] & val[x]\leq sum[x]+to\\ f[x]=sum[x]+to & val[x]>sum[x]+to \end{cases} $$

  1. $val[x]\leq sum[x]<sum[x]+to$ ,那么这次增加费用对其没有影响
  2. $sum[x]<val[x]< sum[x]+to$ ,那么这次增加的费用为 $val[x]-sum[x]$
  3. 若有 $sum[x]<sum[x]+to\leq val[x]$ ,那么这次增加的费用为 $to$

从下往上考虑,对于连续的一段 $3$ 情况的点,可以直接区间更新
紧接着遇到 $2$ 情况,则将 $to$ 修改为 $val[x]-sum[x]$ ,递归进行
若遇到 $1$ 情况或者走到了根,退出

由于 $sum[x]<val[x]<sum[x]+to$ 的点次不超过 $n+m$ (一开始就 $sum[x]<val[x]$ 或者在某次修改中使得 $sum[x]<val[x]$,并且每次遇到一个这样的点就会将其修改为 $val[x]\leq sum[x]$)

所以可以考虑线段树 + 树剖来维护,总复杂度 $O((n+m)\log^2 n)$

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
typedef long long LL;
#define L (x << 1)
#define R (x << 1 | 1)
#define mid ((l + r) >> 1)
LL read() {
    LL ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
struct Tree {
    LL val[N << 2], sum[N << 2], del[N << 2];
    void update(int x) {
        del[x] = min(del[L], del[R]) - sum[x];
    }
    void pushdown(int x) {
        sum[L] += sum[x]; sum[R] += sum[x];
        del[L] -= sum[x]; del[R] -= sum[x];
        sum[x] = 0;
    }
    void changePoint(int x, int l, int r, int pos, LL Val, LL Sum) {
        if(l == r) {
            val[x] = Val; sum[x] = Sum;
            del[x] = val[x] - sum[x];
        }
        else {
            pushdown(x);
            if(pos <= mid)
                changePoint(L, l, mid, pos, Val, Sum);
            else
                changePoint(R, mid + 1, r, pos, Val, Sum);
            update(x);
        }
    }
    void build(int x, int l, int r, LL* V, LL* S, int* dfn) {
        if(l == r) {
            val[x] = V[dfn[l]]; sum[x] = S[dfn[l]];
            del[x] = val[x] - sum[x];
        }
        else {
            build(L, l, mid, V, S, dfn);
            build(R, mid + 1, r, V, S, dfn);
            update(x);
        }
    }
    LL getSum(int x, int l, int r, int pos) {
        if(l == r)
            return sum[x];
        else {
            pushdown(x);
            if(pos <= mid)
                return getSum(L, l, mid, pos);
            else
                return getSum(R, mid + 1, r, pos);
            update(x);
        }
    }
    int queryDelta(int x, int l, int r, int ll, int rr, int key) {
        if(l == r)
            return del[x] >= key ? 0 : l;
        else {
            pushdown(x);
            if(l >= ll && r <= rr && del[x] >= key)
                return 0;
            int opt = 0;
            if(mid < rr) opt = queryDelta(R, mid + 1, r, ll, rr, key);
            if(opt) return opt;
            if(mid >= ll) opt = queryDelta(L, l, mid, ll, rr, key);
            return opt;
        }
    }
    void change(int x, int l, int r, int ll, int rr, int key) {
        if(ll > rr) return;
        if(l >= ll && r <= rr) {
            sum[x] += key;
            del[x] -= key;
        }
        else {
            pushdown(x);
            if(mid >= ll) change(L, l, mid, ll, rr, key);
            if(mid < rr) change(R, mid + 1, r, ll, rr, key);
            update(x);
        }
    }
}t;

struct Edge {
    int t, n;
}e[N << 1];
int head[N], tot;
void addedge(int u, int v) {
    e[++ tot] = {v, head[u]};
    head[u] = tot;
}
int dfn[N], id[N], DFN, siz[N], son[N], fa[N], top[N];
LL val[N], sum[N], f[N];
int n;
char opt[10];
void dfs1(int x, int _f) {
    fa[x] = _f; siz[x] = 1;
    for(int i = head[x]; i; i = e[i].n) {
        if(e[i].t == fa[x]) continue;
        dfs1(e[i].t, x);
        siz[x] += siz[e[i].t];
        if(siz[e[i].t] > siz[son[x]])
            son[x] = e[i].t;
    }
}
void dfs2(int x, int _top) {
    dfn[++ DFN] = x; id[x] = DFN;
    top[x] = _top;
    if(son[x])
        dfs2(son[x], _top);
    else
        sum[x] = LONG_LONG_MAX / 3;
    sum[x] += f[son[x]];
    for(int i = head[x]; i; i = e[i].n) {
        if(e[i].t == fa[x] || e[i].t == son[x]) continue;
        dfs2(e[i].t, e[i].t);
        sum[x] += f[e[i].t];
    }
    f[x] = min(val[x], sum[x]);
}
LL getAns(int x) {
    return min(val[x], t.getSum(1, 1, n, id[x]));
}
void solve(int x, LL y) {
    LL Sum = t.getSum(1, 1, n, id[x]);
    
    LL pre = getAns(x);
    val[x] += y;
    t.changePoint(1, 1, n, id[x], val[x], Sum);
    LL now = getAns(x);

    x = fa[x];
    y = now - pre;
    while(x && y) {
        int last = t.queryDelta(1, 1, n, id[top[x]], id[x], y);
        last = dfn[last];
        if(last) {
            t.change(1, 1, n, id[last] + 1, id[x], y);
            Sum = t.getSum(1, 1, n, id[last]);

            pre = getAns(last);
            Sum += y;
            t.changePoint(1, 1, n, id[last], val[last], Sum);
            now = getAns(last);

            x = fa[last];
            y = now - pre;
        }
        else {
            t.change(1, 1, n, id[top[x]], id[x], y);
            x = fa[top[x]];
        }
    }
}
int main() {
    n = read();
    for(int i = 1; i <= n; ++ i)
        val[i] = read();
    for(int i = 1; i < n; ++ i) {
        int u = read(), v = read();
        addedge(u, v);
        addedge(v, u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    t.build(1, 1, n, val, sum, dfn);
    int m = read();
    while(m --) {
        scanf("%s", opt);
        if(opt[0] == 'C') {
            LL x = read(), y = read();
            solve(x, y);
        }
        else {
            LL x = read();
            printf("%lld\n", getAns(x));
        }
    }
    return 0;
}
Last modification:February 22nd, 2019 at 07:24 pm

Leave a Comment