Lotuses's Blog

树形 dp 学习笔记

  • ~18.39K 字
  1. 1. P1352 没有上司的舞会
  2. 2. P2015 二叉苹果树
  3. 3. P2014【CTSC1997】选课
  4. 4. P4316 绿豆蛙的归宿
  5. 5. P1273 有线电视网
  6. 6. P2656 采蘑菇
  7. 7. P2585【ZJOI2006】三色二叉树

虽然树形 dp 并未在一大论文之中获得一席之地，但是却无时不体现出 dp 与记忆化搜索的联系与结合。

简单来说，树形 dp 指一类发生在树上的状态转移与优化问题，与一般 dp 问题拥有类似的特征，分阶段，有状态，只不过阶段为层数，状态为节点。后效性与子问题需要着重考虑，不然可能出现设计状态出错的问题。

拿例题说话。

P1352 没有上司的舞会

这是一道树形 dp 模板题。

首先，每一个子树相互独立，互不影响，所以无后效性，且保证了子问题最优的要求。

其次，设计状态，每个节点作为一个状态，代表了子树的最优情况。

但是题目有特殊要求，员工选了就不能选他的直接上司。为了保证状态的准确，增加一维，表示此位置有没有选择，以决定上层的上司能否选择。

因此，可以得到树形 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
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

const int maxn = 12004;
int r[maxn];

struct Edge {
    int u, v;
};
std::vector<Edge> G[maxn];
int faa[maxn];
int rem[maxn][2];

int dfs(int cur, int t) {
    if (rem[cur][t] != 0) {
        return rem[cur][t];
    }
    if (G[cur].size() == 0) {
        if (t == 0) return 0;
        else return rem[cur][t] = r[cur];
    }
    int ans = 0;
    if (t == 0) {
        for (Edge e : G[cur]) {
            ans += std::max(dfs(e.v, 0), dfs(e.v, 1));
        }
    } else {
        for (Edge e : G[cur]) {
            ans += dfs(e.v, 0);
        }
        ans += r[cur];
    }
    return rem[cur][t] = ans;

}

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    int n;
    read(n);
    for (int i = 1; i <= n; i++) {
        read(r[i]);
    }

    int u, v;
    for (int i = 1; i <= n - 1; i++) {
        read(u, v);
        G[v].push_back({v, u});
        faa[u]++;
    }
    int fa;
    for (int i = 1; i <= n; i++) {
        if (!faa[i]) {
            fa = i;
            break;
        }
    }
    writeln(std::max(dfs(fa, 1), dfs(fa, 0)));
    return 0;
}

多倍经验：P2016 战略游戏；

P2015 二叉苹果树

题目大意：删掉一些枝条使边为题目要求 + 仍旧联通，保持树的性质，且边权和最大。（要求必须要有根 1）

由于保证了树必然是二叉树，且每个节点要么满要么没有儿子，所以直接对儿子进行枚举。像方才那样设计递推式，将第二维改成已经选择了多少个边，之后向上递推，完成 dp。

按照这个做法完成这道题目时间绰绰有余。

但是，对于这道相似的题目，却完全不一样了。

P2014【CTSC1997】选课

题目大意：对森林中每棵树选择一些对应拓扑顺序节点，使所有节点数量符合要求，且权值最大。

在这道题中，并未保证每个节点的儿子情况，甚至是森林，导致在节点中枚举鸽节点中情况过多，每个节点枚举代价太高。

因此，考虑如何优化每个单独的节点的情况。

一种很新颖的做法，dp 套 dp。

这么多选择，其实就是背包对容量的很多选择，和 01 背包是一个道理，只不过对于每个物品都有 1 ~ m 种可能，多枚举一层。

隐去一维，树 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
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

const int maxn = 305;
struct Edge {
    int u, v;
};
std::vector<Edge> G[maxn];
int w[maxn];
int f[maxn][maxn];
int n, m;

void insert(int u, int v) {
    G[u].push_back({u, v});
    G[v].push_back({v, u});
}

void dfs(int u, int fa) {
    f[u][1] = w[u];
    for (auto e : G[u]) {
        if (e.v != fa) {
            dfs(e.v, u);
            for (int k = m; k >= 1; k--) {
                for (int j = 0; j < k; j++) {
                    f[u][k] = std::max(f[u][k], f[u][k - j] + f[e.v][j]);
                }
            }
        }
    }
}

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

    read(n, m); m++;
    
    for (int i = 1; i <= n; i++) {
        static int x;
        read(x, w[i]);
        insert(i, x);
    }
    
    dfs(0, -1);
    writeln(f[0][m]);
    return 0;
}

