Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

动态DP模板

发表于 分类于
本文字数： 8.2k 阅读时长 ≈ 7 分钟
标签：        

动态DP问题。

求树的最大权独立集，带修。

树剖写法中，矩阵中不包含重儿子的贡献。

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <cstdio>
#include <vector>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
template <class Type>
void chkmax(Type &x, Type k) { if (k > x) x = k; }
const int N = 1e5 + 10, inf = 1e8;
vector <int> g[N];
int n, m, w[N], p[N], d[N], sz[N], f[N][2];
int stmp, son[N], top[N], dfn[N], rnk[N], ed[N];
struct Matrix
{
    int w[2][2];
    Matrix () { w[0][0] = w[0][1] = w[1][0] = w[1][1] = -inf; }
    friend Matrix operator * (Matrix a, Matrix b)
    {
        Matrix res;
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                for (int k = 0; k < 2; ++k)
                    chkmax(res.w[i][j], a.w[i][k] + b.w[k][j]);
        return res;
    }
} v[N];
struct Node { int l, r; Matrix w; } tr[N << 2];
void pushup (int x) { tr[x].w = tr[x << 1].w * tr[x << 1 | 1].w; }
void build (int l = 1, int r = n, int x = 1)
{
    tr[x].l = l, tr[x].r = r;
    if (l == r) return void(tr[x].w = v[rnk[l]]);
    int mid = l + r >> 1;
    build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
    pushup(x);
}
void modify (int t, int x = 1)
{
    if (tr[x].l == tr[x].r) return void(tr[x].w = v[rnk[t]]);
    int mid = tr[x].l + tr[x].r >> 1;
    modify(t, t <= mid ? x << 1 : x << 1 | 1);
    pushup(x);
}
Matrix query (int l, int r, int x = 1)
{
    if (tr[x].l >= l && tr[x].r <= r) return tr[x].w;
    int mid = tr[x].l + tr[x].r >> 1;
    if (r <= mid) return query(l, r, x << 1);
    if (l > mid) return query(l, r, x << 1 | 1);
    return query(l, r, x << 1) * query(l, r, x << 1 | 1);
}
void dfs1 (int x)
{
    sz[x] = 1;
    for (int i : g[x]) if (i ^ p[x])
    {
        p[i] = x, d[i] = d[x] + 1;
        dfs1(i);
        sz[x] += sz[i];
        if (sz[i] > sz[son[x]]) son[x] = i;
    }
}
void dfs2 (int x, int t)
{
    rnk[dfn[x] = ++stmp] = x;
    top[x] = t;
    chkmax(ed[t], stmp);
    f[x][0] = 0, f[x][1] = w[x];
    v[x].w[0][0] = v[x].w[0][1] = 0, v[x].w[1][0] = w[x];
    if (!son[x]) return;
    dfs2(son[x], t);
    f[x][0] += max(f[son[x]][0], f[son[x]][1]), f[x][1] += f[son[x]][0];
    for (int i : g[x]) if (i ^ p[x] && i ^ son[x])
    {
        dfs2(i, i);
        f[x][0] += max(f[i][0], f[i][1]), f[x][1] += f[i][0];
        v[x].w[0][0] += max(f[i][0], f[i][1]);
        v[x].w[0][1] = v[x].w[0][0];
        v[x].w[1][0] += f[i][0];
    }
}
void ModifyPath (int x, int k)
{
    v[x].w[1][0] += k - w[x]; w[x] = k;
    while (x)
    {
        Matrix s = query(dfn[top[x]], ed[top[x]]);
        modify(dfn[x]);
        Matrix t = query(dfn[top[x]], ed[top[x]]);
        x = p[top[x]];
        v[x].w[0][0] += max(t.w[0][0], t.w[1][0]) - max(s.w[0][0], s.w[1][0]);
        v[x].w[0][1] = v[x].w[0][0];
        v[x].w[1][0] += t.w[0][0] - s.w[0][0];
    }
}
int main ()
{
    read(n, m);
    for (int i = 1; i <= n; ++i) read(w[i]);
    for (int i = 1, a, b; i < n; ++i)
    {
        read(a, b);
        g[a].push_back(b), g[b].push_back(a);
    }
    dfs1(1), dfs2(1, 1), build();
    for (int t, k; m; m--)
    {
        read(t, k);
        ModifyPath(t, k);
        Matrix res = query(dfn[1], ed[1]);
        write(max(res.w[0][0], res.w[1][0])), puts("");
    }
    return 0;
}

LCT写法复杂度更优，更好理解。

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <cstdio>
#include <vector>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
template <class Type>
void chkmax (Type &x, Type k) { if (k > x) x = k; }
const int N = 1e5 + 10, inf = 1e8;
struct Matrix
{
    int w[2][2];
    Matrix () {}
    Matrix (int f0, int f1) { w[0][0] = w[0][1] = f0, w[1][0] = f1, w[1][1] = -inf; }
    friend Matrix operator * (Matrix a, Matrix b)
    {
        Matrix res(-inf, -inf);
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                for (int k = 0; k < 2; ++k)
                    chkmax(res.w[i][j], a.w[i][k] + b.w[k][j]);
        return res;
    }
} v[N];
vector <int> g[N];
int n, m, w[N], f[N][2];
struct Node { Matrix w; int p, s[2]; } tr[N];
void pushup(int x)
{
    tr[x].w = Matrix(f[x][0], f[x][1]);
    if (tr[x].s[0]) tr[x].w = tr[tr[x].s[0]].w * tr[x].w;
    if (tr[x].s[1]) tr[x].w = tr[x].w * tr[tr[x].s[1]].w;
}
bool isroot(int x) { return tr[tr[x].p].s[0] ^ x && tr[tr[x].p].s[1] ^ x; }
void rotate(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    if (!isroot(y)) tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}
void splay(int x)
{
    for (; !isroot(x); rotate(x))
    {
        int y = tr[x].p, z = tr[y].p;
        if (!isroot(y))
            rotate((y == tr[z].s[1]) ^ (x == tr[y].s[1]) ? x : y);
    }
}
void access(int t)
{
    for (int x = t, y = 0; x; y = x, x = tr[x].p)
    {
        splay(x);
        if (tr[x].s[1])
        {
            Matrix &s = tr[tr[x].s[1]].w;
            f[x][0] += max(s.w[0][0], s.w[1][0]);
            f[x][1] += s.w[0][0];
        }
        if (y)
        {
            Matrix &s = tr[y].w;
            f[x][0] -= max(s.w[0][0], s.w[1][0]);
            f[x][1] -= s.w[0][0];
        }
        tr[x].s[1] = y;
        pushup(x);
    }
    splay(t);
}
void dfs (int x, int fa)
{
    f[x][1] = w[x];
    for (int i : g[x]) if (i ^ fa)
    {
        tr[i].p = x;
        dfs(i, x);
        f[x][0] += max(f[i][0], f[i][1]);
        f[x][1] += f[i][0];
    }
    tr[x].w = Matrix(f[x][0], f[x][1]);
}
int main()
{
    read(n, m);
    for (int i = 1; i <= n; ++i) read(w[i]);
    for (int i = 1, a, b; i < n; ++i)
    {
        read(a, b);
        g[a].push_back(b), g[b].push_back(a);
    }
    dfs(1, 0);
    for (int t, k; m; --m)
    {
        read(t, k);
        access(t), splay(t);
        f[t][1] += k - w[t], w[t] = k;
        pushup(t), splay(1);
        Matrix &s = tr[1].w;
        write(max(s.w[0][0], s.w[1][0])), puts("");
    }
    return 0;
}
相关文章