题解：P5024 [NOIP 2018 提高组] 保卫王国

· · 题解

[NOIP 2018 提高组] 保卫王国

这道题和 P4719 是同样的。其中 P4719 要求的是最大独立集，而在这一题中，要用最小的点权和覆盖所有边，即求最小覆盖集。而 \text{最小覆盖集}=\text{全集}-\text{最大独立集}，这个可以感性理解。使用此，就可以将这个问题转换为上述的模板题，用动态 DP 解决即可。

此处讲述 O(n\log^2n) 的动态 DP。在求最大独立集的问题中，显然有 O(n) 的 DP，如用 f_{u, 0/1} 表示 u 点选或不选，u 子树满足条件的答案，转移方程：f_{u, 0}=\sum_v \max(f_{v, 0}, f_{v, 1}), f_{u, 1}=val_u+\sum_v f_{v, 0}。然后题目中的对于最小覆盖集的强制选或不选，是对最大独立集的不选或选，即给一个点赋为负无穷大或无穷大。而对于每个询问，只有两个位置的转移方程会有变化，以及其祖先们的答案会有变化。而对于加速一条链向上更新的问题，可以使用树链剖分，然后每个节点只保留其轻儿子的转移，设 g 为仅保留轻儿子的答案，则由 g 得到 f：

\begin{bmatrix}g_{u, 0}&g_{u, 0}\\g_{u, 1}&-\infty\end{bmatrix}\times\begin{bmatrix}f_{v, 0}\\f_{v, 1}\end{bmatrix}=\begin{bmatrix}f_{u, 0}\\f_{u, 1}\end{bmatrix}

由于每个点的 g 存储的信息仅和轻儿子有关，因此当改变某个节点的转移时，只需要更新该节点向上的 O(\log n) 条重链的链顶的父亲即可。查询时只要查根节点向下的一条重链的矩阵的乘积。用线段树维护重链，则对单个节点修改及查询复杂度 O(\log n)，而每次询问有 O(\log n) 个修改查询操作，所以一次询问的总复杂度 O(\log^2n)。

Code

