本节内容对树形dp做一个复习
另外还有部分状态压缩dp的内容

树形dp

LA3797

树形dp常见套路

POJ1463

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

const int maxn = 1500 + 5;
int hasFa[maxn];
int f[maxn][2];
vector<int> son[maxn];
int N;

void init() {
    Set(hasFa, 0);
    Set(f, 0);
    _for(i, 0, maxn) son[i].clear();
}

void dp(int u) {
    f[u][0] = 0;
    f[u][1] = 1;
    _for(i, 0, son[u].size()) {
        int v = son[u][i];
        dp(v);
        f[u][0] += f[v][1];
        f[u][1] += (min(f[v][0], f[v][1]));
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d", &N) != EOF) {
        init();
        _for(i, 0, N) {
            int u, k;
            scanf("%d:(%d)", &u, &k);
            _for(j, 0, k) {
                int v;
                scanf("%d", &v);
                son[u].push_back(v);
                hasFa[v] = 1;
            }
        }
        // then input finished
        int r = 0;
        _for(i, 0, N) if(!hasFa[i]) { r = i; break; }

        dp(r);
        printf("%d\n", min(f[r][0], f[r][1]));
    }
}

树形背包问题，倒序遍历

LA3797

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

const int maxn = 200 + 5;
const int inf = 0x3f3f3f3f;
map<string, int> dic;
int tot = 0;
int N, M;

vector<int> son[maxn];
bool hasFa[maxn];
int cost[maxn];
int sum[maxn];
int f[maxn][maxn];

void init() {
    dic.clear();
    tot = 0;
    Set(hasFa, 0);
    Set(sum, 0);
    _for(i, 0, maxn) son[i].clear();
}

void initdp() {
    _rep(i, 1, N) if(!hasFa[i]) son[0].push_back(i);
    Set(f, inf);
    f[0][0] = 0;
}

void dp(int u) {
    f[u][0] = 0;
    sum[u] = 1;

    _for(i, 0, son[u].size()) {
        int v = son[u][i];
        dp(v);

        sum[u] += sum[v];
        //debug(sum[u]);
        _forDown(t, N, 1) _forDown(j, t, 0) {
            if(t - j < 0) continue;
            f[u][t] = min(f[u][t], f[v][j] + f[u][t - j]);
        }
    }
    if(u) f[u][sum[u]] = cost[u];
}

int main() {
    freopen("input.txt", "r", stdin);
    string data;
    while (getline(cin, data)) {
        if(data[0] == '#') break;
        init();
        stringstream ss(data);
        ss >> N >> M;
        //debug(N), debug(M);
        _for(i, 0, N) {
            getline(cin, data);
            stringstream ss(data);
            string ctry, dctry;
            int x;

            ss >> ctry >> x;
            //debug(ctry), debug(x);
            if(!dic.count(ctry)) dic[ctry] = ++tot;
            cost[dic[ctry]] = x;
            //debug(dic[ctry]);

            while (ss >> dctry) {
                //debug(dctry);
                if(!dic.count(dctry)) dic[dctry] = ++tot;
                //debug(dic[dctry]);
                son[dic[ctry]].push_back(dic[dctry]);
                hasFa[dic[dctry]] = 1;
            }
        }
        //puts("");
        // input finished
        assert(tot == N);
        initdp();
        //for(auto x : son[0]) cout << x << " ";
        dp(0);

        int ans = inf;
        _forDown(k, N, M) ans = min(ans, f[0][k]);
        printf("%d\n", ans);
    }
}

树形dp与换根法

HDU2196
HDU2196-01
HDU2196-02

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

const int maxn = 10000 + 10;
int f1[maxn], f12nd[maxn], f2[maxn];
int pass[maxn];

int N;

class Graph {
public:
    int tot;
    int head[maxn], ver[maxn * 2], nxt[maxn * 2];
    int w[maxn * 2];

    void clear() {
        tot = 1;
        Set(head, 0);
        Set(ver, 0);
        Set(nxt, 0);
        Set(w, 0);
    }

    void add(int x, int y, int z) {
        ver[++tot] = y;
        w[tot] = z;

        nxt[tot] = head[x];
        head[x] = tot;
    }
};