P4316 绿豆蛙的归宿

初看这道题似乎挺麻烦的，还得找所有路径对应概率乘积求期望。

但是，画几个草图就能发现，每条边的贡献与选择的路无关，只和自身的位置和父亲节点有关。

那么就能将概率递推求得，再用概率乘上边权，加起来便是总的期望。

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
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

int n, m;
const int maxn = 400005;
struct Edge {
    int u, v, w;
}; std::vector<Edge> G[maxn];
int in[maxn], out[maxn];
int L[maxn], cnt = 0;
std::vector<Edge> P[maxn];
double p[maxn], f[maxn];

void topo() {
    std::queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!in[i]) q.push(i);
    }
    while (!q.empty()) {
        int ft = q.front(); q.pop();
        L[++cnt] = ft;
        for (auto e : G[ft]) {
            if (--in[e.v] == 0) {
                q.push(e.v);
            }
        }
    }
}

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    read(n, m);
    for (int i = 1; i <= m; i++) {
        static int u, v, w;
        read(u, v, w);
        G[u].push_back({u, v, w});
        P[v].push_back({v, u, w});
        in[v]++;
        out[u]++;
    }
    topo();

    p[1] = 1;
    for (int i = 2; i <= cnt; i++) {
        for (auto e : P[L[i]]) {
            p[e.u] += 1.0 / out[e.v] * p[e.v];
            f[e.u] += 1.0 / out[e.v] * p[e.v] * e.w;
        }
        // printf("%d %.2lf %.2lf\n", L[i], p[L[i]], f[L[i]]);
    }
    double ans = 0;
    for (int i = 1; i <= n; i++) ans += f[i];
    printf("%.2lf\n", ans);
    return 0;
}

P1273 有线电视网

多倍经验，与《选课》类似，树形背包。但是要注意循环内枚举顺序与范围优化，否则滚动/时间是不正确的。

需要注意的是，这道题目中，背包容量不能设置为边权。选择不同的起始点会影响到后来的选择，而且边权之和可以为负，不好处理且空间爆炸，因此可以转换思路，改成以个数作为容量，后面从大到小判断并输出。

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
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

const int maxn = 3005;
struct Edge {
    int u, v, w;
};
std::vector<Edge> G[maxn];
int f[maxn][maxn];
int n, m, i;

int dfs(int u) {
    f[u][0] = 0;
    if (G[u].size() == 0) {
        return 1;
    }
    int szz = 0;
    for (auto e : G[u]) {
        int sz = dfs(e.v);
        for (int j = sz + szz; j >= 0; j--) {
            for (int k = 0; k <= sz; k++) {
                f[u][j] = std::max(f[u][j], f[e.v][k] + f[u][j - k] - e.w);
            }
        }
        szz += sz;
    }
    return szz;
}

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    read(n, m);
    for (i = 1; i <= n - m; i++) {
        static int k, a, c;
        read(k);
        for (int j = 1; j <= k; j++) {
            read(a, c);
            G[i].push_back({i, a, c});
        }
    }
    memset(f, -63, sizeof(f));
    for (; i <= n; i++) {
        static int c;
        read(c); f[i][1] = c;
    }
    dfs(1);
    for (int i = m; i >= 0; i--) {
        if (f[1][i] >= 0) {
            writeln(i);
            return 0;
        }
    }
    writeln(0);
    return 0;
}

P2656 采蘑菇

图上 dp。DAG 上最长路模板，dp 可做到 。

大概思路，缩点算点权后在 DAG 上求最长路即可，数据范围不大，所以怎么搞都行。

需要注意的是，最好重新建图，否则容易混乱，导致我调了近一个小时。

以及精度问题，这道题虽然仅有小数点后一位，但是涉及到小数变整数的截取操作，因此要加 eps，不然会出现实际上 1 但是在内部存储了 0.9999999999 然后向下取整截掉了。

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>

const int maxn = 400004;
int n, m;
struct Edge {
    int u, v, w, q;
    bool re;
};
std::vector<Edge> G[maxn];

