bzoj5210最大连通子块和（动态dp+卡常好题）

卡了一晚上，经历了被卡空间，被卡T，被卡数组等一堆惨惨的事情之后，终于在各位大爹的帮助下过了这个题qwqqq

（全网都没有用矩阵转移的动态dp，让我很慌张）

首先，我们先考虑一个比较基础的$dp$

我们令$dp1[i]$表示必须选$i$的最大连通块的权值是多少。

然后令$ans1[i]$表示$i$的子树中的$dp1$的最大值。

那么该怎么计算这两个数组呢。

首先$$dp1[i] = dp1[i]+max(0,dp1[p])$$ 其中$p$是$i$的儿子。

\[ans1[i]=max(ans1[i],ans1[p]),ans1[i]=max(ans1[i],dp1[i])
\]

那么朴素的$dp$大概就是这样。

应该如何去优化呢。

由于是树上问题，不难想到树链剖分然后划分出轻重儿子。

我们令$g$表示考虑重儿子的$dp$数组，$ans$表示考虑重儿子的$max$数组。

然后$f,ans1$分别表示不考虑重儿子的$dp和max$数组。

若$p$是$x$的重儿子的话

不难发现，$g[x]=max(f[x],g[p]+f[x]),ans[x]=max(ans1[x],max(ans[p],g[p]+f[x]))$

我们这里默认$ans1[x]$一开始和$f[x]$取过$max$.

那么我们就可以直接构造如下矩阵

f[x] f[x] -inf

-inf 0 -inf

f[x] ans1[x] 0

来进行转移（注意特判链尾）

但是有一个需要注意的地方，就是我们的$ans1[x]$由于涉及到修改，所以需要一个可删堆（或者$multiset$）

来进行维护，感觉$modify$的时候还是有很多细节。qwq懒得写太多了，直接看代码吧。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<vector>

#include<queue>

#include<cmath>

#include<map>

#include<set>

#define pb push_back

#define mk make_pair

#define ll long long

#define lson ch[x][0]

#define rson ch[x][1]

#define rint register int

using namespace std;

//char buf[100010],*buff = buf + 100000;

//#define getchar() (buff == buf + 100000 ? (fread(buf,1,100000,stdin),buff = buf) : 0,*buff++)

inline int read()

