动态DP其实挺简单一个东西。
把DP值的定义改成去掉重儿子之后的DP值。
重链上的答案就用线段树/lct维护，维护子段/矩阵都可以。其实本质上差不多...
修改的时候在log个线段树上修改。轻儿子所在重链的线段树的根拿去更新父亲的DP值。
1 #include <cstdio>
2 #include <algorithm>
3
4 const int N = 100010, INF = 0x3f3f3f3f;
5
6 template <class T> inline void read(T &x) {
7 x = 0;
8 char c = getchar();
9 bool f = 0;
10 while(c < '0' || c > '9') {
11 if(c == '-') {
12 f = 1;
13 }
14 c = getchar();
15 }
16 while(c >= '0' && c <= '9') {
17 x = (x << 3) + (x << 1) + c - 48;
18 c = getchar();
19 }
20 if(f) {
21 x = (~x) + 1;
22 }
23 return;
24 }
25
26 struct Edge {
27 int nex, v;
28 }edge[N << 1]; int tp;
29
30 // 0 0 0
31 // 1 0 1
32 // 2 1 0
33 // 3 1 1
34
35 int top[N], e[N], siz[N], pos[N], id[N], val[N], fa[N], son[N], d[N], num, n, len[N];
36 int f[N][2], seg[N * 4][4], tot, ls[N * 4], rs[N * 4], rt[N];
37
38 inline void add(int x, int y) {
39 tp++;
40 edge[tp].v = y;
41 edge[tp].nex = e[x];
42 e[x] = tp;
43 return;
44 }
45
46 void DFS_1(int x, int f) { // son siz fa d
47 fa[x] = f;
48 d[x] = d[f] + 1;
49 siz[x] = 1;
50 for(int i = e[x]; i; i = edge[i].nex) {
51 int y = edge[i].v;
52 if(y == f) {
53 continue;
54 }
55 DFS_1(y, x);
56 siz[x] += siz[y];
57 if(siz[y] > siz[son[x]]) {
58 son[x] = y;
59 }
60 }
61 return;
62 }
63
64 void DFS_2(int x, int f) { // pos id top
65 top[x] = f;
66 pos[x] = ++num;
67 id[num] = x;
68 len[x] = 1;
69 if(son[x]) {
70 DFS_2(son[x], f);
71 len[x] = len[son[x]] + 1;
72 }
73 for(int i = e[x]; i; i = edge[i].nex) {
74 int y = edge[i].v;
75 if(y == son[x] || y == fa[x]) {
76 continue;
77 }
78 DFS_2(y, y);
79 }
80 return;
81 }
82
83 inline void pushup(int o) {
84 int l = ls[o], r = rs[o];
85 seg[o][0] = std::max(seg[l][0] + seg[r][0], seg[l][0] + seg[r][2]);
86 seg[o][0] = std::max(seg[o][0], seg[l][1] + seg[r][0]);
87
88 seg[o][1] = std::max(seg[l][0] + seg[r][1], seg[l][0] + seg[r][3]);
89 seg[o][1] = std::max(seg[o][1], seg[l][1] + seg[r][1]);
90
91 seg[o][2] = std::max(seg[l][2] + seg[r][0], seg[l][2] + seg[r][2]);
92 seg[o][2] = std::max(seg[o][2], seg[l][3] + seg[r][0]);
93
94 seg[o][3] = std::max(seg[l][2] + seg[r][1], seg[l][2] + seg[r][3]);
95 seg[o][3] = std::max(seg[o][3], seg[l][3] + seg[r][1]);
96 return;
97 }
98
99 inline void build(int l, int r, int &o) {
100 if(!o) {
101 o = ++tot;
102 }
103 if(l == r) {
104 seg[o][0] = f[id[r]][0];
105 seg[o][1] = -INF;
106 seg[o][2] = -INF;
107 seg[o][3] = val[id[r]] + f[id[r]][1];
108 return;
109 }
110 int mid = (l + r) >> 1;
111 build(l, mid, ls[o]);
112 build(mid + 1, r, rs[o]);
113 pushup(o);
114 return;
115 }
116
117 void change(int p, int l, int r, int o) {
118 //printf("change -- : %d %d %d \n", p, l, r);
119 if(l == r) {
120 seg[o][0] = f[id[r]][0];
121 seg[o][1] = -INF;
122 seg[o][2] = -INF;
123 seg[o][3] = val[id[r]] + f[id[r]][1];
124 //printf("%d = %d + %d \n", id[r], val[id[r]], f[id[r]][1]);
125 return;
126 }
127 int mid = (l + r) >> 1;
128 if(p <= mid) {
129 change(p, l, mid, ls[o]);
130 }
131 else {
132 change(p, mid + 1, r, rs[o]);
133 }
134 pushup(o);
135 //printf("%d %d \n", id[l], id[r]);
136 //printf("%d %d %d %d \n", seg[o][0], seg[o][1], seg[o][2], seg[o][3]);
137 return;
138 }
139
140 inline void change(int x, int v) {
141 //printf("change %d %d \n", x, v);
142 val[x] = v;
143 while(x) {
144 int xx = top[x];
145 if(fa[xx]) {
146 int temp = std::max(seg[rt[xx]][0], seg[rt[xx]][1]);
147 f[fa[xx]][1] -= temp;
148 f[fa[xx]][0] -= std::max(std::max(seg[rt[xx]][2], seg[rt[xx]][3]), temp);
149 }
150 //printf("ch %d %d %d \n", x, xx, id[pos[xx] + len[xx] - 1]);
151 change(pos[x], pos[xx], pos[xx] + len[xx] - 1, rt[xx]);
152 if(fa[xx]) {
153 int temp = std::max(seg[rt[xx]][0], seg[rt[xx]][1]);
154 f[fa[xx]][1] += temp;
155 f[fa[xx]][0] += std::max(std::max(seg[rt[xx]][2], seg[rt[xx]][3]), temp);
156 }
157 x = fa[xx];
158 }
159 return;
160 }
161
162 int main() {
163 int m;
164 read(n); read(m);
165 for(int i = 1; i <= n; i++) {
166 read(val[i]);
167 }
168 for(int i = 1, x, y; i < n; i++) {
169 read(x); read(y);
170 add(x, y);
171 add(y, x);
172 }
173 DFS_1(1, 0);
174 DFS_2(1, 1);
175 for(int i = 1; i <= n; i++) {
176 int x = id[n + 1 - i];
177 if(top[x] == x) {
178 build(pos[x], pos[x] + len[x] - 1, rt[x]);
179 if(fa[x]) {
180 int temp = std::max(seg[rt[x]][0], seg[rt[x]][1]);
181 f[fa[x]][1] += temp;
182 f[fa[x]][0] += std::max(std::max(seg[rt[x]][2], seg[rt[x]][3]), temp);
183 }
184 }
185 }
186
187 for(int i = 1, x, y; i <= m; i++) {
188 read(x); read(y);
189 change(x, y);
190 int a = std::max(seg[rt[1]][0], seg[rt[1]][1]);
191 int b = std::max(seg[rt[1]][2], seg[rt[1]][3]);
192 printf("%d\n", std::max(a, b));
193 }
194
195 return 0;
196 }
AC代码