[NOIP2018TG]保卫王国

BZOJ

luogu

当动态dp模板题写的,(全集-最大点权独立集)不能放军队的+inf,必须放军队-inf即可

注意矩阵乘法的顺序问题

#define ll long long

#define ls x<<1,l,mid

#define rs x<<1|1,mid+1,r

#include<bits/stdc++.h>

using namespace std;

const int _=1e5+5,inf=1e9;

int re(){

    int x=0,w=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*w;

}

int n,m,cnt,ts;

int h[_],p[_],fa[_],sz[_],son[_],top[_],dfn[_],id[_],ed[_];

ll sum,Ans,f[2][_];

string type;

struct edge{int to,next,w;}e[_<<1];

struct Mx{

    ll g[2][2];

    Mx(){memset(g,0,sizeof(g));}

}t[_<<2],val[_];

Mx operator *(Mx x,Mx y){

    Mx z;

    for(int i=0;i<2;i++)

        for(int j=0;j<2;j++)

            for(int k=0;k<2;k++)

                z.g[i][j]=max(z.g[i][j],x.g[i][k]+y.g[k][j]);

    return z;

}

void link(int u,int v){

    e[++cnt]=(edge){v,h[u]};h[u]=cnt;

    e[++cnt]=(edge){u,h[v]};h[v]=cnt;

}

void dfs(int u){

    sz[u]=1;

    for(int i=h[u];i;i=e[i].next){

        int v=e[i].to;

        if(v==fa[u])continue;

        fa[v]=u;dfs(v);sz[u]+=sz[v];

        if(sz[v]>sz[son[u]])son[u]=v;

    }

}

void dfs(int u,int tp){

    top[u]=tp;id[dfn[u]=++ts]=u;

    if(son[u])dfs(son[u],tp);

    else ed[top[u]]=ts;

    for(int i=h[u];i;i=e[i].next){

        int v=e[i].to;

        if(v^fa[u]&&v^son[u])dfs(v,v);

    }

}

void dp(int u){

    f[1][u]=p[u];

    for(int i=h[u];i;i=e[i].next){

        int v=e[i].to;

        if(v==fa[u])continue;

        dp(v);

        f[0][u]+=max(f[1][v],f[0][v]);

        f[1][u]+=f[0][v];

    }

}

void pu(int x){t[x]=t[x<<1]*t[x<<1|1];}

void bu(int x,int l,int r){

    if(l==r){

        t[x].g[0][0]=t[x].g[0][1]=f[0][id[l]]-max(f[0][son[id[l]]],f[1][son[id[l]]]);

        t[x].g[1][0]=f[1][id[l]]-f[0][son[id[l]]];t[x].g[1][1]=-inf;val[l]=t[x];return;

    }

    int mid=(l+r)>>1;bu(ls);bu(rs);pu(x);

}

void upd(int x,int l,int r,int k){

    if(l==r){t[x]=val[k];return;}

    int mid=(l+r)>>1;

    if(k<=mid)upd(ls,k);else upd(rs,k);pu(x);

}

Mx query(int x,int l,int r,int ql,int qr){

    if(ql<=l&&r<=qr)return t[x];

    int mid=(l+r)>>1;

    if(qr<=mid)return query(ls,ql,qr);

    if(ql>mid)return query(rs,ql,qr);

    return query(ls,ql,qr)*query(rs,ql,qr);

}

void modify(int u,int v){

    val[dfn[u]].g[1][0]+=v;

    Mx od,nw;

    while(u){

        od=query(1,1,n,dfn[top[u]],ed[top[u]]);

        upd(1,1,n,dfn[u]);

        nw=query(1,1,n,dfn[top[u]],ed[top[u]]);

        u=fa[top[u]];

        val[dfn[u]].g[0][0]+=max(nw.g[0][0],nw.g[1][0])-max(od.g[0][0],od.g[1][0]);

        val[dfn[u]].g[0][1]=val[dfn[u]].g[0][0];

        val[dfn[u]].g[1][0]+=nw.g[0][0]-od.g[0][0];

    }

}

int main(){

    n=re(),m=re();cin>>type;

    for(int i=1;i<=n;i++)p[i]=re(),sum+=p[i];

    for(int i=1,u,v;i<n;i++){

        u=re(),v=re();link(u,v);

    }

    dfs(1);dfs(1,1);dp(1);bu(1,1,n);

    while(m--){

        int a=re(),x=re(),b=re(),y=re();

        if(!x&&!y&&(fa[a]==b||fa[b]==a)){puts("-1");continue;}

        if(x)modify(a,-inf);

        else modify(a,inf),sum+=inf;

        if(y)modify(b,-inf);

        else modify(b,inf),sum+=inf;

        Mx ans=query(1,1,n,dfn[1],ed[1]);

        Ans=sum-max(ans.g[1][0],ans.g[0][0]);

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

        if(x)modify(a,inf);

        else modify(a,-inf),sum-=inf;

        if(y)modify(b,inf);

        else modify(b,-inf),sum-=inf;

    }

    return 0;

}