树形DP

树形DP

0x00 树形DP的定义

树形DP就是在树上的DP。（废话）

树形DP利用了一定的DP的思想。

0x10 例题

0x11 例题 1

给定一棵树，求这颗树每一个点的子树大小。$1\le 点数\le 10^6$。

最基本的树形DP。

• 叶子节点的子树大小是 $1$。
• 递归，在回溯的时候，非叶子节点的子树大小是他所有儿子的子树大小的和加上 $1$。

void dfs(int u, int fa)
{
  sum[u] = 1;
  for (auto &i : z[u])
  {
    if (i == fa)
      continue ;
    dfs(i, u);
    sum[u] += sum[i];
  }
}
1
2
3
4
5
6
7
8
9
10
11

0x12 例题2 没有上司的舞会 P1352

定义 $f[i][0/1]$ 代表 $i$ 为根的子树，没有选/选了。

然后进行树形DP。

$$f[i][0]=\sum _{j是i的儿子}\max (f[j][0],f[j][1])$$

$$f[i][1]=\sum _{j是i的儿子}f[j][0]$$

答案就是 $\max (f[i][0],f[i][1]),i\in [1,n]$。

#include 

using namespace std;

const int N = 6010;
int f[N][2], v[N];
bool flag[N];
vector <int> z[N];

void dfs(int u, int fa = -1)
{
  f[u][0] = 0, f[u][1] = v[u];
  for (auto &i : z[u])
  {
    if (i == fa)
      continue ;
    dfs(i, u);
    f[u][0] += max(f[i][0], f[i][1]);
    f[u][1] += f[i][0];
  }
}

signed main()
{
  int n;
  cin >> n;
  for (int i = 1; i <= n; i ++)
    cin >> v[i];
  for (int i = 1; i < n; i ++)
  {
    int a, b;
    cin >> a >> b;
    z[a].push_back(b);
    z[b].push_back(a);
    flag[a] = true;
  }
  int root = 1;
  for (; root <= n; root ++)
    if (!flag[root])
      break;
  dfs(root);
  int mx = 0;
  for (int i = 1; i <= n; i ++)
    mx = max(mx, max(f[i][0], f[i][1]));
  cout << mx << '\n';
  return 0;
}

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