洛谷P4719 【模板】动态dp
? 解题记录 ? ? 模板 ? ? 动态规划 ? ? 树链剖分 ?    2018-12-10 11:15:59    669    0    0

题目描述

给定一棵n个点的树,点带点权。

m次操作,每次操作给定x,y,表示修改点x的权值为y

你需要在每次操作之后求出这棵树的最大权独立集的权值大小。

输入输出格式

输入格式:

 

第一行,n,m,分别代表点数和操作数。

第二行,V1,V2,...,Vn,代表nn个点的权值。

接下来n1行,x,y,描述这棵树的n1条边。

接下来m行,x,y,修改点x的权值为y

 

输出格式:

 

对于每个操作输出一行一个整数,代表这次操作后的树上最大权独立集。

保证答案在int范围内

 

输入输出样例

输入样例#1: 复制
  1. 10 10
  2. -11 80 -99 -76 56 38 92 -51 -34 47
  3. 2 1
  4. 3 1
  5. 4 3
  6. 5 2
  7. 6 2
  8. 7 1
  9. 8 2
  10. 9 4
  11. 10 7
  12. 9 -44
  13. 2 -17
  14. 2 98
  15. 7 -58
  16. 8 48
  17. 3 99
  18. 8 -61
  19. 9 76
  20. 9 14
  21. 10 93
输出样例#1: 复制
  1. 186
  2. 186
  3. 190
  4. 145
  5. 189
  6. 288
  7. 244
  8. 320
  9. 258
  10. 304

说明

对于30%的数据,1n,m10

对于60%的数据,1n,m1000

对于100%的数据,1n,m100000


考场上其实想过树链剖分维护矩阵乘积,觉得联赛不会考的这么毒没有继续往下想了。

想不到出题人是个毒瘤……唉……

