动态DP其实挺简单一个东西。
把DP值的定义改成去掉重儿子之后的DP值。
重链上的答案就用线段树/lct维护，维护子段/矩阵都可以。其实本质上差不多...
修改的时候在log个线段树上修改。轻儿子所在重链的线段树的根拿去更新父亲的DP值。
#include <cstdio>
#include <algorithm> const int N = , INF = 0x3f3f3f3f; template <class T> inline void read(T &x) {
x = ;
char c = getchar();
bool f = ;
while(c < '' || c > '') {
if(c == '-') {
f = ;
}
c = getchar();
}
while(c >= '' && c <= '') {
x = (x << ) + (x << ) + c - ;
c = getchar();
}
if(f) {
x = (~x) + ;
}
return;
} struct Edge {
int nex, v;
}edge[N << ]; int tp; // 0 0 0
// 1 0 1
// 2 1 0
// 3 1 1 int top[N], e[N], siz[N], pos[N], id[N], val[N], fa[N], son[N], d[N], num, n, len[N];
int f[N][], seg[N * ][], tot, ls[N * ], rs[N * ], rt[N]; inline void add(int x, int y) {
tp++;
edge[tp].v = y;
edge[tp].nex = e[x];
e[x] = tp;
return;
} void DFS_1(int x, int f) { // son siz fa d
fa[x] = f;
d[x] = d[f] + ;
siz[x] = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == f) {
continue;
}
DFS_1(y, x);
siz[x] += siz[y];
if(siz[y] > siz[son[x]]) {
son[x] = y;
}
}
return;
} void DFS_2(int x, int f) { // pos id top
top[x] = f;
pos[x] = ++num;
id[num] = x;
len[x] = ;
if(son[x]) {
DFS_2(son[x], f);
len[x] = len[son[x]] + ;
}
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == son[x] || y == fa[x]) {
continue;
}
DFS_2(y, y);
}
return;
} inline void pushup(int o) {
int l = ls[o], r = rs[o];
seg[o][] = std::max(seg[l][] + seg[r][], seg[l][] + seg[r][]);
seg[o][] = std::max(seg[o][], seg[l][] + seg[r][]); seg[o][] = std::max(seg[l][] + seg[r][], seg[l][] + seg[r][]);
seg[o][] = std::max(seg[o][], seg[l][] + seg[r][]); seg[o][] = std::max(seg[l][] + seg[r][], seg[l][] + seg[r][]);
seg[o][] = std::max(seg[o][], seg[l][] + seg[r][]); seg[o][] = std::max(seg[l][] + seg[r][], seg[l][] + seg[r][]);
seg[o][] = std::max(seg[o][], seg[l][] + seg[r][]);
return;
} inline void build(int l, int r, int &o) {
if(!o) {
o = ++tot;
}
if(l == r) {
seg[o][] = f[id[r]][];
seg[o][] = -INF;
seg[o][] = -INF;
seg[o][] = val[id[r]] + f[id[r]][];
return;
}
int mid = (l + r) >> ;
build(l, mid, ls[o]);
build(mid + , r, rs[o]);
pushup(o);
return;
} void change(int p, int l, int r, int o) {
//printf("change -- : %d %d %d \n", p, l, r);
if(l == r) {
seg[o][] = f[id[r]][];
seg[o][] = -INF;
seg[o][] = -INF;
seg[o][] = val[id[r]] + f[id[r]][];
//printf("%d = %d + %d \n", id[r], val[id[r]], f[id[r]][1]);
return;
}
int mid = (l + r) >> ;
if(p <= mid) {
change(p, l, mid, ls[o]);
}
else {
change(p, mid + , r, rs[o]);
}
pushup(o);
//printf("%d %d \n", id[l], id[r]);
//printf("%d %d %d %d \n", seg[o][0], seg[o][1], seg[o][2], seg[o][3]);
return;
} inline void change(int x, int v) {
//printf("change %d %d \n", x, v);
val[x] = v;
while(x) {
int xx = top[x];
if(fa[xx]) {
int temp = std::max(seg[rt[xx]][], seg[rt[xx]][]);
f[fa[xx]][] -= temp;
f[fa[xx]][] -= std::max(std::max(seg[rt[xx]][], seg[rt[xx]][]), temp);
}
//printf("ch %d %d %d \n", x, xx, id[pos[xx] + len[xx] - 1]);
change(pos[x], pos[xx], pos[xx] + len[xx] - , rt[xx]);
if(fa[xx]) {
int temp = std::max(seg[rt[xx]][], seg[rt[xx]][]);
f[fa[xx]][] += temp;
f[fa[xx]][] += std::max(std::max(seg[rt[xx]][], seg[rt[xx]][]), temp);
}
x = fa[xx];
}
return;
} int main() {
int m;
read(n); read(m);
for(int i = ; i <= n; i++) {
read(val[i]);
}
for(int i = , x, y; i < n; i++) {
read(x); read(y);
add(x, y);
add(y, x);
}
DFS_1(, );
DFS_2(, );
for(int i = ; i <= n; i++) {
int x = id[n + - i];
if(top[x] == x) {
build(pos[x], pos[x] + len[x] - , rt[x]);
if(fa[x]) {
int temp = std::max(seg[rt[x]][], seg[rt[x]][]);
f[fa[x]][] += temp;
f[fa[x]][] += std::max(std::max(seg[rt[x]][], seg[rt[x]][]), temp);
}
}
} for(int i = , x, y; i <= m; i++) {
read(x); read(y);
change(x, y);
int a = std::max(seg[rt[]][], seg[rt[]][]);
int b = std::max(seg[rt[]][], seg[rt[]][]);
printf("%d\n", std::max(a, b));
} return ;
}
AC代码
还有noip最后一题，虽然正解是倍增DP但是显然写动态DP啊...
注意树剖和线段树别写错了..没开O2少用std的函数
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath> typedef long long LL;
const int N = ;
const LL INF = 1e17; template <class T> inline void read(T &x) {
x = ;
char c = getchar();
while(c < '' || c > '') {
c = getchar();
}
while(c >= '' && c <= '') {
x = (x << ) + (x << ) + c - ;
c = getchar();
}
return;
} struct Edge {
int nex, v;
}edge[N * ]; int tp; LL val[N], f[N * ][][], Val[N][];
int e[N], n, m;
int fa[N], top[N], pos[N], id[N], siz[N], son[N], num, d[N], ed[N]; // tree div
int tot, ls[N * ], rs[N * ], rt[N]; // segment tree
char str[]; inline void add(int x, int y) {
tp++;
edge[tp].v = y;
edge[tp].nex = e[x];
e[x] = tp;
return;
} void DFS_1(int x, int f) { // fa son siz d
fa[x] = f;
siz[x] = ;
d[x] = d[f] + ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == f) {
continue;
}
DFS_1(y, x);
siz[x] += siz[y];
if(siz[y] > siz[son[x]]) {
son[x] = y;
}
}
//printf("son %d = %d \n", x, son[x]);
//printf("siz %d = %d \n", x, siz[x]);
return;
} void DFS_2(int x, int f) { // top pos id
pos[x] = ++num;
top[x] = f;
id[num] = x;
ed[f] = num;
//printf("x = %d ed %d = %d \n", x, f, ed[f]);
if(son[x]) {
DFS_2(son[x], f);
}
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == fa[x] || y == son[x]) {
continue;
}
DFS_2(y, y);
}
return;
} inline LL mymin(LL x, LL y) {
return x < y ? x : y;
} inline void exmin(LL &a, LL b) {
a > b ? a = b : ;
return;
} inline void pushup(int o) {
int l = ls[o], r = rs[o];
f[o][][] = INF;
exmin(f[o][][], f[l][][] + f[r][][]);
exmin(f[o][][], f[l][][] + f[r][][]);
exmin(f[o][][], f[l][][] + f[r][][]);
f[o][][] = INF;
exmin(f[o][][], f[l][][] + f[r][][]);
exmin(f[o][][], f[l][][] + f[r][][]);
exmin(f[o][][], f[l][][] + f[r][][]);
f[o][][] = INF;
exmin(f[o][][], f[l][][] + f[r][][]);
exmin(f[o][][], f[l][][] + f[r][][]);
exmin(f[o][][], f[l][][] + f[r][][]);
f[o][][] = INF;
exmin(f[o][][], f[l][][] + f[r][][]);
exmin(f[o][][], f[l][][] + f[r][][]);
exmin(f[o][][], f[l][][] + f[r][][]);
return;
} void build(int l, int r, int &o) {
if(!o) {
o = ++tot;
}
if(l == r) {
// init
int x = id[r];
f[o][][] = Val[x][];
f[o][][] = INF;
f[o][][] = INF;
f[o][][] = val[x] + Val[x][];
return;
}
int mid = (l + r) >> ;
build(l, mid, ls[o]);
build(mid + , r, rs[o]);
pushup(o);
return;
} inline int lca(int x, int y) {
while(top[x] != top[y]) {
if(d[top[x]] <= d[top[y]]) {
y = fa[top[y]];
}
else {
x = fa[top[x]];
}
}
return (d[x] < d[y]) ? x : y;
} inline bool link(int x, int y) {
int z = lca(x, y);
return std::abs(d[x] - d[y]) == && (z == x || z == y);
} inline void change(int p, int v, int l, int r, int o) {
//printf("change %d %d %d %d \n", p, v, l, r);
if(l == r) {
if(v) {
f[o][][] = INF;
}
else {
f[o][][] = INF;
}
return;
}
int mid = (l + r) >> ;
if(p <= mid) {
change(p, v, l, mid, ls[o]);
}
else {
change(p, v, mid + , r, rs[o]);
}
pushup(o);
return;
} inline void update(int p, int l, int r, int o) {
if(l == r) {
int x = id[r];
f[o][][] = Val[x][];
f[o][][] = val[x] + Val[x][];
return;
}
int mid = (l + r) >> ;
if(p <= mid) {
update(p, l, mid, ls[o]);
}
else {
update(p, mid + , r, rs[o]);
}
pushup(o);
return;
} inline void change(int x, int a) {
int xx = x;
while(x) {
if(fa[top[x]]) {
LL temp = mymin(f[rt[top[x]]][][], f[rt[top[x]]][][]);
Val[fa[top[x]]][] -= temp;
Val[fa[top[x]]][] -= mymin(mymin(f[rt[top[x]]][][], f[rt[top[x]]][][]), temp);
}
if(x != xx)
update(pos[x], pos[top[x]], ed[top[x]], rt[top[x]]);
else
change(pos[x], a, pos[top[x]], ed[top[x]], rt[top[x]]);
if(fa[top[x]]) {
LL temp = mymin(f[rt[top[x]]][][], f[rt[top[x]]][][]);
Val[fa[top[x]]][] += temp;
Val[fa[top[x]]][] += mymin(mymin(f[rt[top[x]]][][], f[rt[top[x]]][][]), temp);
}
x = fa[top[x]];
}
return;
} inline void recover(int x) {
while(x) {
if(fa[top[x]]) {
LL temp = mymin(f[rt[top[x]]][][], f[rt[top[x]]][][]);
Val[fa[top[x]]][] -= temp;
Val[fa[top[x]]][] -= mymin(mymin(f[rt[top[x]]][][], f[rt[top[x]]][][]), temp);
}
update(pos[x], pos[top[x]], ed[top[x]], rt[top[x]]);
if(fa[top[x]]) {
LL temp = mymin(f[rt[top[x]]][][], f[rt[top[x]]][][]);
Val[fa[top[x]]][] += temp;
Val[fa[top[x]]][] += mymin(mymin(f[rt[top[x]]][][], f[rt[top[x]]][][]), temp);
}
x = fa[top[x]];
}
return;
} int main() { //freopen("in.in", "r", stdin);
//freopen("my.out", "w", stdout);
read(n); read(m);
scanf("%s", str);
for(register int i = ; i <= n; i++) {
read(val[i]);
}
for(register int i = , x, y; i < n; i++) {
read(x); read(y);
add(x, y); add(y, x);
}
// prework
DFS_1(, );
DFS_2(, );
// build
for(register int a = n; a >= ; a--) {
int x = id[a];
if(top[x] == x) {
build(pos[x], ed[x], rt[x]);
if(fa[x]) {
int father = fa[x];
LL temp = mymin(f[rt[x]][][], f[rt[x]][][]);
Val[father][] += temp;
Val[father][] += mymin(mymin(f[rt[x]][][], f[rt[x]][][]), temp);
}
}
} for(register int i = , x, a, y, b; i <= m; i++) {
scanf("%d%d%d%d", &x, &a, &y, &b);
if(!a && !b && link(x, y)) {
puts("-1");
continue;
}
change(x, a);
change(y, b);
printf("%lld\n", mymin(mymin(f[rt[]][][], f[rt[]][][]), mymin(f[rt[]][][], f[rt[]][][])));
recover(x);
recover(y);
} return ;
}
AC代码