题解 HDU6566 【The Hanged Man】

题意为给定 \(n\) 个点的树，每个节点为一个物品，有体积和价值，选物品必须满足不相邻，即选出一个独立集，求对于 \(\forall i \in [1,m]\)，容量为 \(i\) 时的背包最大价值的方案数。

\(1 \leqslant n \leqslant 50,1 \leqslant m \leqslant 5000\)

暴力就是直接树形背包，\(f_{i,j,0/1}\) 为在 \(i\) 的子树内，容量为 \(j\)，是否选 \(i\) 的方案数，但复杂度为 \(O(nm^2)\)，无法接受。

考虑用 \(dfs\) 序转移来优化，但是发现从 \(dfs\) 序中 \(i\) 转移到 \(i+1\) 时，若 \(i+1\) 对应的节点在 \(i\) 对应的节点的上方时，就可能不知道 \(i+1\) 的父亲选择的情况：

因此还需知道像图中 \(i+1\) 的父亲那样的转折点的选择情况，直接状压一个点到根节点路径上的所有转折点不现实，会被链卡成状态数为 \(O(2^n)\)。

考虑优化状态数，先进行重链剖分，剖分重链时优先遍历轻儿子，因为最后才遍历重儿子，所以一个点到根节点的所有转折点都是重链的链底，那么再进行状压，状态数就为 \(O(2^{\log n})=O(n)\) 了。

设 \(f_{i,S,j}\) 为考虑到 \(dfs\) 序中第 \(i\) 个点，到根的转折点的状态为 \(S\)，容量为 \(j\) 的方案数，转移是 \(O(1)\) 的，复杂度为 \(O(n^2m)\)。

另外一个做法是进行点分治，将每次的分治中心作为转折点来状压，这样状态数也是 \(O(n)\) 的。

#include
#define maxn 210
#define maxm 5010
using namespace std;
typedef long long ll;
template inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
int T,n,m,cnt,now;
int w[maxn],v[maxn],id[maxn];
int siz[maxn],fa[maxn],son[maxn],top[maxn],rev[maxn];
vector t[maxn];
struct edge
{
    int to,nxt;
}e[maxn];
int head[maxn],edge_cnt;
void add(int from,int to)
{
    e[++edge_cnt]={to,head[from]},head[from]=edge_cnt;
}
struct node
{
    int v;
    ll cnt;
}f[2][maxn][maxm],ans[maxm];
node operator +(const node &x,const int &val)
{
    return {x.v+val,x.cnt};
}
void mx(node &x,node y)
{
    if(x.vsiz[son[x]]) son[x]=y;
    }
}
void dfs_chain(int x,int tp)
{
    top[x]=tp,rev[++cnt]=x;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(y==fa[x]||y==son[x]) continue;
        dfs_chain(y,y);
    }
    if(son[x]) dfs_chain(son[x],tp);
}
void clear()
{
    edge_cnt=cnt=0,now=1;
    memset(f,0,sizeof(f));
    memset(ans,0,sizeof(ans));
    memset(son,0,sizeof(son));
    memset(head,0,sizeof(head));
    for(int i=1;i<=n;++i) t[i].clear();
}
void solve(int num)
{
    read(n),read(m),clear();
    for(int i=1;i<=n;++i) read(w[i]),read(v[i]);
    for(int i=1;im) continue;
                mx(f[now][S+1][j+w[rev[i]]],f[now^1][s][j]+v[rev[i]]);
            }
        }
        now^=1;
    }
    for(int s=0;s<(1<