正題

題目鏈接:https://www.luogu.org/problem/P5024

---

題目大意

一棵樹，每次有要求
$axby:$表示$a$點是否必選和$b$點是否必選

然后每次求最小覆蓋集。

---

解題思路

最小覆蓋集=全集-最大獨立集
所以我們每次必選不選就用$+inf$或$?inf$處理即可
之后就是動態dp的模板了：
https://blog.csdn.net/Mr_wuyongcong/article/details/95033161

但貌似樹剖最后一個點會被卡飛，吸口氧就莫得問題了(當然$LCT$也是沒問題的)

---

$code$

#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") %:pragma GCC optimize("-fgcse") %:pragma GCC optimize("-fgcse-lm") %:pragma GCC optimize("-fipa-sra") %:pragma GCC optimize("-ftree-pre") %:pragma GCC optimize("-ftree-vrp") %:pragma GCC optimize("-fpeephole2") %:pragma GCC optimize("-ffast-math") %:pragma GCC optimize("-fsched-spec") %:pragma GCC optimize("unroll-loops") %:pragma GCC optimize("-falign-jumps") %:pragma GCC optimize("-falign-loops") %:pragma GCC optimize("-falign-labels") %:pragma GCC optimize("-fdevirtualize") %:pragma GCC optimize("-fcaller-saves") %:pragma GCC optimize("-fcrossjumping") %:pragma GCC optimize("-fthread-jumps") %:pragma GCC optimize("-funroll-loops") %:pragma GCC optimize("-fwhole-program") %:pragma GCC optimize("-freorder-blocks") %:pragma GCC optimize("-fschedule-insns") %:pragma GCC optimize("inline-functions") %:pragma GCC optimize("-ftree-tail-merge") %:pragma GCC optimize("-fschedule-insns2") %:pragma GCC optimize("-fstrict-aliasing") %:pragma GCC optimize("-fstrict-overflow") %:pragma GCC optimize("-falign-functions") %:pragma GCC optimize("-fcse-skip-blocks") %:pragma GCC optimize("-fcse-follow-jumps") %:pragma GCC optimize("-fsched-interblock") %:pragma GCC optimize("-fpartial-inlining") %:pragma GCC optimize("no-stack-protector") %:pragma GCC optimize("-freorder-functions") %:pragma GCC optimize("-findirect-inlining") %:pragma GCC optimize("-fhoist-adjacent-loads") %:pragma GCC optimize("-frerun-cse-after-loop") %:pragma GCC optimize("inline-small-functions") %:pragma GCC optimize("-finline-small-functions") %:pragma GCC optimize("-ftree-switch-conversion") %:pragma GCC optimize("-foptimize-sibling-calls") %:pragma GCC optimize("-fexpensive-optimizations") %:pragma GCC optimize("-funsafe-loop-optimizations") %:pragma GCC optimize("inline-functions-called-once") %:pragma GCC optimize("-fdelete-null-pointer-checks") #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll Size=2,N=1e5+100,inf=(1ll<<60); ll n,m,tot,cnt,ls[N],fa[N],v[N],f[N][2],sum; ll seg[N],id[N],top[N],siz[N],son[N],ed[N]; struct matrix{ll a[Size][Size]; }val[N]; matrix operator*(matrix a,matrix b) {matrix c;memset(c.a,0,sizeof(c.a));for(ll i=0;i<Size;i++)for(ll j=0;j<Size;j++)for(ll k=0;k<Size;k++)c.a[i][j]=max(c.a[i][j],a.a[i][k]+b.a[k][j]);return c; } struct Tree_node{ll l,r;matrix g; }; struct Edge_node{ll to,next; }a[N<<1]; struct Line_cut_tree{Tree_node t[N<<2];void Build(ll x,ll l,ll r){t[x].l=l;t[x].r=r;if(l==r){ll u=seg[l],g0=0,g1=v[seg[l]];for(ll i=ls[u];i;i=a[i].next){ll y=a[i].to;if(y==fa[u]||y==son[u]) continue;g0+=max(f[y][0],f[y][1]),g1+=f[y][0];}t[x].g.a[0][0]=t[x].g.a[0][1]=g0;t[x].g.a[1][0]=g1;val[l]=t[x].g;return;}ll mid=(l+r)/2;Build(x*2,l,mid);Build(x*2+1,mid+1,r);t[x].g=t[x*2].g*t[x*2+1].g;}matrix Query(ll x,ll l,ll r){if(t[x].l==l&&t[x].r==r)return t[x].g;if(t[x*2].r>=r) return Query(x*2,l,r);if(t[x*2+1].l<=l) return Query(x*2+1,l,r);return Query(x*2,l,t[x*2].r)*Query(x*2+1,t[x*2+1].l,r);}void Change(ll x,ll z){if(t[x].l==t[x].r){t[x].g=val[t[x].l];return;}if(t[x*2].r>=z) Change(x*2,z);else Change(x*2+1,z);t[x].g=t[x*2].g*t[x*2+1].g;} }Tree; void addl(ll x,ll y) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void dfs1(ll x,ll Fa) {siz[x]++;fa[x]=Fa;f[x][1]=max(v[x],0ll);for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==Fa)continue;dfs1(y,x);f[x][0]+=max(f[y][0],f[y][1]);f[x][1]+=f[y][0];siz[x]+=siz[y];if(siz[y]>siz[son[x]]) son[x]=y;} } void dfs2(ll x,ll fa) {id[x]=++cnt;seg[cnt]=x;if(son[x]){top[son[x]]=top[x];dfs2(son[x],x);}else ed[top[x]]=cnt;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa||y==son[x]) continue;top[y]=y;dfs2(y,x);} } matrix ask(ll x) {return Tree.Query(1,id[top[x]],ed[top[x]]);} void path_change(ll x,ll w) {val[id[x]].a[1][0]+=w-v[x];v[x]=w;matrix old,news;while(x){old=ask(top[x]);Tree.Change(1,id[x]);news=ask(top[x]);x=fa[top[x]];val[id[x]].a[0][0]+=max(news.a[0][0],news.a[1][0])-max(old.a[0][0],old.a[1][0]);val[id[x]].a[0][1]=val[id[x]].a[0][0];val[id[x]].a[1][0]+=news.a[0][0]-old.a[0][0];} } int main() {char rubbish[3];scanf("%lld%lld%s",&n,&m,rubbish);for(ll i=1;i<=n;i++)scanf("%lld",&v[i]),sum+=v[i];for(ll i=1;i<n;i++){ll x,y;scanf("%lld%lld",&x,&y);addl(x,y);addl(y,x);}top[1]=1;dfs1(1,0);dfs2(1,0);Tree.Build(1,1,n);matrix ans;while(m--){ll a,x,b,y;scanf("%lld%lld%lld%lld",&a,&x,&b,&y);if(!x) path_change(a,v[a]+inf);else path_change(a,v[a]-inf);if(!y) v[b],path_change(b,v[b]+inf);else path_change(b,v[b]-inf);sum+=((x^1)+(y^1))*inf;ans=ask(1);ll answer=sum-max(ans.a[0][0],ans.a[1][0]);if(answer>inf) printf("-1\n");else printf("%lld\n",answer);if(!x) path_change(a,v[a]-inf);else path_change(a,v[a]+inf);if(!y) v[b],path_change(b,v[b]-inf);else path_change(b,v[b]+inf);sum-=((x^1)+(y^1))*inf;} }

總結

以上是生活随笔為你收集整理的P5024-保卫王国【动态dp,最小覆盖集】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。