{

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

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 2e5+1e2;

const int maxm = 2*maxn;

const ll inf = -1e15;

struct Node{

    priority_queue<ll> q1,q2;

    inline void push(ll x) {q1.push(x);}

    inline void erase(ll x) {q2.push(x);}

    inline ll top(){while ((!q2.empty()) && (q1.top()==q2.top())) q1.pop(),q2.pop(); return q1.top();}

};

Node ans[maxn];

struct Ju{

   int x,y;

   ll a[3][3];

   Ju operator * (Ju b)

   {

       Ju ans;

       ans.x=x;

       ans.y=b.y;

       for (rint i=0;i<=ans.x;++i)

       {

           for (rint j=0;j<=ans.y;++j)

           {

		      ll uu = inf;

		      for (rint k=0;k<=y;++k)

                uu=max(uu,a[i][k]+b.a[k][j]);

              ans.a[i][j]=uu;

           }

       }

       return ans;

   }

};

int point[maxn],nxt[maxm],to[maxm];

int cnt,n,m;

int top[maxn],newnum[maxn],fa[maxn],son[maxn],size[maxn];

Ju f[4*maxn];

//Ju pre[maxn];

ll dp1[maxn],dp[maxn];

ll ans1[maxn];

int back[maxn];

int tot;

int tail[maxn];

ll val[maxn];

int leaf[maxn];

Ju caonima;

struct pp{

    ll cao,kao;

};

pp cnm[maxn];

inline void addedge(int x,int y)

{

    nxt[++cnt]=point[x];

    to[cnt]=y;

    point[x]=cnt;

}

inline void up(int root)

{

    f[root]=f[2*root+1]*f[2*root];

}

void build(int root,int l,int r)

{

    if (l==r)

    {

        int ymh = back[l];

        if (tail[top[ymh]]==ymh)

        {

            f[root].x=0;

            f[root].y=2;

            f[root].a[0][0]=dp[ymh];

            f[root].a[0][1]=max(dp[ymh],0ll);

        }

        else

        {   f[root].x=f[root].y=2;

            f[root].a[0][0]=dp[ymh];

            f[root].a[0][1]=dp[ymh];

            f[root].a[0][2]=inf;

            f[root].a[1][0]=inf;

            f[root].a[1][2]=inf;

            f[root].a[2][0]=dp[ymh];

            f[root].a[2][1]=ans[ymh].top();

        }

        leaf[ymh]=root;

        return;

    }

    int mid = l+r >> 1;

    build(root<<1,l,mid);

    build(root<<1|1,mid+1,r);

    up(root);

}

void update(int root,int l,int r,int x)

{

    if (l==r)

    {

        f[root]=caonima;

        return;

    }

    int mid = l+r >> 1;

    if (x<=mid) update(root<<1,l,mid,x);

    else update(root<<1|1,mid+1,r,x);

    up(root);

}

Ju query(int root,int l,int r,int x,int y)

{

    if(x<=l && r<=y)

    {

        return f[root];

    }

    int mid = l+r >> 1;

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

    if (x>mid) return query(root<<1|1,mid+1,r,x,y);

    return query(root<<1|1,mid+1,r,x,y)*query(root<<1,l,mid,x,y);

}

void dfs1(int x,int faa)

{

    size[x]=1;

    int maxson=-1;

    for (int i=point[x];i;i=nxt[i])

    {

        int p = to[i];

        if (p==faa) continue;

        fa[p]=x;

        dfs1(p,x);

        size[x]+=size[p];

        if (size[p]>maxson)

        {

            maxson=size[p];

            son[x]=p;

        }

    }

}

void dfs2(int x,int chain)

{

    top[x]=chain;

    tail[chain]=x;

    newnum[x]=++tot;

    back[tot]=x;

    if (!son[x]) return;

    dfs2(son[x],chain);

    for (int i=point[x];i;i=nxt[i])

    {

        int p = to[i];

        if (!newnum[p]) dfs2(p,p);

    }

}

void solve(int x,int fa)

{

    dp[x]=dp1[x]=val[x];

    ans1[x]=val[x];

    for (rint i=point[x];i;i=nxt[i])

    {

        int p = to[i];

        if (p==fa) continue;

        solve(p,x);

        dp1[x]=max(dp1[x],dp1[x]+dp1[p]);

        ans1[x]=max(ans1[x],ans1[p]);

        if (p!=son[x]) dp[x]=max(dp[x],dp[x]+dp1[p]),ans[x].push(ans1[p]);

    }

    ans[x].push(dp[x]);

    ans[x].push(0);

    //cout<<x<<endl;

    ans1[x]=max(ans1[x],dp1[x]);

    ans1[x]=max(ans1[x],0ll);

    //cout<<x<<endl;

}

void modify(int x,ll y)

{

    Ju tmp = f[leaf[x]];

    if (tail[top[x]]==x)

    {

        tmp.a[0][0]+=y-val[x];

        tmp.a[0][1]=max(0ll,tmp.a[0][0]);

    }

    else

    {

        ans[x].erase(tmp.a[0][0]);

        tmp.a[0][0]+=y-val[x];

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

        ans[x].push(tmp.a[0][0]);

        tmp.a[2][0]=tmp.a[0][0];

        tmp.a[2][1]=ans[x].top();

    }

    val[x]=y;

    caonima=tmp;

    update(1,1,n,newnum[x]);

    //cout<<x<<" "<<top[x]<<endl;

    for (rint now = top[x];now!=1;now=top[now])

    {

        //cout<<now<<endl;

        int faa = fa[now];

        //Ju ymh = query(1,1,n,newnum[faa],newnum[faa]);

        Ju ymh = f[leaf[faa]];

        Ju lyf;

        if (newnum[now]!=newnum[tail[top[now]]])

          lyf= query(1,1,n,newnum[now],newnum[tail[top[now]]]);

        else

          lyf = f[leaf[now]];

        ans[faa].erase(cnm[now].kao);

        ans[faa].erase(ymh.a[0][0]);

        ymh.a[0][0]+=max(lyf.a[0][0],0ll)-max(cnm[now].cao,0ll);

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

        ymh.a[2][0]=ymh.a[0][0];

        ans[faa].push(ymh.a[0][0]);

        ans[faa].push(lyf.a[0][1]);

        ymh.a[2][1]=ans[faa].top();

        caonima=ymh;

        update(1,1,n,newnum[faa]);

        cnm[now].kao=lyf.a[0][1];

        cnm[now].cao=lyf.a[0][0];

        now=fa[now];

    }

}

int q;

char c;

signed main()

{

  //freopen("5210.in","r",stdin);

  //freopen("ymh.out","w",stdout);

  n=read(),q=read();

  //cout<<n<<" "<<q<<endl;

  for (rint i=1;i<=n;i++) val[i]=read();

  for (rint i=1;i<n;i++)

  {

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

      addedge(x,y);

      addedge(y,x);

  }

  dfs1(1,0);

  dfs2(1,1);

  solve(1,0);

  //cout<<1<<endl;

  build(1,1,n);

  //cout<<ans1[2]<<" "<<dp[2]<<" "<<dp1[2]<<endl;

  for (rint i=1;i<=n;++i)

  {

     Ju ymh = query(1,1,n,newnum[i],newnum[tail[top[i]]]);

     cnm[i].cao=ymh.a[0][0];

     cnm[i].kao=ymh.a[0][1];

  }

  for (rint i=1;i<=q;++i)

  {

      c=getchar();

      while (c<'A' || c>'Z') c=getchar();

      if (c=='M')

      {

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

         modify(x,y);

      }

      else

      {

         int x=read();

         Ju ymh = query(1,1,n,newnum[x],newnum[tail[top[x]]]);

         cout<<max(ymh.a[0][1],max(ymh.a[0][0],0ll))<<"\n";

      }

  }

  return 0;

}

巴特西

bzoj5210最大连通子块和（动态dp+卡常好题）

最新文章

热门文章

巴特西

bzoj5210最大连通子块和 （动态dp+卡常好题）

最新文章

热门文章

bzoj5210最大连通子块和（动态dp+卡常好题）