Graph G;

void init() {
    Set(f1, -1);
    Set(f12nd, -1);
    Set(f2, -1);
    Set(pass, 0);
    G.clear();
}

bool vis[maxn];

void initvis() {
    Set(vis, 0);
}

void dp1(int u) {
    if(f1[u] >= 0) return;
    f1[u] = f12nd[u] = f2[u] = pass[u] = 0;
    vis[u] = 1;

    for(int e = G.head[u]; e; e = G.nxt[e]) {
        int v = G.ver[e];
        if(vis[v]) continue;

        //debug(v);

        dp1(v);

        if(f1[u] < f1[v] + G.w[e]) {
            f12nd[u] = max(f12nd[u], f1[u]);
            f1[u] = f1[v] + G.w[e];
            pass[u] = v;
        }
        else if(f12nd[u] < f1[v] + G.w[e]) {
            f12nd[u] = f1[v] + G.w[e];
        }
    }
    return;
}

void dp2(int u) {
    vis[u] = 1;
    for(int e = G.head[u]; e; e = G.nxt[e]) {
        int v = G.ver[e];
        if(vis[v]) continue;

        if(v == pass[u]) {
            // u - v is the segment of longest path
            f2[v] = max(f2[u], f12nd[u]) + G.w[e];
        }
        else f2[v] = max(f1[u], f2[u]) + G.w[e];
        dp2(v);
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d", &N) == 1 && N) {
        init();
        _rep(i, 2, N) {
            int v, w;
            scanf("%d%d", &v, &w);
            G.add(i, v, w);
            G.add(v, i, w);
        }

        // then dp1 and dp2
        initvis();
        dp1(1);

        initvis();
        dp2(1);

        _rep(i, 1, N) printf("%d\n", max(f1[i], f2[i]));
    }
}

高斯消元

BZOJ2337
BZOJ2337-01
BZOJ2337-02

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

const int maxn = 100 + 10;
const int maxm = 10000 + 10;
double A[maxn][maxn];
double K[maxn];
int N, M;

class Graph {
public:
    int tot;
    int head[maxn], ver[maxm << 1], nxt[maxm << 1], w[maxm << 1];
    void clear() {
        tot = 1;
        Set(head, 0);
        Set(ver, 0);
        Set(nxt, 0);
        Set(w, 0);
    }

    void add(int x, int y, int z) {
        ver[++tot] = y;
        w[tot] = z;

        nxt[tot] = head[x];
        head[x] = tot;
    }
};

Graph G;

void init() {
    G.clear();
    Set(A, 0);
    Set(K, 0);
}

void Gauss() {
    _rep(i, 1, N) {
        int r = i;
        _rep(j, i + 1, N) if(fabs(A[j][i]) > fabs(A[r][i])) r = j;
        if(r != i) _rep(k, 1, N + 1) swap(A[i][k], A[r][k]);

        double t = A[i][i];
        _rep(k, i + 1, N + 1) A[i][k] /= t;

        _rep(j, 1, N) if(i != j) {
            double t = A[j][i];
            _rep(k, 1, N + 1) A[j][k] -= t * A[i][k];
        }
    }
}

double build() {
    double ans = 0.0;
    _for(i, 0, 30) {
        Set(A, 0);
        _for(u, 1, N) {
            A[u][u] = 1.0;
            for(int e = G.head[u]; e; e = G.nxt[e]) {
                int v = G.ver[e];

                if((1 << i) & G.w[e]) A[u][v] += 1.0 / K[u], A[u][N + 1] += 1.0 / K[u];
                else A[u][v] -= 1.0 / K[u];
            }
        }
        A[N][N] = 1.0;
        Gauss();
        ans += A[1][N + 1] * (double)(1 << i);
    }

    return ans;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &N, &M);
    _rep(i, 1, M) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        G.add(u, v, w);
        K[u] += 1.0, K[v] += 1.0;
        if(u == v) K[u] -= 1.0;
        else G.add(v, u, w);
    }
    // then build matrix
    printf("%.3lf\n", build());
}