【bzoj4712】洪水

Portal --> bzoj4712

Description

　　?給你一棵樹，節點從\(1\)到\(n\)編號，每個節點有一個權值，有若干次操作，操作有以下兩種：

\((C,x,delta)\)：將編號為\(x\)的點的權值改為\(delta\)

\((Q,x)\)：詢問將\(x\)號節點為根的子樹中的所有葉子結點與子樹外的其他所有葉子節點分離的最小代價，分離可以通過刪除節點實現，刪除一個節點的對應代價為該點的權值

　　?數據范圍：\(n<=200000\)，任意\(delta\)均為非負數，答案在long long范圍內

Solution

　　?這題貌似是。。經典的動態dp問題，維護重鏈信息\(f\)和輕兒子信息之和\(g\)之后可以用樹剖解決

?　　?我們先考慮沒有修改操作的情況，那就是直接dp

?　　?記\(f[x]\)表示以\(x\)為根的子樹的答案，\(val[x]\)表示\(x\)點的權值，那么有：
\[ f[x]=min(val[x],\sum\limits_{x\rightarrow u}f[u]) \]
? 如果要修改的話我們考慮樹剖，再定義一個數組\(g\)，\(g[x]\)表示\(x\)的輕兒子的\(f\)值之和，那么就有：
\[ f[x]=min(val[x],f[son[x]]+g[x]) \]
?　　?其中\(son[x]\)表示的是\(x\)的重兒子

?　　?這個時候就有好幾種不同的做法了，反正就是維護這兩個值就好了，接下來講的是一種通過維護一個類似轉移矩陣一樣的東西來用樹剖維護的方法

?　　?我們考慮定義一種新的矩陣乘法（額好像也不能叫做矩陣乘法反正就是一種新的運算）：
\[ C[i][j]=min(A[i][k]+B[k][j]) \]
　　?其中\(A,B,C\)都是矩陣，其實這種運算就是將原來的矩陣乘法的乘法改成了取最小值

　　?這個運算是滿足結合律的，具體證明的話就是我們可以將一次這樣的運算理解成求最短路，然后連續兩次這樣的運算的話就是相當于你有三排點，要求最左邊到最右邊的最短路，顯然你可以先求出左邊兩排的最短路，或者先求出右邊兩排的最短路，最后得到的結果是一樣的

　　?定義完這樣的運算有什么用呢？我們可以考慮將\(f[x]\)的求值過程用這種運算來實現，為了方便表示我們將這種運算的符號約定為\(*\)：
\[ \begin{bmatrix}f[x]\\0\end{bmatrix}=\begin{bmatrix}g[x]&val[x]\\0&0\end{bmatrix}*\begin{bmatrix}f[son[x]]\\0\end{bmatrix} \]
　　?具體的話就是。。大力展開一下就好了

?　　?然后我們可以發現\(\begin{bmatrix}f[son[x]]\\0\end{bmatrix}\)是可以寫成\(\begin{bmatrix}g[son[son[x]]]&val[son[son[x]]]\\0&0\end{bmatrix}\)的，一路寫下去就會發現其實就是\(x\)所在的整條重鏈中，從\(x\)這個位置的矩陣一路連續運算一直到重鏈底就好了

?　　?注意到這個剖完之后就是一段連續的區間，然后這樣我們就可以放心用線段樹來維護區間的矩陣的連續運算得到的結果，然后其他的就是跟樹剖差不多的操作了

? 　　?

?　　?其實還是有(hen)點(da)區別的，具體一點就是

1、查詢

　　?與普通樹剖不同的是這樣我們維護的是。。某個位置到鏈底的權值運算和，所以。。我們需要記錄的是每個點所在的鏈底在哪里，然后查詢的時候并不需要往上跳直接查就好了

2、修改

