bzoj 4712 洪水——動态DP

題目：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了。

#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+5,INF=1e9+5;
int n,m,hd[N],xnt,to[N<<1],nxt[N<<1],w[N];
int tot,dfn[N],rnk[N],top[N],son[N],siz[N],fa[N],bj[N],Ls[N<<1],Rs[N<<1];
ll dp[N];
ll Mn(ll a,ll b){return a<b?a:b;}
struct Matrix{
  ll a[2][2];
  Matrix(){a[0][0]=a[0][1]=a[1][0]=a[1][1]=INF;}
  Matrix operator+ (const Matrix &b)const
  {
    Matrix c;
    for(int i=0;i<=1;i++)
      for(int k=0;k<=1;k++)
    for(int j=0;j<=1;j++)
      c.a[i][j]=Mn(c.a[i][j],a[i][k]+b.a[k][j]);
    return c;
  }
}g[N],t[N<<1];
int rdn()
{
  int ret=0;bool fx=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}
  while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',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]=1;
  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:0;
      }
}
void dfsx(int cr)
{
  dfn[cr]=++tot; rnk[tot]=cr;
  dp[cr]=w[cr]; ll tmp=0;
  if(son[cr])top[son[cr]]=top[cr],dfsx(son[cr]);
  g[cr].a[0][0]=INF; g[cr].a[0][1]=w[cr];
  g[cr].a[1][0]=g[cr].a[1][1]=0;
  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[0][0]=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>>1;
  ls=++tot; build(l,mid,ls);
  rs=++tot; build(mid+1,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>>1;
  if(p<=mid)updt(l,mid,ls,p);
  else updt(mid+1,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>>1;
  if(R<=mid)return query(l,mid,ls,L,R);
  if(mid<L)return query(mid+1,r,rs,L,R);
  return query(l,mid,ls,L,R)+query(mid+1,r,rs,L,R);
}
Matrix calc(int cr){ return query(1,n,1,dfn[cr],bj[cr]);}
void cz(int x,int y)
{
  g[x].a[0][1]+=y;
  Matrix k1=calc(top[x]); updt(1,n,1,dfn[x]); Matrix k2=calc(top[x]);
  while(fa[top[x]])
    {
      g[fa[top[x]]].a[0][0]+=Mn(k2.a[0][0],k2.a[0][1])-Mn(k1.a[0][0],k1.a[0][1]);
      x=fa[top[x]];
      k1=calc(top[x]); updt(1,n,1,dfn[x]); k2=calc(top[x]);
    }
}
int main()
{
  n=rdn();for(int i=1;i<=n;i++)w[i]=rdn();
  for(int i=1,u,v;i<n;i++)
    {
      u=rdn(); v=rdn(); add(u,v); add(v,u);
    }
  dfs(1); top[1]=1; dfsx(1); tot=1; build(1,n,1);
  m=rdn();  char ch[5];
  for(int i=1,x,y;i<=m;i++)
    {
      scanf("%s",ch);
      if(ch[0]=='C')
    {
      x=rdn(); y=rdn(); cz(x,y);
    }
      else
    {
      x=rdn(); Matrix d=query(1,n,1,dfn[x],bj[top[x]]);
      printf("%lld\n",Mn(d.a[0][0],d.a[0][1]));
    }
    }
  return 0;
}