#include <iostream>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <bitset>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define fst first
#define scd second
#define db double
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector <int>
#define pii pair <int, int>
#define sz(x) ((int)x.size())
#define ms(f, x) memset(f, x, sizeof(f))
#define L(i, j, k) for (int i=(j); i<=(k); ++i)
#define R(i, j, k) for (int i=(j); i>=(k); --i)
#define ACN(i, H_u) for (int i=H_u; i; i=E[i].nxt)
using namespace std;
template <typename INT> void rd(INT &res) {
    res=0; bool f=false; char ch=getchar();
    while (ch<'0'||ch>'9') f|=ch=='-', ch=getchar();
    while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48), ch=getchar();
    res=(f?-res:res);
}
template <typename INT, typename...Args>
void rd(INT &x, Args &...y) { rd(x), rd(y...); }
//dfs
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=1e5;
const int N=maxn+10;
int H[N], edge_cnt, fa[N], son[N], dfn[N], idx, top[N], bot[N], sz[N], id[N], n, m; ll f[N][2], sum, a[N];
//wmr
struct Edge { int nxt, to; } E[N<<1];
void add(int u, int v) { E[++edge_cnt]={H[u], v}; H[u]=edge_cnt; }
struct matrix {
    ll f00, f01, f10, f11;
    matrix(): f00(-INF), f01(-INF), f10(-INF), f11(-INF) {}
    matrix(ll f00, ll f01, ll f10, ll f11): f00(f00), f01(f01), f10(f10), f11(f11) {}
    void unit() { f00=f11=0; }
    friend matrix operator * (const matrix &x, const matrix &y) { return matrix(max(x.f00+y.f00, x.f01+y.f10), max(x.f00+y.f01, x.f01+y.f11), max(x.f10+y.f00, x.f11+y.f10), max(x.f10+y.f01, x.f11+y.f11)); }
} b[N]; // 矩阵
struct SegmentTree { int l, r; matrix res; } t[N<<2];
//incra
#define ls (p<<1)
#define rs (p<<1|1)
void build(int p, int l, int r) {
    t[p].l=l, t[p].r=r;
    if (l==r) {
        int u=id[l]; ll g0=0, g1=a[u];
        ACN(i, H[u]) {
            int v=E[i].to;
            if (v==fa[u]||v==son[u]) continue;
            g0+=max(f[v][0], f[v][1]); g1+=f[v][0];
        }
        t[p].res=b[u]=matrix(g0, g0, g1, -INF);
        return;
    }
    int mid=l+r>>1;
    build(ls, l, mid), build(rs, mid+1, r);
    t[p].res=t[ls].res*t[rs].res;
} // 线段树
void pre_dfs(int u, int pre) {
    f[u][1]=a[u];
    ACN(i, H[u]) {
        int v=E[i].to;
        if (v==pre) continue;
        pre_dfs(v, u);
        f[u][0]+=max(f[v][0], f[v][1]);
        f[u][1]+=f[v][0];
    }
}
void dfs1(int u, int pre) {
    fa[u]=pre; sz[u]=1;
    ACN(i, H[u]) {
        int v=E[i].to;
        if (v==pre) continue;
        dfs1(v, u), sz[u]+=sz[v];
        if (sz[v]>sz[son[u]]) son[u]=v;
    }
}
void dfs2(int u, int t) {
    top[u]=t; id[dfn[u]=++idx]=u;
    if (son[u]) dfs2(son[u], t), bot[u]=bot[son[u]];
    else bot[u]=u;
    ACN(i, H[u]) {
        int v=E[i].to;
        if (v==fa[u]||v==son[u]) continue;
        dfs2(v, v);
    }
} // 树链剖分
matrix query(int p, int l, int r) {
    if (l<=t[p].l&&t[p].r<=r) return t[p].res;
    int mid=t[p].l+t[p].r>>1; matrix res; res.unit();
    if (l<=mid) res=res*query(ls, l, r);
    if (mid<r) res=res*query(rs, l, r);
    return res;
}
void update(int p, int x) {
    if (t[p].l==t[p].r) return t[p].res=b[id[x]], void();
    int mid=t[p].l+t[p].r>>1;
    if (x<=mid) update(ls, x);
    else update(rs, x);
    t[p].res=t[ls].res*t[rs].res;
}
void update_node(int u, ll v) {
    b[u].f10+=v-a[u]; a[u]=v;
    while (u) {
        matrix pre=query(1, dfn[top[u]], dfn[bot[u]]);
        update(1, dfn[u]);
        matrix cur=query(1, dfn[top[u]], dfn[bot[u]]);
        u=fa[top[u]]; ll t=max(cur.f00, cur.f10)-max(pre.f00, pre.f10);
        b[u].f00+=t, b[u].f01+=t, b[u].f10+=cur.f00-pre.f00;
    }
} // 动态 DP
//lottle
signed main() {
//  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    rd(n, m, a[0]);
    L(i, 1, n) rd(a[i]), sum+=a[i];
    L(i, 1, n-1) { int u, v; rd(u, v); add(u, v); add(v, u); }
    pre_dfs(1, 0); dfs1(1, 0); dfs2(1, 1);
    build(1, 1, n);
    while (m--) {
        int u, v, x, y; rd(u, x, v, y);
        if ((fa[u]==v||fa[v]==u)&&x==0&&y==0) { puts("-1"); continue; }
        int vu=a[u], vv=a[v];
        update_node(u, x?-INF:INF); update_node(v, y?-INF:INF);
        matrix ret=query(1, dfn[1], dfn[bot[1]]);
        printf("%lld\n", sum-(max(ret.f00, ret.f10)+(x?0:vu-INF)+(y?0:vv-INF)));
        update_node(u, vu); update_node(v, vv);
    }
    return 0;
}