「HDU 6566」The Hanged Man

题目大意

给定一棵 \(N\) 个点的无根树，对于所有 \(1 \leq k \leq M\) 求出满足以下条件的点集 \(S\) 个数。

• \(\forall u, v \in S\) ，\(u\) , \(v\) 在树上不相邻
  
• \(\sum_{u \in S} a_u = k\)
  
• \(\sum_{u \in S} b_u\) 在满足上述两个条件的情况下最小
  

\(1 \leq N \leq 50\) ，\(1 \leq M \leq 5000\) 。
初步思考

先考虑把暴力打出来，去优化。
对于此题，容易想到树上背包，定义 \(dp_{u, v, 0/1}\) 表示处理完了 \(u\) 这颗子树，\(\sum a_i = v\) ，\(u\) 不选/选的最小值&方案数。转移时合并背包，时间复杂度 \(O(NM^2)\) ，显然不行。
分析暴力，发现合并背包目前没有更好的方法，那么暴力优化的方向行不通，就要考虑更改状态 or 改变 dp 方法。
进一步探究

对于此题而言，笔者没想出其他可行的 dp 定义，所以从改变 dp 方法入手。
对于树形 dp ，除了常见的从下至上逐层 dp 外，还有按 dfs 序 dp 的方法，我们从这个角度去探究。
仿照暴力，令 \(dp_{u, v, 0/1}\) 表示处理到结点 \(u\) ，\(\sum a_i = v\) ，\(u\) 不选/选的最小值&方案数，发现若我们在从 \(i\) 转移到 \(i + 1\) 时他们代表的结点“跨”树时（即非祖先关系）我们不知道 \(i + 1\) 代表的结点 \(v\) 相连的结点的选择情况，所以需要将 \(v\) 附近的结点选择情况表示出来。
发现直接状压的话是 \(2^N\) 级别的，接受不了，继续挖掘其他性质。手玩发现（真的易证）当 \(i\) 代表结点 \(u\) 到 \(i + 1\) 代表结点 \(v\) “跨”树时 \(v\) 一定是 \(\text{LCA}(u, v)\) 的一个儿子。所以我们状压只需状压从 \(u\) 到根节点的选择情况，然后回溯时将子结点的答案回收，加入本结点的 \(dp\) 数组即可。
但链仍然可以把这种做法卡成 \(O(NM2^N)\) ，所以对于状压仍然要继续优化，由于要状压从 \(u\) 到根节点的链，我们可以从寻找优化链查找的数据结构的角度入手，一个是树链剖分，一个是点分治，此题中两者皆可，笔者就介绍下点分治吧。
做法

首先对于点分治后构成的点分树有一个性质：在原树中相邻的点 \(u\) 和点 \(v\) 在点分树上一定是祖孙关系。因为当 \(u\) - \(v\) 这条边拆开时一定是当以 \(u\) 或 \(v\) 作为其子树根节点，且另一个点非其子树重心时，此时无论另一个点怎么旋，一定在该子树中，也就跟根节点呈祖孙关系。若 \(u\) - \(v\) 没拆开显然呈祖孙关系（父子被包含于祖孙关系中）。

所以我们可以直接在点分树上进行状压&dp（因为对于第一个条件被转化为某一个祖孙关系，在状压的管辖范畴中），在向下递归时将当前结点加入背包，重点在于如何回溯，由于我们是按 dfs 序 dp ，所以所有已做过背包的点的贡献要保留下来。保留在哪里呢？对于 \(dp_{u, v, msk}\) 我们在把 \(u\) 回溯掉后发现只有 \(msk\) 发生了变化，所以 \(dp_{u, v, msk}\) 要加进 \(dp_{fa_u, v, msk \oplus (1  1);        }    if (ok && subn - siz > 1)) return u;    return -1;}//找重心inline void build(int u, int fa) {    subn = getsiz(u);    u = find(u);    adj[fa].push_back(u);    for (auto v : G) {        G[v].erase(lower_bound(G[v].begin(), G[v].end(), u));        build(v, u);    }}//建点分树int stk[N]; //stk表示从根节点到u的第i个结点的编号inline void dfs(int u, int dep) {    if (!dep) {        dp[0][0] = node(0, 1);        dp[1][a] = node(b, 1); //根节点一定要初始化    }    else        for (int msk = 0;msk < 1 > i & 1) && uni[stk]) {                    ok = false;                    break;                }            if (!ok) continue; //选了u后不合法就不选            for (int i = m;i >= a;--i)                if (dp[msk][i - a].c) dp[msk | 1