之前的后綴平衡樹其實沒完，只是過于鬼畜就棄了

傳送門

題意：帶修改點權的最大獨立集

$N\le 1e5$

一個沒啥用的模板，不過適合練習LCT

先寫出方程

$$f(u,0)=\sum _{v\in son(u)}max\{f(v,0),f(v,1)\}$$

$$f(u,1)=val(u)+\sum _{v\in son(u)}f(v,0)$$

首先一個顯然的想法，每次修改暴力跳父親，顯然會T而且實測這玩意極易寫掛

但是我們發現直接跳父親到根的這段信息就浪費了

然而這段信息極其玄學，并不能寫出來，遇到這種考慮矩陣乘法

因為這是棵樹，結構是很難確定的，寫不出轉移矩陣。

所以考慮剖一下

這里采用LCT維護子樹

對于每個節點$u$,維護子樹$g(u,0/1)$

$$g(u,0)=\sum _{v\in virson(u)}max\{f(v,0),f(v,1)\}$$

$$g(u,1)=val(u)+\sum _{v\in virson(u)}f(v,0)$$

($virson$表示虛兒子)

可以理解為只考慮虛節點的$f$

由于這個只有求和，所以可以在切換的時候順便改一下,然后就可以當常數用

這樣可以把狀態轉移方程寫到鏈上

設$v$是$u$的重兒子

$$f(u,0)=max\{f(v,0),f(v,1)\}+g(u,0)$$

$$f(u,1)=f(v,0)+g(u,1)$$

上面那個改一下

$$f(u,0)=max\{f(v,0)+g(u,0),f(v,1)+g(u,0)\}$$

$$f(u,1)=f(v,0)+g(u,1)$$

上矩陣了

當然要擴展下定義，$A?B=C$定義為

$$C_{i,j}=\underset{k}{\max }\{A_{i,k}+B_{k,j}\}$$

然后

$$\left[\begin{array}{c}f(u,0),f(u,1)\end{array}\right]=\left[\begin{array}{c}f(v,0),f(v,1)\end{array}\right]\left[\begin{array}{c}g(u,0),g(u,1)\\ g(u,0),?\infty \end{array}\right]$$

單位矩陣

$$\left[\begin{array}{c}0,?\infty \\ ?\infty ,0\end{array}\right]$$

注意因為一些奇怪的原因，上面那個拆開是倒著的，所以update要倒著寫

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #define MAXN 100005 #define MAXM 200005 using namespace std; const int INF=0x3f3f3f3f; struct edge{int u,v;}e[MAXM]; int head[MAXN],nxt[MAXM],cnt; void addnode(int u,int v) {e[++cnt]=(edge){u,v};nxt[cnt]=head[u];head[u]=cnt; } struct mat {int e[2][2];mat(){for (int i=0;i<2;i++)for (int j=0;j<2;j++)e[i][j]=-INF;}inline int max(){return std::max(e[0][0],e[0][1]);}inline int* operator [](int i){return e[i];} }; inline mat operator *(mat a,mat b) {mat ans;ans[0][0]=ans[0][1]=ans[1][0]=ans[1][1]=0;for (int i=0;i<2;i++)for (int j=0;j<2;j++)for (int k=0;k<2;k++)ans[i][j]=max(ans[i][j],a[i][k]+b[k][j]);return ans; } int val[MAXN]; mat dp[MAXN],trans[MAXN]; int ch[MAXN][2],fa[MAXN]; inline void update(int x){dp[x]=dp[ch[x][1]]*trans[x]*dp[ch[x][0]];} inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;} inline int get(int x){return ch[fa[x]][1]==x;} void rotate(int x) {int y=fa[x],z=fa[y];int l=get(x),r=l^1;int w=ch[x][r];if (!isroot(y)) ch[z][get(y)]=x;ch[x][r]=y;ch[y][l]=w;if (w) fa[w]=y;fa[y]=x;fa[x]=z;update(y);update(x); } void splay(int x) {while (!isroot(x)){int y=fa[x];if (!isroot(y)){if (get(x)==get(y)) rotate(y);else rotate(x);}rotate(x);} } inline void access(int x) {for (int y=0;x;y=x,x=fa[x]){splay(x);trans[x][0][0]=(trans[x][1][0]+=dp[ch[x][1]].max());trans[x][0][1]+=dp[ch[x][1]][0][0];trans[x][0][0]=(trans[x][1][0]-=dp[y].max());trans[x][0][1]-=dp[y][0][0]; ch[x][1]=y;update(x);} } void dfs(int u,int f) {fa[u]=f;int g[2]={0,val[u]};for (int i=head[u];i;i=nxt[i])if (e[i].v!=f){dfs(e[i].v,u);g[0]+=dp[e[i].v].max();g[1]+=dp[e[i].v][0][0];} trans[u][0][0]=trans[u][1][0]=g[0];trans[u][0][1]=g[1];dp[u]=trans[u]; } int main() {dp[0][0][0]=dp[0][1][1]=0;int n,m;scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&val[i]);for (int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);addnode(u,v);addnode(v,u);}dfs(1,0);cerr<<dp[1].max()<<'\n';while (m--){int x,v;scanf("%d%d",&x,&v);access(x);splay(x);trans[x][0][1]-=val[x];trans[x][0][1]+=(val[x]=v);update(x);splay(1);printf("%d\n",dp[1].max());}return 0; }

總結

以上是生活随笔為你收集整理的【洛谷P4719】动态DP【LCT】【矩阵】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。