UVA 1407: Caves —— 树上动态规划

传送门

题目大意:

有一个机器人,它要在一棵有 $n$ 个节点 $n - 1$ 条边的树上行走。已知这个机器人从根节点开始走,最多可以行走 $x$ 距离,并且机器人需要回到根节点。问这个机器人最多可以访问多少个节点。

输入格式:

多组数据。

对于每一组数据,第一行一个整数 $n$ ,代表节点的个数。当 $n = 0$ 时,输入结束。

接下来 $n - 1$ 行,每行三个整数 $i, j, d$ ,代表 $i$ 与 $j$ 间有一条长度为 $d$ 的边。

接下来一行一个整数 $q$ 代表询问的个数。

接下来 $q$ 行,每行一个整数 $x$ ,代表在这次询问中,机器人最多走的距离。

输出格式:

对于每一个询问,输出一行一个整数代表机器人最多可以访问的节点数。格式与样例一致。

测试样例:

Input
3
1 0 5
2 0 3
3
3
10
11
0
Output
Case 1:
2
2
3

分析:

这是一道树上的背包 DP

在定义状态的时候,我们需要迂回一下:本题原本求的是在 $x$ 距离内最多可以访问的节点数,但是我们定义 $dp_{rt,i,0/1}$ 为以 $rt$ 为根节点访问 $i$ 个节点所需要的最小距离,最后一维表示机器人是否返回根节点 $rt$ ,返回为 $1$ ,不返回为 $0$ 。为什么可以这样定义呢?因为从同一个根节点出发,机器人走 $i$ 个节点花费的路径越短,它所剩余的可以走的路径就越长,就更有可能走更多的节点。

现在我们开始考虑状态转移

首先我们必须要预处理出每个节点及其子树的大小,用 $siz_{rt}$ 表示节点 $rt$ 及其子树的大小。

当我们在节点 $rt$ 时,我们肯定要枚举它的子树。当我们枚举到 $rt$ 的子节点 $v$ 及其子树时,我们以根节点及其子树的大小 $siz_{rt}$ 为容量做一个类似 01 背包 的转移。

让我们看一下经典的序列上的 01 背包怎么写:

// 假设容量为 m ,第 i 个物品价值 v[i] ,体积 w[i] 。
for (int i = 1; i <= n; ++i)
  for (int j = m ; j >= w[i]; --j)
    dp[j] = max(dp[j], dp[j - w[i]] + v[i]);


序列上的 01 背包,在枚举到第 $i$ 个物品时,第 $i$ 个物品所占的容量是确定的 $w_i$ 。这一点非常重要。

在树上,这件事情就不同了。假设现在我们正在对节点 $rt$ 进行 01 背包,当我们枚举到它的子节点 $v$ 时, $v$ 及其子树所占的容量并不是确定的,它可以占用 $0 \rightarrow siz_v$ 这个范围内的容量,并且占用不同的容量,在更新的时候得到的 $dp_{rt}$ 的值是不一样的。所以我们需要对它所占用的容量进行枚举,取最优值。

如果浅显一点理解,我们可以这样想:从节点 $rt$ 出发,我们可以走 $i$ 个节点。对于 $rt$ 的一个子节点 $v$ 及其子树,我们从 $i$ 里分 $j$ 个节点给它,剩下的 $(i - j)$ 个节点分给其他子树。但这是一种理解方式,不要忘记了这实际上是一个背包。上面一段写的应该才是严谨的。

转移分三种情况:

  1. 不回 $rt$ :从 $v$ 及其子树回来从其他子树出去。
  2. 不回 $rt$ :从其他子树回来从 $v$ 及其子树出去。
  3. 回 $rt$ :从 $v$ 回 $rt$ ,并从其他子树再次回 $rt$ 。
for (int i = siz[now]; i >= 2; --i) {
  for (int j = 1; j <= min(i, siz[v]); ++j) {
    // w 是 rt -> v 这条边的长度.
    dp[now][i][0] = min(dp[now][i][0], dp[now][i - j][1] + dp[v][j][0] + w);
    dp[now][i][0] = min(dp[now][i][0], dp[now][i - j][0] + dp[v][j][1] + (w << 1));
    dp[now][i][1] = min(dp[now][i][1], dp[now][i - j][1] + dp[v][j][1] + (w << 1));
  }
}


