「NOIP2018 保卫王国」

强制选点我们可以把那个点权搞成\(-inf\)，强制不选我们搞成\(inf\)，之后就真的成为动态\(dp\)的板子题了

由于不想像板子那样再写一个最大独立集的方程，之后利用最小点覆盖=总点权-最大独立集的做法，而直接写了一个最小点覆盖的方程，所以写出了很多锅

矩阵里存放相同意义变量的位置可能真实值不相等，于是要取一个\(min\)

突然发现自己好像也没有写出多少锅，那就这样吧

代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<map>

#define mp std::make_pair

#define LL long long

#define re register

#define maxn 100005

inline int read() {

    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

const LL inf=5e15;

const LL Inf=5e10;

typedef std::pair<int,int> pii;

std::map<pii,int> ma;

char opt[6];

struct E{int v,nxt;}e[maxn<<1];

struct mat{LL a[2][2];}d[maxn*4];

int n,m,num,__;

int l[maxn*4],r[maxn*4];

int sum[maxn],son[maxn],deep[maxn],head[maxn],top[maxn],bot[maxn];

LL dp[maxn][2],f[maxn][2];int dfn[maxn],id[maxn],pos[maxn],fa[maxn],a[maxn];

inline LL min(LL a,LL b) {return a<b?a:b;}

inline LL max(LL a,LL b) {return a>b?a:b;}

inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}

inline mat operator*(mat a,mat b) {

    mat c;

    c.a[0][0]=min(a.a[0][0]+b.a[0][0],a.a[0][1]+b.a[1][0]);

    c.a[0][1]=min(a.a[0][1]+b.a[1][1],a.a[0][0]+b.a[0][1]);

    c.a[1][0]=min(a.a[1][0]+b.a[0][0],a.a[1][1]+b.a[1][0]);

    c.a[1][1]=min(a.a[1][1]+b.a[1][1],a.a[1][0]+b.a[0][1]);

    return c;

}

void dfs1(int x) {

    sum[x]=1;int maxx=-1;

    for(re int i=head[x];i;i=e[i].nxt) {

        if(deep[e[i].v]) continue;

        deep[e[i].v]=deep[x]+1;fa[e[i].v]=x;

        dfs1(e[i].v);sum[x]+=sum[e[i].v];

        if(sum[e[i].v]>maxx) maxx=sum[e[i].v],son[x]=e[i].v;

    }

}

int dfs2(int x,int topf) {

    top[x]=topf,dfn[x]=++__,id[__]=x;

    if(!son[x]) return bot[x]=x;

    bot[x]=dfs2(son[x],topf);

    for(re int i=head[x];i;i=e[i].nxt) {

        if(top[e[i].v]) continue;

        dfs2(e[i].v,e[i].v);

    }

    return bot[x];

}

inline void pushup(int i) {d[i]=d[i<<1]*d[i<<1|1];}

void build(int x,int y,int i) {

    l[i]=x,r[i]=y;

    if(x==y) {

        int now=id[x];pos[now]=i;

        for(re int j=head[now];j;j=e[j].nxt) {

            if(deep[e[j].v]<deep[now]||e[j].v==son[now]) continue;

            dp[now][1]+=min(dp[e[j].v][0],dp[e[j].v][1]);

            dp[now][0]+=dp[e[j].v][1];

        }

        f[now][0]=dp[now][0];f[now][1]=dp[now][1];dp[now][1]+=a[now];

        d[i].a[0][0]=inf,d[i].a[0][1]=dp[now][0];

        d[i].a[1][0]=d[i].a[1][1]=dp[now][1];

        if(son[now])

            dp[now][1]+=min(dp[son[now]][0],dp[son[now]][1]),dp[now][0]+=dp[son[now]][1];

        return;

    }

    int mid=x+y>>1;

    build(mid+1,y,i<<1|1),build(x,mid,i<<1);pushup(i);

}

mat query(int x,int y,int i) {

    if(x<=l[i]&&y>=r[i]) return d[i];

    int mid=l[i]+r[i]>>1;

    if(y<=mid) return query(x,y,i<<1);

    if(x>mid) return query(x,y,i<<1|1);

    return query(x,y,i<<1)*query(x,y,i<<1|1);

}

inline void updata(int i,mat val) {d[i]=val;while(i) {i>>=1;pushup(i);}}

inline void change(int x,LL val) {

    mat pre=query(dfn[top[x]],dfn[bot[x]],1);

    mat t;

    t.a[0][0]=inf,t.a[0][1]=f[x][0],t.a[1][0]=t.a[1][1]=f[x][1]+val;

    updata(pos[x],t);

    while(1) {

        if(top[x]==1) return;

        mat now=query(dfn[top[x]],dfn[bot[x]],1);

        mat t=d[pos[fa[top[x]]]];

        t.a[0][1]-=pre.a[1][1];

        t.a[0][1]+=now.a[1][1];

        t.a[1][1]-=min(pre.a[0][1],pre.a[1][1]);

        t.a[1][1]+=min(now.a[0][1],now.a[1][1]);

        t.a[1][0]=t.a[1][1];

        x=fa[top[x]];

        pre=query(dfn[top[x]],dfn[bot[x]],1);

        updata(pos[x],t);

    }

}

signed main() {

    n=read(),m=read();scanf("%s",opt);int x,y,A,B;

    for(re int i=1;i<=n;i++) a[i]=read();

    for(re int i=1;i<n;i++) {

         x=read(),y=read();

         if(x>y) std::swap(x,y);ma[mp(x,y)]=1;

         add(x,y),add(y,x);

    }

    deep[1]=1,dfs1(1),dfs2(1,1),build(1,n,1);

    while(m--) {

        x=read(),A=read(),y=read(),B=read();

        if(!A&&!B&&ma[mp(min(x,y),max(x,y))]) {puts("-1");continue;}

        if(deep[x]>deep[y]) std::swap(x,y),std::swap(A,B);

        if(A) change(x,-1ll*Inf+a[x]);

            else change(x,Inf+a[x]);

        if(B) change(y,-1ll*Inf+a[y]);

            else change(y,Inf+a[y]);

        mat now=query(1,dfn[bot[1]],1);

        LL ans=min(now.a[0][1],now.a[1][1]);

        if(A) ans+=Inf;

        if(B) ans+=Inf;

        printf("%lld\n",ans);

        change(y,a[y]);change(x,a[x]);

    }

    return 0;

}

巴特西

「NOIP2018 保卫王国」

最新文章

热门文章