跃迁引擎启动

HDu6656 The Hanged Man 题解

发表于 更新于 分类于 阅读次数：

题面

给定一棵 $n$ 个点的树，每个点有权值 $a_i$ 和 $b_i$，定义 $f(x)$ 表示满足 $a_i$ 之和等于 $x$ 的所有树上独立集中，$b_i$ 权值和最大的方案数。你需要求出 $f(1), f(2), \dots, f(m)$ 的值。

其中 $1 \le n \le 50, 1 \le m \le 5000$。

分析

显然有一个 $f(i,j,0/1)$ 的 $O(nm^2)$ 的树形背包做法，无法通过。

我们考虑在 dfs 序上进行 DP，注意到一个点能否被选择只和它到根的链上的状态有关，于是我们按照 dfs 序枚举时，同时记录每种链上的状态的信息。但是，这样仍然难易通过，因为可能会存在一个长链。

对于树进行轻重链剖分，不同于传统的剖分后标号方式，我们首先标记轻子树的 dfs 序，然后标记重子树。对于这样的标号方式，当我们考虑 dfs 序上的第 $i$ 个转移到第 $i+1$ 个时，要么是沿着向下的边走了一步，要么是跳到该重链链头的父亲后，往下走了一步，或者重复往上跳链头的父亲，然后往下走一步。那么，以这样的方式标号后，每个点到根的路径上有用的点，就只有每条重链的底部节点（每条重链链头的父节点）。于是，我们对这些关键点进行状压。

标号和 dfs

转移时，需要考虑第 $i$ 个点上的关键点集合和第 $i+1$ 个点上的关键点集合的重复部分，得到具体的转移状态，分成使用节点 $i+1$ 和不使用节点 $i+1$ 两种进行转移。

代码

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
#include <cstdio>
#include <cassert>
#include <vector>
using namespace std;
using ll = long long;
const int maxn = 100 + 5;
const int maxm = 5000 + 5;

struct Node {
  int val;
  ll cnt;

  void operator += (const Node& rhs) {
    if (val == rhs.val) {
      cnt += rhs.cnt;
    } else if (val < rhs.val) {
      val = rhs.val;
      cnt = rhs.cnt;
    }
  }
} f[maxn][maxm], g[maxn][maxm];

int n, m, a[maxn], b[maxn];
int fa[maxn], dfn[maxn], rdfn[maxn];
vector<int> edge[maxn], chain[maxn];

namespace hld {
  int tot, siz[maxn], dep[maxn], son[maxn], top[maxn];
  void dfs(int u, int f) {
    fa[u] = f; siz[u] = 1; son[u] = 0;
    int m = -1;
    for (auto& v: edge[u]) {
      if (v == f) continue;
      dep[v] = dep[u] + 1;
      dfs(v, u);
      siz[u] += siz[v];
      if (siz[v] > m) son[u] = v, m = siz[v];
    }
  }
  void dfs(int u, int f, int tp) {
    dfn[u] = ++tot;
    rdfn[tot] = u;
    top[u] = tp;
    for (auto& v: edge[u]) {
      if (v == f || v == son[u]) continue;
      dfs(v, u, v);
    }
    if (son[u]) {
      dfs(son[u], u, tp);
    }
  }
  void build() {
    tot = 0;
    dep[1] = 0;
    dfs(1, 0);
    dfs(1, 0, 1);
    for (int i = 1; i <= n; i++) {
      int x = i;
      while (x) {
        chain[i].push_back(x);
        x = fa[top[x]];
      }
    }
  }
}

int main() {
  int T, kase = 0; scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
      edge[i].clear();
      chain[i].clear();
    }
    for (int i = 1; i <= n; i++) {
      scanf("%d%d", a + i, b + i);
    }
    for (int i = 2, u, v; i <= n; i++) {
      scanf("%d%d", &u, &v);
      edge[u].push_back(v);
      edge[v].push_back(u);
    }

    hld::build();
    for (int s = 0; s < 2; s++) {
      for (int j = 0; j <= m; j++) {
        f[s][j] = { 0, 0 };
      }
    }
    f[0][0] = { 0, 1 };
    f[1][a[rdfn[1]]] = { b[rdfn[1]], 1 };
    for (int i = 2; i <= n; i++, swap(f, g)) {
      int u = rdfn[i];
      int ss = 1 << chain[u].size();
      for (int s = 0; s < ss; s++) {
        for (int j = 0; j <= m; j++) {
          g[s][j] = { 0, 0 };
        }
      }
      int pre = rdfn[i - 1], fa = -1;
      int ps = 1 << chain[pre].size();
      vector<int> mp(chain[pre].size(), -1);
      for (int i = 0; i < chain[pre].size(); i++) {
        int x = chain[pre][i];
        if (x == ::fa[u]) fa = i;
        for (int j = 0; j < chain[u].size(); j++) {
          if (chain[u][j] == x) {
            mp[i] = j;
            break;
          }
        }
      }
      assert(fa != -1);
      for (int s = 0; s < ps; s++) {
        int nxt = 0;
        for (int i = 0; i < chain[pre].size(); i++) {
          if (s >> i & 1) {
            if (mp[i] != -1) {
              nxt |= 1 << mp[i];
            }
          }
        }
        for (int j = 0; j <= m; j++) {
          if (f[s][j].cnt == 0) continue;
          g[nxt][j] += f[s][j];
          if ((s >> fa & 1) == 0 && j + a[u] <= m) {
            g[nxt | 1][j + a[u]] += Node { f[s][j].val + b[u], f[s][j].cnt };
          }
        }
      }
    }

    printf("Case %d:\n", ++kase);
    for (int i = 1; i <= m; i++) {
      Node ans { 0, 0 };
      for (int s = 0; s < (1 << chain[rdfn[n]].size()); s++) {
        ans += f[s][i];
      }
      printf("%lld%c", ans.cnt, " \n"[i == m]);
    }
  }
  return 0;
}