动态规划之树形dp

概括

树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。

基础

没有上司的舞会

某大学有 n 个职员，编号为 1 --- N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 Ai，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

思路分析

我们设 f(i,0/1) 代表以 i 为根的子树的最优解(第二维的值为 0 代表 i 不参加舞会的情况，1 代表 i 参加舞会的情况)。

对于每个状态，都存在两种决策(其中下面的 x 都是 i 的儿子)：

1. 上司不参加舞会时，下属可以参加，也可以不参加，此时有 f(i,0) = sum{max{f(x,1),f(x,0)}}。
2. 上司参加舞会时，下属都不会参加，此时有 f(i,1) = sum{f(x,0)} + Ai。

我们可以通过 DFS，在返回上一层时更新当前结点的最优解。

题解代码

const int maxN = 6e3 + 5;

vector<int> arr[maxN];
int happy[maxN];
int vis[maxN];
int dp[maxN][2];
int isRoot[maxN];

int dfs(int s) {
    vis[s] = 1;
    for (auto u : arr[s]) {
        if (vis[u]) continue;
        dfs(u);
        dp[s][1] += dp[u][0];
        dp[s][0] += max(dp[u][0], dp[u][1]);
    }
    dp[s][1] += happy[s];
}

int main() {
    int N;
    cin >> N;
    memset(vis, 0, sizeof(vis));
    memset(dp, 0, sizeof(dp));
    memset(isRoot, 1, sizeof(isRoot));
    for (int i = 1; i <= N; i++) cin >> happy[i];
    for (int i = 1; i < N; i++) {
        int k, l;
        cin >> l >> k;
        isRoot[l] = 0;
        arr[k].emplace_back(l);
    }
    for (int i = 1; i <= N; i++) {
        if (isRoot[i]) {
            dfs(i);
            cout << max(dp[i][0], dp[i][1]) << endl;
            break;
        }
    }
}

Computer

题意： 给出边有权的一棵树，求离每个节点最远的点的距离

思路分析

求一个树中所有节点能到达的最远距离。要用两个dfs。

首先第一个dfs求出所有每个节点i在其子树中的正向最大距离 dist[i][0] 和正向次大距离 dist[i][1] (如果i节点在子树中最大距离经过了2号儿子，那么次大距离就是不经过2号儿子的最大距离)。并且还要标记 longest[i]=j 表示节点i在其子树中的最大距离经过了节点j(即j是i的一个儿子)。

由上步我们获得了正向最大距离，正向次大距离和最大距离的儿子节点标记。画图可以知道我们建立的这棵树，i节点的最远距离只有两种选择：i节点所在子树的最大距离，或者i节点连接它的父节点所能到达的最大距离。(即前者往下走，后者先往上走之后很可能也往下走)

所以我们只要求出反向最大距离dist[i][2](即i节点往它的父节点走所能到达的最大距离)就可以知道i节点在整个树中能走的最大距离了。

dist[i][2]求法：i节点往它的父节j点走，如果它的父节点的正向最大距离不经过i的话，那么dist[i][2]要不就是它父节点的反向最大距离+W[i][j]要不就是它父节点的正向最大距离+ W[i][j].

如果它的父节点的正向最大距离经过i的话，那么dist[i][2]要不就是它父节点的反向最大距离+W[i][j]要不就是它父节点的正向次大距离+ W[i][j].

上面就是dfs2要求的值。最终f[i] = max(dist[i][0]，dist[i][2])

代码实现

struct Edge {
    int to;
    int val;
    Edge(int to, int val) : to(to), val(val) {}
};

const int maxN = 1e4 + 5;

vector<Edge> arr[maxN];
int dp[maxN][3];
int longest[maxN];
int vis[maxN];