int cnt;
int dfn[maxn], low[maxn];
bool vis[maxn], in_stack[maxn];
std::stack<int> st;
std::vector<std::vector<int> > pot;
int pc[maxn];

void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    vis[u] = true; in_stack[u] = true;
    st.push(u);
    for (auto e : G[u]) {
        if (!vis[e.v]) {
            tarjan(e.v);
            low[u] = std::min(low[u], low[e.v]);
        } else if (in_stack[e.v]) {
            low[u] = std::min(low[u], dfn[e.v]);
        }
    }
    if (dfn[u] == low[u]) {
        std::vector<int> v; v.clear();
        while (st.top() != u) {
            v.push_back(st.top());
            in_stack[st.top()] = 0;
            pc[st.top()] = pot.size() + 1;
            st.pop();
        }
        v.push_back(u);
        in_stack[st.top()] = 0;
        pc[st.top()] = pot.size() + 1;
        st.pop();
        // std::reverse(v.begin(), v.end());
        pot.push_back(v);
    }
}

int f[maxn], in[maxn];
int cnt1[maxn];
// bool vis1[maxn];
// void dfs1(int u, int id) {
//     if (vis1[u]) return;
//     vis1[u] = true;
//     for (auto e : G[u]) {
//         if (pc[e.v] == id) {
//             in[id]--;
//             dfs1(e.v, id);
//             while (e.w > 0) {
//                 cnt1[id] += e.w;
//                 e.w = e.w * e.q;
//             }
//         }
//     }
// }

std::vector<Edge> G2[maxn];

void bfs2(int s) {
    f[s] = cnt1[s];
    // writeln(f[s]);
    std::queue<int> q;
    // q.push(s);
    for (int i = 1; i <= pot.size(); i++) {
        if (in[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int ft = q.front(); q.pop(); // ft is ok in default
        for (auto e : G2[ft]) {
            f[e.v] = std::max(f[e.v], f[ft] + e.w + cnt1[e.v]);
            in[e.v]--;
            if (in[e.v] == 0) q.push(e.v);
        }
    }
}


int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    int s;
    memset(pc, -1, sizeof(pc));
    memset(f, -63, sizeof(f));
    read(n, m);
    for (int i = 1; i <= m; i++) {
        static int u, v, w; static double q;
        read(u, v, w); scanf("%lf", &q);
        G[u].push_back({u, v, w, int(q * 10 + 0.0001), false});
        // in[v]++;
    }
    read(s);

    for (int i = 1; i <= n; i++) if (!vis[i]) tarjan(i);
    // for (auto v : pot) {
    //     if (v.size() == 1) {
    //         pc[v[0]] = v[0];
    //         continue;
    //     }
    //     int id = ++n;
    //     pc[id] = id;
    //     for (int q : v) {
    //         pc[q] = id;
    //         in[id] += in[q];
    //     }
    //     dfs1(v[0], id);
    //     for (int q : v) {
    //         for (auto e : G[q]) {
    //             if (pc[e.v] == id) continue;
    //             e.u = id;
    //             G[id].push_back(e);
    //         }
    //     }
    // }
    for (int i = 1; i <= n; i++) {
        for (auto e : G[i]) {
            if (pc[e.u] != pc[e.v]) {
                G2[pc[e.u]].push_back({pc[e.u], pc[e.v], e.w, e.q, e.re});
                in[pc[e.v]]++;
            } else {
                while (e.w > 0) {
                    cnt1[pc[e.u]] += e.w;
                    e.w = e.w * e.q;
                    e.w /= 10;
                }
            }
        }
    }

    // writeln(pc[s], in[pc[s]]);
    bfs2(pc[s]);
    // writeln(pot.size());
    int ans = 0;
    for (int i = 1; i <= pot.size(); i++) {
        ans = std::max(ans, f[i]);
        // writeln(f[i]);
    }
    writeln(ans);
    return 0;
}

P2585【ZJOI2006】三色二叉树

题目不难，主要考察了树的表示方法（模拟）和一个很简单的三状态树上 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
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>

const int maxn = 500005;
int s[maxn], n = 0;
void read() {
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') s[++n] = ch - '0', ch = getchar();
}

std::stack<std::pair<int, int> > st;
int l[maxn], r[maxn];
void init() {
    memset(l, -1, sizeof(r));
    memset(r, -1, sizeof(r));
    for (int i = 1; i <= n; i++) {
        if (!st.empty()) {
            auto tp = st.top(); st.pop();
            switch (tp.second)
            {
                case 1:
                    l[tp.first] = i;
                    break;
                case 2:
                    r[tp.first] = i;
                    break;
            
                default:
                    break;
            }
        }

        switch (s[i])
        {
            case 1:
                st.push(std::make_pair(i, 1));
                break;
                
            case 2:
                st.push(std::make_pair(i, 2));
                st.push(std::make_pair(i, 1));
                break;

            default:
                break;
        }
    }
}

int f1[maxn][3], f2[maxn][3];

void dfs(int u) {
    if (s[u] == 0) {
        f1[u][0] = 1; f1[u][1] = f1[u][2] = 0;
        f2[u][0] = 1; f2[u][1] = f2[u][2] = 0;
    } else if (s[u] == 1) {
        dfs(l[u]);
        f1[u][0] = std::max(f1[l[u]][1], f1[l[u]][2]) + 1;
        f1[u][1] = std::max(f1[l[u]][0], f1[l[u]][2]);
        f1[u][2] = std::max(f1[l[u]][0], f1[l[u]][1]);
        
        f2[u][0] = std::min(f2[l[u]][1], f2[l[u]][2]) + 1;
        f2[u][1] = std::min(f2[l[u]][0], f2[l[u]][2]);
        f2[u][2] = std::min(f2[l[u]][0], f2[l[u]][1]);
    } else {
        dfs(l[u]);
        dfs(r[u]);
        f1[u][0] = std::max(f1[l[u]][1] + f1[r[u]][2], f1[l[u]][2] + f1[r[u]][1]) + 1;
        f1[u][1] = std::max(f1[l[u]][0] + f1[r[u]][2], f1[l[u]][2] + f1[r[u]][0]);
        f1[u][2] = std::max(f1[l[u]][0] + f1[r[u]][1], f1[l[u]][1] + f1[r[u]][0]);

        f2[u][0] = std::min(f2[l[u]][1] + f2[r[u]][2], f2[l[u]][2] + f2[r[u]][1]) + 1;
        f2[u][1] = std::min(f2[l[u]][0] + f2[r[u]][2], f2[l[u]][2] + f2[r[u]][0]);
        f2[u][2] = std::min(f2[l[u]][0] + f2[r[u]][1], f2[l[u]][1] + f2[r[u]][0]);
    }
}

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

    read();
    init();

    memset(f1, -63, sizeof(f1));
    memset(f2, 63, sizeof(f2));
    dfs(1);
    writeln(std::max(f1[1][0], std::max(f1[1][1], f1[1][2])),
            std::min(f2[1][0], std::min(f2[1][1], f2[1][2])));
    return 0;
}

