[NOIP2018 提高组]保卫王国

本文主要是介绍[NOIP2018 提高组]保卫王国，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

保卫王国

题解

动态dp板子题。

首先我们明白，对于一棵树，有$最小覆盖集=全集-最大独立集$。
所以，我们可以将这道题转化成求最大独立集去做，相信最大独立集的方法大家都会，如果不会的话可以看看这里动态dp模板
至于必选与不必选的内容，我们可以通过更改点的权值实现，必选就改为$-\infty$，不必选就改为$\infty$。
但这同时还需在dp过程中记录下原来的权值，因为要求答案。

时间复杂度$O(mlo{g}^{2}n)$。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
#define MAXN 100005
#define lowbit(x) (x&-x)
#define reg register
typedef long long LL;
const LL INF=0x7f7f7f7f7f7f;
typedef unsigned long long uLL;
typedef pair<LL,LL> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
int n,m,head[MAXN],tot,idx,ld[MAXN];LL a[MAXN],b[MAXN];
int siz[MAXN],dfn[MAXN],id[MAXN],wson[MAXN],ltp[MAXN],father[MAXN];
struct edge{int to,nxt;}e[MAXN<<1];
struct ming{LL dp,gp;ming(){dp=gp=0;}ming(LL D,LL G){dp=D;gp=G;}ming operator + (const ming rhs)const{return ming(dp+rhs.dp,gp+rhs.gp);}ming operator - (const ming rhs)const{return ming(dp-rhs.dp,gp-rhs.gp);}void friend operator += (ming &x,ming y){x=x+y;}void friend operator -= (ming &x,ming y){x=x-y;}
}g[MAXN][2],f[MAXN][2];
ming Max(ming x,ming y){return x.dp>y.dp?x:y;}
void addEdge(int u,int v){e[++tot]=(edge){v,head[u]};head[u]=tot;}
struct matrix{ming c[2][2];matrix(){for(int i=0;i<2;i++)for(int j=0;j<2;j++)c[i][j]=ming(-INF,-INF);}ming* operator [] (const int &x){return c[x];}matrix operator * (const matrix rhs)const{matrix res;for(int i=0;i<2;i++)for(int k=0;k<2;k++)for(int j=0;j<2;j++)res[i][j]=Max(res[i][j],c[i][k]+rhs.c[k][j]);return res;}void print(){for(int i=0;i<2;i++,puts(""))for(int j=0;j<2;j++)printf("%lld ",c[i][j].gp);}
}val[MAXN],tr[MAXN<<2],I;
void dosaka1(int u,int fa){siz[u]=1;wson[u]=0;father[u]=fa;for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(v==fa)continue;dosaka1(v,u);siz[u]+=siz[v];if(siz[wson[u]]<siz[v])wson[u]=v;}
}
void dosaka2(int u,int tp){ltp[u]=tp;dfn[u]=++idx;g[u][1]=ming(a[u],b[u]);id[idx]=u;if(wson[u])dosaka2(wson[u],tp),ld[u]=ld[wson[u]];for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(v==father[u]||v==wson[u])continue;dosaka2(v,v);g[u][1]+=f[v][0];g[u][0]+=Max(f[v][0],f[v][1]);}if(wson[u])val[u][0][0]=val[u][0][1]=g[u][0],val[u][1][0]=g[u][1],f[u][0]=Max(f[wson[u]][0],f[wson[u]][1])+g[u][0],f[u][1]=g[u][1]+f[wson[u]][0];else f[u][1]=g[u][1],ld[u]=u,val[u][0][0]=val[u][0][1]=ming(0LL,0LL),val[u][1][0]=g[u][1];
}
void build(int rt,int l,int r){if(l>r)return ;int mid=l+r>>1;if(l==r){tr[rt]=val[id[l]];return ;}build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);tr[rt]=tr[rt<<1]*tr[rt<<1|1];
}
void modify(int rt,int l,int r,int ai,matrix aw){if(l>r||l>ai||r<ai)return ;int mid=l+r>>1;if(l==r){tr[rt]=aw;return ;}if(ai<=mid)modify(rt<<1,l,mid,ai,aw);if(ai>mid)modify(rt<<1|1,mid+1,r,ai,aw);tr[rt]=tr[rt<<1]*tr[rt<<1|1];
}
matrix query(int rt,int l,int r,int al,int ar){if(l>r||l>ar||r<al)return I;int mid=l+r>>1;if(al<=l&&r<=ar)return tr[rt];matrix res;if(ar<=mid)return query(rt<<1,l,mid,al,ar);if(al>mid)return query(rt<<1|1,mid+1,r,al,ar);return query(rt<<1,l,mid,al,ar)*query(rt<<1|1,mid+1,r,al,ar);
}
void ChainModify(int x,int y){g[x][1]-=ming(a[x],b[x]);a[x]=y;g[x][1]+=ming(a[x],b[x]);val[x][1][0]=g[x][1];modify(1,1,n,dfn[x],val[x]);x=ltp[x];while(x>1){matrix tmp=query(1,1,n,dfn[x],dfn[ld[x]]);int y=father[x];g[y][1]-=f[x][0];g[y][0]-=Max(f[x][0],f[x][1]);f[x][0]=tmp[0][0];f[x][1]=tmp[1][0];g[y][1]+=f[x][0];g[y][0]+=Max(f[x][0],f[x][1]);val[y][0][0]=val[y][0][1]=g[y][0];val[y][1][0]=g[y][1];modify(1,1,n,dfn[y],val[y]);x=ltp[y];}
}
string typ;
signed main(){freopen("defense.in","r",stdin);freopen("defense.out","w",stdout);read(n);read(m);cin>>typ;LL sum=0;for(int i=1;i<=n;i++)read(a[i]),b[i]=a[i],sum+=a[i];for(int i=1;i<n;i++){int u,v;read(u);read(v);addEdge(u,v);addEdge(v,u);}dosaka1(1,0);dosaka2(1,1);build(1,1,n);for(int i=1;i<=m;i++){int u,v;LL x,y;read(u);read(x);read(v);read(y);if(!x&&!y&&(father[u]==v||father[v]==u)){puts("-1");continue;}ChainModify(u,x?-INF:INF);ChainModify(v,y?-INF:INF);matrix tmp=query(1,1,n,dfn[1],dfn[ld[1]]);printf("%lld\n",sum-Max(tmp[0][0],tmp[1][0]).gp);ChainModify(u,b[u]);ChainModify(v,b[v]);}return 0;
}

谢谢！！！

这篇关于[NOIP2018 提高组]保卫王国的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---