接下来还有两个问题:

第一个问题是:转移的时候加上 $w$ 或者 $2w$ 是怎么回事?让我们看下下面这棵树:


假设我们现在的根节点是 $rt$ ,枚举到的节点子节点是 $v$ 。我们可以看到,我们在用 $v$ 出发走的最短距离更新从 $rt$ 出发走的最短距离时, $rt \rightarrow v$ 这条红色的边实际上被忽略掉了。所以我们如果要从 $v$ 及其子树回到 $rt$ 这个节点,实际上要多走 $2 \times w_{rt \rightarrow v}$ ;而如果我们直接从 $v$ 的子树走了没有回来,秩只需补上 $1 \times w_{rt \rightarrow v}$ 。

第二个问题是:我们如何能保证在我分配 $j$ 个节点给 $v$ 及其子树后,剩下的 $(i - j)$ 个节点一定在其他子树中?

这是因为每一个子节点只会被枚举一次,也就说,每次枚举到的 $v$ 都是一个新的 $v$ ,并且我们的容量是倒序枚举的,所以我们的 $dp_{now, i - j}$ 还并没有被当前枚举的这个 $v$ 的 $dp_{v, i - j}$ 影响过, $dp_{now, i - j}$ 的上一次更新是在枚举到上一个 $v$ 的时候更新的(想想 经典的 01 背包是如何优化掉一维的),所以一定在其他子树里。

最后,稍微想想就能知道,不回来肯定是比回来可以走更多的节点,我们最后答案的更新我们只需要可能最后一维是 $0$ 的 $dp$ 值。

最后推荐一道与这道题非常相似的题:POJ 2486: Apple Tree

代码:

#include <bits/stdc++.h>
using namespace std;

template<class _T> inline void read(_T &_x) {
  int _t, _flag = 0;
  while ((_t = getchar()) != '-' && (_t < '0' || _t > '9'));
  if (_t ==' -')  _t = getchar(), _flag = 1;
  _x = _t - '0';
  while ((_t = getchar()) >= '0' && _t <= '9')
    _x = (_x << 3) + ( _x << 1) + _t - '0';
  if (_flag)  _x = -_x;
}

typedef long long ll;

const int MAX_N = 500 + 10, INF = 0x3f3f3f3f;
struct Edge {
  int v, w, next;
} edge[MAX_N << 1];
int n, q, head[MAX_N], siz[MAX_N], kk = 1, dp[MAX_N][MAX_N][2];

inline void addedge(int u, int v, int w) {
  edge[kk] = (Edge) {v, w, head[u]}, head[u] = kk++;
}

void init() {
  memset(head, 0, sizeof(head));
  kk = 1;
  memset(dp, INF, sizeof(dp));
  memset(siz, 0, sizeof(siz));
}

void dfs(int now, int fa) {
  dp[now][1][0] = dp[now][1][1] = 0;
  siz[now] = 1;
  for (int i = head[now]; i; i = edge[i].next) {
    int v = edge[i].v, w = edge[i].w;
    if (v == fa)  continue;
    dfs(v, now);
    siz[now] += siz[v];
    for (int i = siz[now]; i >= 2; --i) {
      for (int j = 1; j <= min(i, siz[v]); ++j) {
        dp[now][i][0] = min(dp[now][i][0], dp[now][i - j][1] + dp[v][j][0] + w);
        dp[now][i][0] = min(dp[now][i][0], dp[now][i - j][0] + dp[v][j][1] + (w << 1));
        dp[now][i][1] = min(dp[now][i][1], dp[now][i - j][1] + dp[v][j][1] + (w << 1));
      }
    }
  }
}

int main() {
  read(n);
  int kase = 0;
  while (n) {
    init();
    for (int i = 1; i < n; ++i) {
      int a, b, c;
      read(a), read(b), read(c);
      addedge(a, b, c), addedge(b, a, c);
    }
    dfs(0, -1);
    read(q);
    printf("Case %d:\n", ++kase);
    while (q--) {
      int x;
      read(x);
      for (int i = n; i >= 0; --i) {
        if (dp[0][i][0] <= x) {
          printf("%d\n", i);
          break;
        }
      }
    }
    read(n);
  }
}