　　?修改的話因為這里會影響到祖先的\(g\)值，所以我們還是要常規操作一路跳上去，不過不同的是，這里修改直接暴力通過線段樹區間查詢求得\(f[top[x]\)然后在\(g[pre[top[x]]]\)里面減去（\(pre[x]\)表示\(x\)在原樹上的直接祖先，\(top[x]\)表示\(x\)所在的重鏈頭），然后更新線段樹中的信息，然后再將新的值加回\(g[pre[top[x]]]\)中

　　?

?　　?然后就十分愉悅\(O(nlog^2n)\)做完啦，這個做法有一個好處就是。。就算沒有保證修改的\(delta\)非負也可以直接做，以及重載運算符之后線段樹寫起來很爽qwq

?　　?以及洛谷上面貌似有碾爆LCT和樹剖的一個\(log\)做法qwq（orzlyy！！）然而。。我太懶了并沒有寫qwq

　　?

?　　?代碼大概長這個樣子

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=200010,SEG=N*4;
const ll inf=1LL<<60;
struct xxx{int y,nxt;
}a[N*2];
int h[N],lis[N],dfn[N],ed[N],pre[N],sz[N];//ed=the end of the chain
ll f[N],g[N],val[N];
int son[N],top[N];
int n,m,tot,dfn_t;
ll ans;
struct Mtrix{/*{{{*/ll a[2][2];int n;void init(int _n){n=_n;for (int i=0;i<n;++i)for (int j=0;j<n;++j) a[i][j]=inf;}friend Mtrix operator * (Mtrix x,Mtrix y){Mtrix ret; ret.n=x.n;for (int i=0;i<ret.n;++i)for (int j=0;j<ret.n;++j){ret.a[i][j]=inf;for (int k=0;k<ret.n;++k)if (x.a[i][k]!=inf&&y.a[k][j]!=inf)ret.a[i][j]=min(ret.a[i][j],x.a[i][k]+y.a[k][j]);}return ret;}
};/*}}}*/
namespace Seg{/*{{{*/int ch[SEG][2];Mtrix info[SEG];int n,tot;void pushup(int x){info[x]=info[ch[x][0]]*info[ch[x][1]];}void _build(int x,int l,int r){info[x].init(2);if (l==r){info[x].a[0][0]=g[lis[l]];info[x].a[0][1]=val[lis[l]];info[x].a[1][0]=info[x].a[1][1]=0;return;}int mid=l+r>>1;ch[x][0]=++tot; _build(ch[x][0],l,mid);ch[x][1]=++tot; _build(ch[x][1],mid+1,r);pushup(x);}void build(int _n){n=_n;tot=1;_build(1,1,n);}void _update(int x,int d,int lx,int rx){if (lx==rx){info[x].a[0][0]=g[lis[lx]];info[x].a[0][1]=val[lis[lx]];info[x].a[1][0]=info[x].a[1][1]=0;return;}int mid=lx+rx>>1;if (d<=mid) _update(ch[x][0],d,lx,mid);else _update(ch[x][1],d,mid+1,rx);pushup(x);}void update(int d){_update(1,d,1,n);}Mtrix _query(int x,int l,int r,int lx,int rx){if (l<=lx&&rx<=r) return info[x];int mid=lx+rx>>1;if (r<=mid) return _query(ch[x][0],l,r,lx,mid);else if (l>mid) return _query(ch[x][1],l,r,mid+1,rx);else{return _query(ch[x][0],l,mid,lx,mid)*_query(ch[x][1],mid+1,r,mid+1,rx);}}Mtrix query(int l,int r){return _query(1,l,r,1,n);}
}/*}}}*/
void add(int x,int y){a[++tot].y=y; a[tot].nxt=h[x]; h[x]=tot;}
void dfs(int fa,int x){int u;sz[x]=1; son[x]=0; pre[x]=fa;for (int i=h[x];i!=-1;i=a[i].nxt){u=a[i].y;if (u==fa) continue;dfs(x,u);sz[x]+=sz[u];if (sz[u]>sz[son[x]]) son[x]=u;}
}
void dfs1(int fa,int x){int u,cntson=0;dfn[x]=ed[x]=++dfn_t; lis[dfn_t]=x;if (son[x]){top[son[x]]=top[x];dfs1(x,son[x]);ed[x]=ed[son[x]];f[x]+=f[son[x]];++cntson;}for (int i=h[x];i!=-1;i=a[i].nxt){u=a[i].y;if (u==fa||u==son[x]) continue;top[u]=u;dfs1(x,u);g[x]+=f[u];++cntson;}if (cntson==0) g[x]=inf,f[x]=val[x];elsef[x]=min(val[x],f[x]+g[x]);
}
ll query(int x){Mtrix tmp=Seg::query(dfn[x],ed[x]);return min(tmp.a[0][0],tmp.a[0][1]);
}
void update(int x,int delta){ll tmp;val[x]+=delta;while (top[x]){tmp=query(top[x]);if (pre[top[x]])g[pre[top[x]]]-=tmp;Seg::update(dfn[x]);tmp=query(top[x]);if (pre[top[x]])g[pre[top[x]]]+=tmp;x=pre[top[x]];}
}int main(){
#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);
#endifchar op[5];int x,y;scanf("%d",&n);for (int i=1;i<=n;++i) scanf("%lld",val+i);memset(h,-1,sizeof(h));tot=0;for (int i=1;i<n;++i){scanf("%d%d",&x,&y);add(x,y); add(y,x);}dfs(0,1);top[1]=1; dfn_t=0;dfs1(0,1);Seg::build(dfn_t);scanf("%d",&m);for (int i=1;i<=m;++i){scanf("%s",&op);if (op[0]=='C'){scanf("%d%d",&x,&y);update(x,y);}else{scanf("%d",&x);ans=query(x);printf("%lld\n",ans);}}
}