void dfs1(int s, int fa) {
    vis[s] = 1;
    for (auto& e : arr[s]) {
        if (e.to == fa) continue;
        if (vis[e.to]) continue;
        dfs1(e.to, s);
        if (dp[s][0] < dp[e.to][0] + e.val) {
            longest[s] = e.to;
            dp[s][1] = max(dp[s][1], dp[s][0]);
            dp[s][0] = dp[e.to][0] + e.val;
        } else if (dp[s][1] < dp[e.to][0] + e.val) {
            dp[s][1] = dp[e.to][0] + e.val;
        }
    }
}

void dfs2(int s, int fa) {
    for (auto& e : arr[s]) {
        if (e.to == fa) continue;
        if (e.to == longest[s]) dp[e.to][2] = max(dp[s][1], dp[s][2]) + e.val;
        else dp[e.to][2] = max(dp[s][0], dp[s][2]) + e.val;
        dfs2(e.to, s);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    while (cin >> N && N) {
        for (auto& a : arr) a.clear();
        memset(dp, 0, sizeof(dp));
        memset(vis, 0, sizeof(vis));
        memset(longest, 0, sizeof(longest));
        for (int i = 2; i <= N; i++) {
            int u, val;
            cin >> u >> val;
            arr[u].emplace_back(i, val);
            arr[i].emplace_back(u, val);
        }
        dfs1(1, 1);
        dfs2(1, 1);
        for (int i = 1; i <= N; i++)
            cout << max(dp[i][0], dp[i][2]) << endl;
    }
}

Strategic game

const int maxN = 1505;

vector<int> arr[maxN];
int dp[maxN][2];

void dfs(int s, int fa) {
    dp[s][1] = 1;
    for (auto u : arr[s]) {
        if (u == fa) continue;
        dfs(u, s);
        dp[s][1] += min(dp[u][1], dp[u][0]);
        dp[s][0] += dp[u][1];
    }
}

int main() {
    int N;
    while (~scanf("%d", &N) && N) {
        memset(dp, 0, sizeof(dp));
        for (auto& a : arr) a.clear();
        for (int i = 0; i < N; i++) {
            int number, cnt;
            scanf("%d:(%d)", &number, &cnt);
            for (int j = 0; j < cnt; j++) {
                int u;
                scanf("%d", &u);
                arr[number].emplace_back(u);
                arr[u].emplace_back(number);
            }
        }
        dfs(0, 0);
        int ans = min(dp[0][1], dp[0][0]);
        cout << ans << endl;
    }
}

最大子树和

思路分析

一道比较简单的树形DP题, 题意就是让你求这个树上点权和最大的一个联通部分（连通分量）。

考虑设 f(i) 表示以 i 为根的所有子树中点权和最大的一个。

对于 u 和 u 的儿子 v，如果 f(v) >= 1 则它对答案有贡献，要保留，反之则要减掉。

题解代码

const int maxN = 16005;

int dp[maxN];
vector<int> arr[maxN];

void dfs(int s, int fa) {
    for (auto u : arr[s]) {
        if (u == fa) continue;
        dfs(u, s);
        if (dp[u] > 0) dp[s] += dp[u];
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> dp[i];
    }
    for (int i = 1; i <= N - 1; i++) {
        int u, v;
        cin >> u >> v;
        arr[u].emplace_back(v);
        arr[v].emplace_back(u);
    }
    dfs(1, 1);
    int ans = INT_MIN;
    for (int i = 1; i <= N; i++) ans = max(ans, dp[i]);
    cout << ans << endl;
}

加分二叉树

暴力解法

const int maxN = 35;

long long arrS[maxN];
long long memo[maxN][maxN];
int memoRoot[maxN][maxN];

long long dfs(int left, int right) {
    if (memo[left][right] != 0) {
        return memo[left][right];
    }
    if (left > right) {
        return memo[left][right] = 1;
    }
    if (left == right) {
        memoRoot[left][right] = left;
        return memo[left][right] = arrS[left];
    }
    long long ret = 0;
    for (int i = left; i <= right; i++) {
        long long cur = dfs(left, i - 1) * dfs(i + 1, right) + arrS[i];
        if (cur > ret) {
            memoRoot[left][right] = i;
            ret = cur;
        }
    }
    return memo[left][right] = ret;
}

void traverse(int left, int right) {
    if (left > right) return;
    int root = memoRoot[left][right];
    cout << root << " ";
    traverse(left, root - 1);
    traverse(root + 1, right);
}

int main() {
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> arrS[i];
    long long ans = dfs(1, N);
    cout << ans << endl;
    traverse(1, N);
}

树上背包

树上的背包问题，简单来说就是背包问题与树形 DP 的结合。

选课

现在有 n 门课程，第 i 门课程的学分为 a_i，每门课程有零门或一门先修课，有先修课的课程需要先学完其先修课，才能学习该课程。

一位学生要学习 m 门课程，求其能获得的最多学分数。

思路分析

每门课最多只有一门先修课的特点，与有根树中一个点最多只有一个父亲结点的特点类似。

因此可以想到根据这一性质建树，从而所有课程组成了一个森林的结构。为了方便起见，我们可以新增一门 0 学分的课程(设这个课程的编号为 0)，作为所有无先修课课程的先修课，这样我们就将森林变成了一棵以 0 号课程为根的树。

我们设 f(u,i,j) 表示以 u 号点为根的子树中，已经遍历了 u 号点的前 i 棵子树，选了 j 门课程的最大学分。

转移的过程结合了树形 DP 和 背包 DP 的特点，我们枚举 u 点的每个子结点 v，同时枚举以 v 为根的子树选了几门课程，将子树的结果合并到 u 上。

记点 x 的儿子个数为 sX，以 x 为根的子树大小为 sizeX，可以写出下面的状态转移方程：

$$f(u,i,j)=\max_{v,k \leq j,k \leq sizeX } f(u,i-1,j-k)+f(v,sV,k)$$

注意上面状态转移方程中的几个限制条件，这些限制条件确保了一些无意义的状态不会被访问到。

f 的第二维可以很轻松地用滚动数组的方式省略掉，注意这时需要倒序枚举 j 的值。

题解代码

const int maxN = 305;

vector<int> arr[maxN];
int dp[maxN][maxN];
int arrW[maxN];
int arrV[maxN];
int N, M;

void dfs(int s, int fa) {
    for (int i = M; i >= arrV[s]; i--) dp[s][i] = arrW[s];
    for (auto x : arr[s]) {
        if (x == fa) continue;
        dfs(x, s);
        for (int i = M; i >= arrV[s]; i--)
            for (int j = 0; i - j >= arrV[s]; j++)
                dp[s][i] = max(dp[s][i], dp[s][i - j] + dp[x][j]);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        int k;
        cin >> k >> arrW[i];
        arrV[i] = 1;
        arr[k].emplace_back(i);
    }
    arrV[0] = 0, arrW[0] = 0;
    memset(dp, 0, sizeof(dp));
    dfs(0, 0);
    cout << dp[0][M] << endl;
}

二叉苹果树

const int maxN = 105;

vector<Edge> arr[maxN];
int dim[maxN];
int dp[maxN][maxN];
int siz[maxN];
int N, Q;

void dfs(int s, int fa) {
    for (auto& e : arr[s]) {
        if (e.to == fa) continue;
        dfs(e.to, s);
        siz[s] += 1 + siz[e.to];
        for (int i = min(siz[s], Q); i >= 0; i--) {
            for (int j = min(i - 1, siz[e.to]); j >= 0; j--) {
                dp[s][i] = max(dp[s][i], dp[s][i - j - 1] + dp[e.to][j] + e.val);
            }
        }
    }
}

int main() {
    memset(dp, 0, sizeof(dp));
    memset(siz, 0, sizeof(siz));
    memset(dim, 0, sizeof(dim));
    cin >> N >> Q;
    for (int i = 1; i <= N - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        arr[u].emplace_back(v, w);
        arr[v].emplace_back(u, w);
        dim[u]++, dim[v]++;
    }
    int root = 1;
    for (int i = 1; i <= N; i++)
        if (arr[i].size() == 2) {
            root = i;
            break;
        }
    dfs(root, root);
    cout << dp[root][Q] << endl;
}

换根 DP

树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。

通常需要两次 DFS，第一次 DFS 预处理诸如深度，点权和之类的信息，在第二次 DFS 开始运行换根动态规划。

STA-Station

给定一个 n 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。

思路分析

不妨令 u 为当前结点，v 为当前结点的子结点。首先需要用 s_i 来表示以 i 为根的子树中的结点个数，并且有 s_u=1+sum{s_v}。显然需要一次 DFS 来计算所有的 s_i，这次的 DFS 就是预处理，我们得到了以某个结点为根时其子树中的结点总数。

考虑状态转移，这里就是体现＂换根＂的地方了。令 f_u 为以 u 为根时，所有结点的深度之和。

f_v <-- f_u 可以体现换根，即以 u 为根转移到以 v 为根。显然在换根的转移过程中，以 v 为根或以 u 为根会导致其子树中的结点的深度产生改变。具体表现为：

1. 所有在 v 的子树上的结点深度都减少了一，那么总深度和就减少了 s_v；
2. 所有不在 v 的子树上的结点深度都增加了一，那么总深度和就增加了 n-s_v；

根据这两个条件就可以推出状态转移方程 f_v = f_u - s_v + n - s_v = f_u + n - 2 * s_v。

于是在第二次 DFS 遍历整棵树并状态转移 f_v=f_u + n - 2 * s_v，那么就能求出以每个结点为根时的深度和了。最后只需要遍历一次所有根结点深度和就可以求出答案。

代码实现

const int maxN = 1e6 + 5;

vector<int> arr[maxN];
int siz[maxN];
int dep[maxN];
long long dp[maxN];
int N;

void dfs1(int s, int pre) {
    siz[s] = 1;
    dep[s] = dep[pre] + 1;
    for (auto u : arr[s]) {
        if (u == pre) continue;
        dfs1(u, s);
        siz[s] += siz[u];
    }
}

void dfs2(int s, int pre) {
    for (auto u : arr[s]) {
        if (u == pre) continue;
        dp[u] = dp[s] + N - 2 * siz[u];
        dfs2(u, s);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N;
    for (int i = 1; i < N; i++) {
        int u, v;
        cin >> u >> v;
        arr[u].emplace_back(v);
        arr[v].emplace_back(u);
    }
    dfs1(1, 1);
    dp[1] = 0;
    dep[1] = 0;
    for (int i = 1; i <= N; i++) dp[1] += dep[i];
    dfs2(1, 1);
    long long ans = -1;
    int index = -1;
    for (int i = 1; i <= N; i++) if (dp[i] > ans) ans = dp[i], index = i;
    cout << index << endl;
}

Accumulation Degree

const int inf = 0x3f3f3f3f;
const int maxN = 2e5 + 5;

struct Edge {
    int to;
    int val;
    Edge(int to, int val) : to(to), val(val) {}
};

vector<Edge> arr[maxN];
int dp[maxN][2];

void dfs1(int s, int fa) {
    for (auto& e : arr[s]) {
        if (e.to == fa) continue;
        dfs1(e.to, s);
        if (arr[e.to].size() == 1) dp[s][0] += e.val;
        else dp[s][0] += min(e.val, dp[e.to][0]);
    }
}

void dfs2(int s, int fa) {
    for (auto& e : arr[s]) {
        if (e.to == fa) continue;
        if (arr[s].size() == 1) dp[e.to][1] = e.val;
        else dp[e.to][1] = min(e.val, dp[s][1] + dp[s][0] - min(e.val, dp[e.to][0]));
        dfs2(e.to, s);
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        for (auto& a : arr) a.clear();
        memset(dp, 0, sizeof(dp));
        int N;
        cin >> N;
        for (int i = 1; i <= N - 1; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            arr[x].emplace_back(y, z);
            arr[y].emplace_back(x, z);
        }
        dfs1(1, 1);
        dfs2(1, 1);
        int maxAns = 0;
        for (int i = 1; i <= N; i++) if (dp[i][0] + dp[i][1] > maxAns) maxAns = dp[i][0] + dp[i][1];
        cout << maxAns << endl;
    }
}

Great Cow Gathering G

struct Edge {
    int to;
    int len;
    Edge(int to, int len) : to(to), len(len) {}
};

const int maxN = 1e5 + 5;

long long siz[maxN];
vector<Edge> arr[maxN];
long long dp[maxN];
long long sumSize;

void dfs1(int s, int fa) {
    for (auto& e : arr[s]) {
        if (e.to == fa) continue;
        dfs1(e.to, s);
        siz[s] += siz[e.to];
        dp[s] += dp[e.to] + siz[e.to] * e.len;
    }
}

void dfs2(int s, int fa) {
    for (auto& e : arr[s]) {
        if (e.to == fa) continue;
        dp[e.to] = dp[s] - siz[e.to] * e.len + (sumSize - siz[e.to]) * e.len;
        dfs2(e.to, s);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    memset(dp, 0, sizeof(dp));
    memset(siz, 0, sizeof(siz));
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> siz[i], sumSize += siz[i];
    for (int i = 1; i <= N - 1; i++) {
        int a, b, l;
        cin >> a >> b >> l;
        arr[a].emplace_back(b, l);
        arr[b].emplace_back(a, l);
    }
    dfs1(1, 1);
    dfs2(1, 1);
    long long ans = LLONG_MAX;
    for (int i = 1; i <= N; i++) ans = min(ans, dp[i]);
    cout << ans << endl;
}

Centroids

高难度

潜入行动

const long long p = 1e9 + 7;
const int maxN = 1e5 + 5;

int N, K;
vector<int> arr[maxN];
int dp[maxN][105][2][2];
int siz[maxN];
long long temp[105][2][2];

inline void add(int& x, long long y) {
    y %= p;
    x += y;
    x %= p;
}

void dfs(int s, int fa) {
    siz[s] = dp[s][0][0][0] = dp[s][1][1][0] = 1;
    for (auto u : arr[s]) {
        if (u == fa) continue;
        dfs(u, s);
        for (int i = 0; i <= min(K, siz[s]); i++) {
            temp[i][0][0] = dp[s][i][0][0], dp[s][i][0][0] = 0;
            temp[i][0][1] = dp[s][i][0][1], dp[s][i][0][1] = 0;
            temp[i][1][0] = dp[s][i][1][0], dp[s][i][1][0] = 0;
            temp[i][1][1] = dp[s][i][1][1], dp[s][i][1][1] = 0;
        }
        for (int i = 0; i <= min(siz[s], K); i++) {
            for (int j = 0; j <= min(siz[u], K - i); j++) {
                add(dp[s][i + j][0][0], temp[i][0][0] * dp[u][j][0][1]);
                add(dp[s][i + j][0][1], temp[i][0][0] * (dp[u][j][1][1]));
                add(dp[s][i + j][0][1], temp[i][0][1] * (0LL+dp[u][j][1][1] + dp[u][j][0][1]));
                add(dp[s][i + j][1][0], temp[i][1][0] * (0LL+dp[u][j][0][1] + dp[u][j][0][0]));
                add(dp[s][i + j][1][1], temp[i][1][0] * (0LL+dp[u][j][1][1] + dp[u][j][1][0]));
                add(dp[s][i + j][1][1],temp[i][1][1] *
                    (0LL+dp[u][j][0][0] + dp[u][j][0][1] + dp[u][j][1][0] + dp[u][j][1][1]));
            }
        }
        siz[s] += siz[u];
    }
}

int main() {
    cin >> N >> K;
    for (int i = 1; i <= N - 1; i++) {
        int u, v;
        cin >> u >> v;
        arr[u].emplace_back(v);
        arr[v].emplace_back(u);
    }
    memset(dp, 0, sizeof(dp));
    dfs(1, 1);
    cout << (dp[1][K][0][1] + dp[1][K][1][1]) << endl;
}

苹果树

FAR-FarmCraft