P2515【HAOI2010】软件安装

依赖背包，以前没填的坑，今天终于填了。

简单来说，就是利用树来限制转移的源和目标，使父亲节点必须要被选上，然后再在树上做一个树上 01 背包即可。

细节挺多的，比如说，有可能某些软件互相依赖，本来以为题目保证了是无环图，但是看讨论区才注意到，重构了一遍，加入了缩点；

重建图的时候一定要把那些与 0 无关的点连上，已经连了就不能连了，多连会出事。

拓扑到某一点时，需要先单独将该点的权值做一遍和先前做过儿子节点的 01 背包，因为不能跟儿子节点一起做，否则就会算重。

在拓扑排序中顺便把 dp 以向外扩散的方式递推出去，不选择当前节点的那些容量位置因为被滚动下来了要重新置为极小值。

最后取答案只取 0 上的答案，dp 会搞定一切。

debug 挺麻烦的，最好一遍过。

思维绿，实现紫？

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
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <vector>

const int maxn = 1005;
int n, m;
int w[maxn], v[maxn], d[maxn];
int f[maxn][maxn];
struct Edge {
    int u, v;
}; std::vector<Edge> G[maxn];

void insert(int u, int v) {
    G[u].push_back({u, v});
}

int id[maxn], ct = 0;
int dfn[maxn], low[maxn], cnt = 0;
bool ins[maxn];
std::stack<int> st;
void tarjan(int u) {
    dfn[u] = low[u] = ++cnt; ins[u] = true;
    st.push(u);
    for (auto e : G[u]) {
        if (!dfn[e.v]) {
            tarjan(e.v);
            low[u] = std::min(low[u], low[e.v]);
        } else if (ins[e.v]) {
            low[u] = std::min(low[u], dfn[e.v]);
        }
    }
    if (dfn[u] == low[u]) {
        ct++;
        while (st.top() != u) {
            id[st.top()] = ct;
            ins[st.top()] = false;
            st.pop();
        }
        id[st.top()] = ct;
        ins[st.top()] = false;
        st.pop();
    }
}

