題解

在冬令營上聽到冬眠的東西，現在都是板子了貓錕真的是好毒瘤啊(霧)

(立個flag，我去thusc之前要把WC2018T1亂搞過去= =）

好的，我們可以參考貓錕的動態動態dp的課件，然后你發現你什么都看不懂（菜啊

但是我們仔細看一看，可以發現用數據結構維護矩陣，那么我們嘗試構造一個矩陣

\(\begin{bmatrix} \ g_{u,0} & g_{u,0}\\ g_{u,1} & 0 \end{bmatrix} \begin{bmatrix} f_{son[u],0}\\ f_{son[u],1} \end{bmatrix} = \begin{bmatrix} f_{u,0}\\ f_{u,1} \end{bmatrix}\)
其中\(g_{u,0}\)表示不選u，對于u的子樹，除了u的重兒子所在子樹，u的輕兒子最大獨立集是多少
\(g_{u,1}\)表示選了u
\(f_{u,0}\)表示不選u，以u為根的子樹最大獨立集是多少
\(f_{u,1}\)表示選了u，以u為根的子樹最大獨立集是多少

這個矩陣的運算不是加法和乘法，而是加法和取max
也就是\(c_{i,j} = max(a_{i,k} + b_{k,j})\)
也是滿足結合律的

這樣我們就可以用一個樹鏈剖分來維護這些矩陣了

注意一下，合并矩陣的時候是左右合并，但是乘法的時候一定先從右邊乘
舉個例子，我們的運算實際是這樣的
一條鏈:
3 - 4 - 5
3是4的父親，4是5的父親
\(\begin{bmatrix} \ g_{3,0} & g_{3,0}\\ g_{3,1} & 0 \end{bmatrix} \begin{bmatrix} \ g_{4,0} & g_{4,0}\\ g_{4,1} & 0 \end{bmatrix} \begin{bmatrix} f_{5,0}\\ f_{5,1} \end{bmatrix} = \begin{bmatrix} f_{3,0}\\ f_{3,1} \end{bmatrix}\)
也就是5先和4的矩陣結合，再和3的矩陣結合

實際上寫代碼的時候，既然每一條鏈的最后一定是一個葉子節點，我們就可以直接把f0設成0，f1設成0去做矩陣乘法，乘上這條鏈上所有的矩陣作為鏈頂的f值

代碼

#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <cmath> #include <cstring> #include <map> //#define ivorysi #define pb push_back #define space putchar(' ') #define enter putchar('\n') #define mp make_pair #define pb push_back #define fi first #define se second #define mo 974711 #define RG register #define MAXN 100005 #define debug using namespace std; typedef long long int64; typedef double db; template<class T> void read(T &res) {res = 0;char c = getchar();T f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {res = res * 10 + c - '0';c = getchar();}res *= f; } template<class T> void out(T x) {if(x < 0) putchar('-'),x = -x;if(x >= 10) out(x / 10);putchar('0' + x % 10); } const int MOD = 1000000007; int mul(int a,int b) {return 1LL * a * b % MOD; } int inc(int a,int b) {a = a + b;if(a >= MOD) a -= MOD;return a; }int fpow(int x,int c) {int res = 1,t = x % MOD;while(c) {if(c & 1) res = mul(res,t);t = mul(t,t);c >>= 1;}return res; } int N,Q; int64 val[MAXN],g[MAXN][2],f[MAXN][2]; int top[MAXN],btm[MAXN],dfn[MAXN],fa[MAXN],dep[MAXN],son[MAXN],idx,siz[MAXN],L[MAXN],pos[MAXN]; int cnt = 0; struct node {int to,next; }E[MAXN * 2]; int head[MAXN],sumE; struct tr_node {int l,r;int64 M[2][2]; }tr[MAXN * 4]; void add(int u,int v) {E[++sumE].to = v;E[sumE].next = head[u];head[u] = sumE; } void dfs1(int u) {dep[u] = dep[fa[u]] + 1;siz[u] = 1;for(int i = head[u] ; i ; i = E[i].next) {int v = E[i].to;if(v != fa[u]) {fa[v] = u;dfs1(v);siz[u] += siz[v];if(siz[v] > siz[son[u]]) son[u] = v;}} } void dfs2(int u) {dfn[u] = ++idx;L[idx] = u;if(!top[u]) {top[u] = u;}if(son[u]) {top[son[u]] = top[u];dfs2(son[u]);btm[u] = btm[son[u]]; }g[u][1] = val[u];g[u][0] = 0;for(int i = head[u] ; i ; i = E[i].next) {int v = E[i].to;if(v != son[u] && v != fa[u]) {dfs2(v);g[u][0] += max(f[v][0],f[v][1]);g[u][1] += max(0LL,f[v][0]);}}f[u][1] = g[u][1] + max(f[son[u]][0],0LL);f[u][0] = g[u][0] + max(f[son[u]][1],f[son[u]][0]);if(!son[u]) btm[u] = u; } void update(int u) {int L = u << 1,R = u << 1 | 1;tr[u].M[0][0] = max(tr[L].M[0][0] + tr[R].M[0][0],tr[L].M[0][1] + tr[R].M[1][0]);tr[u].M[0][1] = max(tr[L].M[0][0] + tr[R].M[0][1],tr[L].M[0][1] + tr[R].M[1][1]);tr[u].M[1][0] = max(tr[L].M[1][0] + tr[R].M[0][0],tr[L].M[1][1] + tr[R].M[1][0]);tr[u].M[1][1] = max(tr[L].M[1][0] + tr[R].M[0][1],tr[L].M[1][1] + tr[R].M[1][1]); } void build(int u,int l,int r) {tr[u].l = l;tr[u].r = r;if(l == r) {int v = L[l];tr[u].M[0][0] = g[v][0];tr[u].M[0][1] = g[v][0];tr[u].M[1][0] = g[v][1];tr[u].M[1][1] = 0;pos[v] = u;return ;}int mid = (l + r) >> 1;build(u << 1,l,mid);build(u << 1 | 1,mid + 1,r);update(u); } void Query(int u,int L,int R,int64 &f0,int64 &f1) {if(tr[u].l == L && tr[u].r == R) {int64 x = max(f0 + tr[u].M[0][0],f1 + tr[u].M[0][1]);int64 y = max(f0 + tr[u].M[1][0],f1 + tr[u].M[1][1]);f0 = x;f1 = y;return;}int mid = (tr[u].l + tr[u].r) >> 1;if(R <= mid) Query(u << 1,L,R,f0,f1);else if(L > mid) Query(u << 1 | 1,L,R,f0,f1);else {Query(u << 1 | 1,mid + 1,R,f0,f1);Query(u << 1,L,mid,f0,f1);} } void Change(int x) {int t = pos[x] >> 1;while(t) {update(t);t >>= 1;} } void Change_tr(int x) {while(1) {int a = top[x];if(fa[a] != 0) {g[fa[a]][0] -= max(f[a][0],f[a][1]);g[fa[a]][1] -= max(f[a][0],0LL);}f[a][0] = 0;f[a][1] = 0;Query(1,dfn[top[x]],dfn[btm[x]],f[a][0],f[a][1]);if(fa[a] == 0) break;g[fa[a]][0] += max(f[a][0],f[a][1]);g[fa[a]][1] += max(f[a][0],0LL);x = fa[a];tr[pos[x]].M[0][0] = tr[pos[x]].M[0][1] = g[x][0];tr[pos[x]].M[1][0] = g[x][1];tr[pos[x]].M[1][1] = 0;Change(x);} } void Init() {read(N);read(Q);for(int i = 1 ; i <= N ; ++i) read(val[i]);int u,v;for(int i = 1 ; i < N ; ++i) {read(u);read(v);add(u,v);add(v,u);}dfs1(1);dfs2(1);build(1,1,N); } void Solve() {int x;int64 y;while(Q--) {++cnt;read(x);read(y);g[x][1] = g[x][1] - val[x] + y;tr[pos[x]].M[1][0] = g[x][1];val[x] = y;Change(x);Change_tr(x);out(max(f[1][0],f[1][1]));enter;} } int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endifInit();Solve();return 0; }

轉載于:https://www.cnblogs.com/ivorysi/p/9118007.html

總結

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

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