标签 树形DP 下的文章

url: https://www.luogu.com.cn/problem/P2986

tag:
动态规划，树形DP，USACO，2010

思路：
可以参考 洛谷P3478 POI 2008 STA-Station 都是要求出当某一个节点为根时其他点到这个根的距离，我们可以用一次dfs来求出以任意选的一个节点作为根节点时的答案，比如选择节点1为根节点。然后再利用一次dfs来做节点转移的更新，求当其他节点做根节点时的答案，然后和全局答案做一个更新。最后输出这个答案即可。对于这道题，状态转移方程1是 f[u] += f[j] + w[i] * s[j]; 用f[i] 表示以i为根节点时其他节点到该点的不方便值。状态转移方程2是 d[j] = d[u] - s[j] * w[i] + (cnt - s[j]) * w[i]; 先做初始化让 d[1] = f[1] 然后自上到下更新。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int e[N * 2], ne[N * 2], h[N], w[N * 2], idx;
int n;
LL cnt, ans;
int c[N];
LL f[N];
LL s[N];
LL d[N];
void add(int a, int b, int cc)
{
    e[idx] = b;
    w[idx] = cc;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void dfs1(int u, int fa)
{
    s[u] = c[u];
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfs1(j, u);
        s[u] += s[j];
        f[u] += f[j] + w[i] * s[j];
    }
}
void dfs2(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        d[j] = d[u] - s[j] * w[i] + (cnt - s[j]) * w[i];
        ans = min(ans, d[j]);
        dfs2(j, u);
    }
}
int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++) cin >> c[i], cnt += c[i];
    for (int i = 0; i < n - 1; i ++)
    {
        int a, b, cc;
        cin >> a >> b >> cc;
        add(a, b, cc), add(b, a, cc);
    }
    dfs1(1, 0);
    d[1] = f[1];
    ans = d[1];
    dfs2(1, 0);
    cout << ans << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P2014

tag:
动态规划，树形DP，CTSC/CTS，1997

思路：
和背包比较像，但是有一点区别的是对如果某个节点要选，也需要将其选不同数量节点的情况，分别更新，也就是说不知道每个点的“体积”是多少。因为要选一门课需要将其有依赖的课也选。所以需要从小更新到大。如果将0也算节点，那么整个结构会构成棵树，此时也需要让m ++，表示一共选m + 1个节点。最后输出 f[0][m] 表示选0时不超过m门课，最大的学分。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 400;
int n, m;
int h[N], e[N * 2], ne[N * 2], idx;
int s[N];
int f[N][N];
void add (int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void dfs(int u)
{
    f[u][1] = s[u];
    for (int i = h[u]; ~i; i = ne[i])
        dfs(e[i]);
    for (int i = h[u]; ~i; i = ne[i])
        for (int j = m; j > 0; j --)
            for (int k = 0; k < j; k ++)
                f[u][j] = max(f[u][j], f[u][j - k] + f[e[i]][k]);
}
int main()
{
    cin >> n >> m;
    m ++;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++)
    {
        int a;
        cin >> a >> s[i];
        add(a, i);
    }
    dfs(0);
    cout << f[0][m] << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P4084

tag:
动态规划，树形DP，USACO，2017

思路：
用树形DP来解决。定义数组 f[i][k] 表示以i为根节点且i涂的颜色为k时的方案数。然后根据k的不同分别更新即可。最后答案输出以1为根节点时3个颜色方案数之和（以其他节点为根节点也可以）。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int mod = 1e9 + 7;
int e[N * 2], ne[N * 2], h[N], idx;
int n, k;
int c[N];
LL f[N][4];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a]= idx ++;
}
void dfs(int u, int fa)
{
    if (c[u]) f[u][c[u]] = 1;
    else
    {
        f[u][1] = f[u][2] = f[u][3] = 1;
    }
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
        f[u][1] = f[u][1] * ((f[j][2] + f[j][3]) % mod) % mod;
        f[u][2] = f[u][2] * ((f[j][1] + f[j][3]) % mod) % mod;
        f[u][3] = f[u][3] * ((f[j][1] + f[j][2]) % mod) % mod;
    }
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> k;
    for (int i = 0; i < n - 1; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    for (int i = 0; i < k;  i++)
    {
        int a, b;
        cin >> a >> b;
        c[a] = b;
    }
    dfs(1, 0);
    LL res = 0;
    for (int i = 1; i <= 3; i ++) res = (res + f[1][i]) % mod;
    cout << res << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P2015

tag：
树形DP，动态规划

思路：
用数组f[u, j] 表示以u为根节点使用不超过 j 条边时最大的苹果数量。和背包问题有点不同的是，对于每一个点来说，假如需要用到某一个子节点来更新，则需要与之想连，所以其实是需要预备那个子节点所连的所有边 + 1的边来更新。所以状态转移方程为 f[u, j] = max(f[u, j], f[u, j - k - 1] + f[v,k] + w).在用二维循环更新时，不能让可能用到的边超过子树拥有的边，所以每次dfs之后还需要用s数组来更新以当前节点为根时所拥有的最大的边数。

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 200;
int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;
int n, q;
int s[N];
int f[N][N];
void add(int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}
void dfs(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
        s[u] += s[j] + 1;
        for (int l = min(s[u], q); l; l --)
            for (int k = min(s[j], l - 1); k >= 0; k --)
                f[u][l] = max(f[u][l], f[u][l - k - 1] + f[j][k] + w[i]);
    }
}
int main()
{
    cin >> n >> q;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n - 1; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c),add(b, a, c);
    }
    dfs(1, 0);
    cout << f[1][q] << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P3047

tag:
树形DP, USACO, 2012

思路：
用f[u,m] 表示以u为根节点，向下走出不超过m步时的权值，d[u, m] 表示以u为根节点，向上或向下走不超过m步时的权值。利用两次dfs分别求出f和d，最后输出每个节点作为根节点时的权值和即可。

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int h[N], e[N * 2], ne[N * 2], idx;
int w[N];
int n, k;
LL f[N][25], d[N][25];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void dfs(int u, int fa)
{
    for (int i = 0; i <= k; i ++) f[u][i] = w[u];
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != fa)
        {
            dfs(j, u);
            for (int p = 1; p <= k; p ++)
            {
                f[u][p] += f[j][p - 1];
            }
        }
    }
}
void dfs2(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        d[j][1] += d[u][0];
        for (int p = 2; p <= k; p ++)
        {
            d[j][p] += d[u][p - 1] - f[j][p - 2];
        }
        dfs2(j, u);
    }
}
int main()
{
    cin >> n >> k;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n - 1; i ++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }
    for (int i = 1; i <= n; i ++) cin >> w[i];
    dfs(1, 0);
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= k; j ++)
            d[i][j] = f[i][j];
    dfs2(1, 0);
    for (int i = 1; i <= n; i ++) cout << d[i][k] << endl;
    return 0;
}
  1. 1
  2. 2
  3. 3