专栏文章

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

bbelot
P5024题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipiczku
此快照首次捕获于
2025/12/03 12:29
3 个月前
此快照最后确认于
2025/12/03 12:29
3 个月前
查看原文

[NOIP 2018 提高组] 保卫王国

这道题和 P4719 是同样的。其中 P4719 要求的是最大独立集，而在这一题中，要用最小的点权和覆盖所有边，即求最小覆盖集。而 最小覆盖集=全集−最大独立集\text{最小覆盖集}=\text{全集}-\text{最大独立集}，这个可以感性理解。使用此，就可以将这个问题转换为上述的模板题，用动态 DP 解决即可。
此处讲述 O(nlog⁡2n)O(n\log^2n) 的动态 DP。在求最大独立集的问题中，显然有 O(n)O(n) 的 DP，如用 fu,0/1f_{u, 0/1} 表示 uu 点选或不选，uu 子树满足条件的答案，转移方程：fu,0=∑vmax⁡(fv,0,fv,1),fu,1=valu+∑vfv,0f_{u, 0}=\sum_v \max(f_{v, 0}, f_{v, 1}), f_{u, 1}=val_u+\sum_v f_{v, 0}。然后题目中的对于最小覆盖集的强制选或不选，是对最大独立集的不选或选，即给一个点赋为负无穷大或无穷大。而对于每个询问，只有两个位置的转移方程会有变化，以及其祖先们的答案会有变化。而对于加速一条链向上更新的问题，可以使用树链剖分，然后每个节点只保留其轻儿子的转移，设 gg 为仅保留轻儿子的答案，则由 gg 得到 ff：
[gu,0gu,0gu,1−∞]×[fv,0fv,1]=[fu,0fu,1]\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}
由于每个点的 gg 存储的信息仅和轻儿子有关，因此当改变某个节点的转移时，只需要更新该节点向上的 O(log⁡n)O(\log n) 条重链的链顶的父亲即可。查询时只要查根节点向下的一条重链的矩阵的乘积。用线段树维护重链，则对单个节点修改及查询复杂度 O(log⁡n)O(\log n)，而每次询问有 O(log⁡n)O(\log n) 个修改查询操作，所以一次询问的总复杂度 O(log⁡2n)O(\log^2n)。
Code
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...