bzoj 4712 洪水—

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4712

因为作为动态DP练习而找到，所以就用动态DP做了，也没管那种二分的方法。

感觉理解似乎加深了。

果然初始权值也都是非负的。

所以 dp[cr] 表示当前子树与自己的叶子都断开了的最小代价，则 dp[cr]=min{ sigma dp[v] , w[cr] }(v是cr的直接孩子)。

但这样的话，修改的时候需要把自己到根的路径都走一遍。不过查询是O(1)的，所以考虑分配一下。

走到根的过程如果是 log 的话就好了。那么不是倍增就是树剖。

考虑用树剖，s[cr] 表示 sigma dp[v] ( v是cr的轻儿子）。这样修改的话只要每次遇到别的重链就改一下它的 s 就行了。

考虑查询，可以从矩阵的角度看：

　　状态矩阵是2行1列，放 dp[cr] 和 0 ；转移矩阵是2行2列，[0][0]=s[cr]，[0][1]=w[cr]，[1][0]=0，[1][1]=0。转移的时候是[ i ][ j ]=min( [ i ][ j ] , [ i ][ k ]+[ k ][ j ] )。

于是树剖的线段树维护的就是转移矩阵的乘积，查询一个点到其所在重链底端的一段乘积即可。原本要乘一个状态，但那个是 [0][0]=0，[0][1]=0，所以把2行2列的 [0][0] 和 [0][1] 取个min作为dp[ ]。

然后就能以很慢的速度A了。

或者像这个人这样，好像能快个2504ms。https://www.cnblogs.com/GXZlegend/p/8710445.html

自己生硬地弄2×2矩阵果然不够好吗……这也启示我们，只要是线段树能维护的东西就行，不一定非是矩阵。关键是把轻儿子的信息带在身上，现求重儿子的信息。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

#define ls Ls[cr]

#define rs Rs[cr]

using namespace std;

const int N=2e5+,INF=1e9+;

int n,m,hd[N],xnt,to[N<<],nxt[N<<],w[N];

int tot,dfn[N],rnk[N],top[N],son[N],siz[N],fa[N],bj[N],Ls[N<<],Rs[N<<];

ll dp[N];

ll Mn(ll a,ll b){return a<b?a:b;}

struct Matrix{

  ll a[][];

  Matrix(){a[][]=a[][]=a[][]=a[][]=INF;}

  Matrix operator+ (const Matrix &b)const

  {

    Matrix c;

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

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

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

      c.a[i][j]=Mn(c.a[i][j],a[i][k]+b.a[k][j]);

    return c;

  }

}g[N],t[N<<];

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return fx?ret:-ret;

}

void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}

void dfs(int cr)

{

  siz[cr]=;

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa[cr])

      {

    fa[v]=cr; dfs(v); siz[cr]+=siz[v];

    siz[v]>siz[son[cr]]?son[cr]=v:;

      }

}

void dfsx(int cr)

{

  dfn[cr]=++tot; rnk[tot]=cr;

  dp[cr]=w[cr]; ll tmp=;

  if(son[cr])top[son[cr]]=top[cr],dfsx(son[cr]);

  g[cr].a[][]=INF; g[cr].a[][]=w[cr];

  g[cr].a[][]=g[cr].a[][]=;

  if(!son[cr]){bj[top[cr]]=dfn[cr];return;}

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa[cr]&&v!=son[cr])

      {

    top[v]=v;dfsx(v);

    tmp+=dp[v];

      }

  g[cr].a[][]=tmp; dp[cr]=Mn(w[cr],tmp+dp[son[cr]]);

}

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

{

  if(l==r){t[cr]=g[rnk[l]];return;}

  int mid=l+r>>;

  ls=++tot; build(l,mid,ls);

  rs=++tot; build(mid+,r,rs);

  t[cr]=t[ls]+t[rs];

}

void updt(int l,int r,int cr,int p)

{

  if(l==r){t[cr]=g[rnk[l]];return;}

  int mid=l+r>>;

  if(p<=mid)updt(l,mid,ls,p);

  else updt(mid+,r,rs,p);

  t[cr]=t[ls]+t[rs];

}

Matrix query(int l,int r,int cr,int L,int R)

{

  if(l>=L&&r<=R)return t[cr];

  int mid=l+r>>;

  if(R<=mid)return query(l,mid,ls,L,R);

  if(mid<L)return query(mid+,r,rs,L,R);

  return query(l,mid,ls,L,R)+query(mid+,r,rs,L,R);

}

Matrix calc(int cr){ return query(,n,,dfn[cr],bj[cr]);}

void cz(int x,int y)

{

  g[x].a[][]+=y;

  Matrix k1=calc(top[x]); updt(,n,,dfn[x]); Matrix k2=calc(top[x]);

  while(fa[top[x]])

    {

      g[fa[top[x]]].a[][]+=Mn(k2.a[][],k2.a[][])-Mn(k1.a[][],k1.a[][]);

      x=fa[top[x]];

      k1=calc(top[x]); updt(,n,,dfn[x]); k2=calc(top[x]);

    }

}

int main()

{

  n=rdn();for(int i=;i<=n;i++)w[i]=rdn();

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

    {

      u=rdn(); v=rdn(); add(u,v); add(v,u);

    }

  dfs(); top[]=; dfsx(); tot=; build(,n,);

  m=rdn();  char ch[];

  for(int i=,x,y;i<=m;i++)

    {

      scanf("%s",ch);

      if(ch[]=='C')

    {

      x=rdn(); y=rdn(); cz(x,y);

    }

      else

    {

      x=rdn(); Matrix d=query(,n,,dfn[x],bj[top[x]]);

      printf("%lld\n",Mn(d.a[][],d.a[][]));

    }

    }

  return ;

}

巴特西

bzoj 4712 洪水——动态DP

最新文章

热门文章