于是就是这样了,树链剖分把轻链看成常数写进转移,在重链上dp维护矩阵乘积。

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #define For(i, a, b) for(register int i = a; i <= b; ++i)
  5. using namespace std;
  6. const int maxn = 1e5 + 5;
  7. const int inf = 0x3f3f3f3f;
  8. struct edge {
  9. int v, next;
  10. } e[maxn << 1];
  11. int head[maxn], cnt, n, m, u, v, w[maxn], MXR[maxn];
  12. void adde(const int &u, const int &v) {
  13. e[++cnt] = (edge) {v, head[u]};
  14. head[u] = cnt;
  15. }
  16. struct MAT {int d[2][2];};
  17. MAT tmp;
  18. MAT operator * (const MAT & A, const MAT & B) {
  19. tmp = (MAT){-inf, -inf, -inf, -inf};
  20. For(i, 0, 1) For(j, 0, 1) For(k, 0, 1)
  21. tmp.d[i][j] = max(A.d[k][j] + B.d[i][k], tmp.d[i][j]);
  22. return tmp;
  23. }
  24.  
  25. int siz[maxn], fa[maxn], top[maxn], son[maxn], d[maxn];
  26. int dfn[maxn], org[maxn], dcnt, dp[maxn][2], ldp[maxn][2];
  27. void dfs1(int u, int p) {
  28. siz[u] = 1;
  29. fa[u] = p, d[u] = d[p] + 1;
  30. for(register int i = head[u]; i; i = e[i].next) {
  31. int v = e[i].v;
  32. if(v == p) continue;
  33. dfs1(v, u), siz[u] += siz[v];
  34. if(!son[u] || siz[son[u]] < siz[v])
  35. son[u] = v;
  36. }
  37. }
  38.  
  39. void work(int u) {
  40. ldp[u][1] = dp[u][1] = w[u];
  41. for(register int i = head[u]; i; i = e[i].next) {
  42. int v = e[i].v;
  43. if(v == fa[u]) continue;
  44. dp[u][0] += max(dp[v][0], dp[v][1]);
  45. dp[u][1] += dp[v][0];
  46. }
  47. for(register int i = head[u]; i; i = e[i].next) {
  48. int v = e[i].v;
  49. if(v == fa[u] || v == son[u]) continue;
  50. ldp[u][0] += max(dp[v][0], dp[v][1]);
  51. ldp[u][1] += dp[v][0];
  52. }
  53. }
  54.  
  55. int dfs2(int u, int tp) {
  56. dfn[u] = ++dcnt;
  57. org[dfn[u]] = u;
  58. top[u] = tp, MXR[u] = u;
  59. if(son[u]) MXR[u] = dfs2(son[u], tp);
  60. for(register int i = head[u]; i; i = e[i].next) {
  61. int v = e[i].v;
  62. if(v == son[u] || v == fa[u]) continue;
  63. dfs2(v, v);
  64. }
  65. work(u);
  66. return MXR[u];
  67. }
  68.  
  69. namespace SGT {
  70. MAT t[maxn << 2];
  71. void push_up(int rt) {
  72. t[rt] = t[rt << 1 | 1] * t[rt << 1];
  73. }
  74. void build(int l, int r, int rt) {
  75. if(l == r) {
  76. t[rt] = (MAT) {ldp[org[l]][0], ldp[org[l]][0],
  77. ldp[org[l]][1], -inf};
  78. rt;
  79. return ;
  80. }
  81. int mid = l + r >> 1;
  82. build(l, mid, rt << 1);
  83. build(mid + 1, r, rt << 1 | 1);
  84. push_up(rt);
  85. }
  86. void edit(int x, int tl, int tr, const MAT &nw, int rt) {
  87. if(tl == tr) {
  88. t[rt] = nw;
  89. return ;
  90. }
  91. int mid = tl + tr >> 1;
  92. if(x <= mid) edit(x, tl, mid, nw, rt << 1);
  93. else edit(x, mid + 1, tr, nw, rt << 1 | 1);
  94. push_up(rt);
  95. }
  96. MAT query(int l, int r, int tl, int tr, int rt) {
  97. if(l == tl && r == tr) return t[rt];
  98. int mid = tl + tr >> 1;
  99. if(r <= mid) return query(l, r, tl, mid, rt << 1);
  100. else if(l > mid) return query(l, r, mid + 1, tr, rt << 1 | 1);
  101. else return query(mid + 1, r, mid + 1, tr, rt << 1 | 1) *
  102. query(l, mid, tl, mid, rt << 1);
  103. }
  104. }
  105.  
  106. int Q() {
  107. MAT ans = SGT::query(1, dfn[MXR[1]], 1, n, 1);
  108. return max(ans.d[0][0], ans.d[1][0]);
  109. }
  110.  
  111. void Ref(int x, int dp0, int dp1) {
  112. ldp[fa[x]][0] -= max(dp[x][0], dp[x][1]);
  113. ldp[fa[x]][1] -= dp[x][0];
  114. dp[x][0] = dp0, dp[x][1] = dp1;
  115. ldp[fa[x]][0] += max(dp[x][0], dp[x][1]);
  116. ldp[fa[x]][1] += dp[x][0];
  117. }
  118.  
  119. void E(int x, int W) {
  120. ldp[x][1] -= w[x];
  121. ldp[x][1] += (w[x] = W);
  122. while(x) {
  123. SGT::edit(dfn[x], 1, n, (MAT) {ldp[x][0], ldp[x][0],
  124. ldp[x][1], -inf}, 1);
  125. x = top[x];
  126. tmp = SGT::query(dfn[x], dfn[MXR[x]], 1, n, 1);
  127. Ref(x, tmp.d[0][0], tmp.d[1][0]);
  128. x = fa[x];
  129. }
  130. }
  131.  
  132. int main() {
  133. scanf("%d%d", &n, &m);
  134. for(register int i = 1; i <= n; ++i)
  135. scanf("%d", &w[i]);
  136. for(register int i = 1; i < n; ++i)
  137. scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
  138. dfs1(1, 0), dfs2(1, 1), SGT::build(1, n, 1);
  139. //printf("%d\n", Q());
  140. for(register int i = 1; i <= m; ++i) {
  141. scanf("%d%d", &u, &v);
  142. E(u, v);
  143. printf("%d\n", Q());
  144. }
  145. return 0;
  146. }

上一篇: LOJ #6433. 「PKUSC2018」最大前缀和

下一篇: LOJ#2340. 「WC2018」州区划分

669 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航