int Nw[maxn], Nv[maxn];
bool vis[maxn][maxn];
int in[maxn];
std::vector<Edge> Gn[maxn];

std::queue<int> q;
void sort() {
    memset(f, -63, sizeof(f));
    for (int i = 1; i <= ct; i++) {
        if (!in[i]) q.push(i);
        f[i][0] = 0;
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int j = m; j >= Nv[u]; j--) {
            f[u][j] = f[u][j - Nv[u]] + Nw[u];
        }
        for (int j = Nv[u] - 1; j >= 1; j--) {
            f[u][j] = -998244353;
        }
        for (auto e : Gn[u]) {
            for (int j = m; j >= 0; j--) {
                for (int k = 0; k <= j; k++) {
                    f[e.v][j] = std::max(f[e.v][j], f[e.v][j - k] + f[u][k]);
                }
            }
            in[e.v]--;
            if (!in[e.v]) {
                q.push(e.v);
            }
        }
    }
}

int main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    read(n, m);
    for (int i = 1; i <= n; i++) read(v[i]);
    for (int i = 1; i <= n; i++) read(w[i]);
    for (int i = 1; i <= n; i++) {
        read(d[i]);
        insert(i, d[i]);
    }

    for (int i = 0; i <= n; i++) if (!dfn[i]) tarjan(i);

    for (int i = 0; i <= n; i++) {
        Nw[id[i]] += w[i];
        Nv[id[i]] += v[i];
        bool flag = 0;
        for (auto e : G[i]) {
            if (id[i] != id[e.v] && !vis[id[i]][id[e.v]]) {
                Gn[id[i]].push_back({id[i], id[e.v]});
                vis[id[i]][id[e.v]] = true;
                in[id[e.v]]++;
                flag |= true;
            }
        }
        if (!flag && !vis[id[i]][id[0]]){
            Gn[id[i]].push_back({id[i], id[0]});
            vis[id[i]][id[0]] = true;
            in[id[0]]++;
        }
    }
    sort();
    int ans = 0;
    for (int q = 0; q <= 0; q++)
    for (int i = Nv[id[q]]; i <= m; i++) {
        ans = std::max(ans, f[id[q]][i]);
    }
    writeln(ans);
    return 0;
}

P2986【USACO10MAR】Great Cow Gathering G

找树的带权重心，而且是边权点权一起有的那种。

套路树形 dp，先预处理子树大小（加点权），顺便把 （选择在 时的总代价）算了。

再从 开始，向下递推，式子为：

是上方点数量， 是下方点数量，其他自行理解。

实现不难，好像要开 long long？不知道不管了，反正加了又不会 MLE。

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
// Copyright 2023 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

#define int long long

const int maxn = 400005;
int c[maxn];

struct Edge {
    int u, v, w;
}; std::vector<Edge> G[maxn];

void insert(int u, int v, int w) {
    G[u].push_back({u, v, w});
    G[v].push_back({v, u, w});
}

int f[maxn];
int sum[maxn];
void dfs1(int u, int fa, int w) {
    sum[u] = c[u];
    f[1] += w * c[u];
    for (auto e : G[u]) {
        if (e.v != fa) {
            dfs1(e.v, u, w + e.w);
            sum[u] += sum[e.v];
        }
    }
}

void dfs2(int u, int fa) {
    for (auto e : G[u]) {
        if (e.v != fa) {
            f[e.v] = f[u] + e.w * (sum[1] - sum[e.v] * 2);
            dfs2(e.v, u);
        }
    }
}

signed main() {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    int n;
    read(n);
    for (int i = 1; i <= n; i++) {
        read(c[i]);
    }
    for (int i = 1; i < n; i++) {
        static int a, b, l;
        read(a, b, l);
        insert(a, b, l);
    }

    dfs1(1, -1, 0);
    dfs2(1, -1);
    int ans = f[1];
    for (int i = 2; i <= n; i++) {
        ans = std::min(ans, f[i]);
    }
    writeln(ans);
    return 0;
}

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可