【51Nod1673】树有几多愁（虚树+树形DP+状压DP）

多愁（虚树+树形DP+状压DP）"/>

【51Nod1673】树有几多愁（虚树+树形DP+状压DP）

题目描述：

树有几多愁传送门

算法：

虚树+树形DP+状压DP

做法：

首先观察到标号一定是从小到大，从叶子结点往根的方向标。在从叶子结点向上标的过程中，如果遇到的结点的子树中所有叶子结点都已标上号，那么就可以从这个结点继续向上标，否则不能继续向上标。

按照这个方法只要在叶子结点上标了号，其他点再怎么标都不会影响到这个叶子结点了。但所有叶子结点标的先后顺序对结果有很大影响，我们也无法找到一个规律使得按照这个规律标能使结果最优。

题目保证叶子结点个数不超过 20 ，因此可以用状压DP计算所有方案。

用 f[s] 表示选叶子结点状态为 s 时的最优解，那么

f[s]=maxi∈s(f[(sxor(1<<i))]∗now) $$f[s] = \max_{i∈s}(f[(s xor (1<<i))]*now)$$

其中 now 表示标完 s xor (1<< i) 的叶子结点后下一个叶子结点的标号。当然也可以用刷表法。

先建立虚树，再状压+树形DP，时间复杂度 O(2n∗n) $O(2^n*n)$

由于结果较大，long long存不下，只能有 double 存 f 数组，用 g 存对应 f %1e9+7 后的结果。

细节见代码。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;void inline read(int &x){x=0; char c=getchar();while(!(c>='0'&&c<='9')) c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0', c=getchar();
}const int N=100010, P=(int)1e9+7;
int n, mi;
int head[N];struct Edge{int to, next;
}e[N<<1];void inline add(int u, int v){e[++mi] = (Edge){v, head[u]};head[u] = mi;
}const int MAX=(1<<20)+233;
typedef long long LL;
typedef double DB;
int leaf, cnt;  // leaf：叶子结点个数 cnt：虚树中的点的个数  
int siz[N];     // 原树中的子树大小  
int hav[N];     // 虚树中一个点实际代表的点的个数  
int lef[N];     // 叶子结点对应的虚树中的标号  
int sz2[N];     // 虚树中的子树大小  
int sig[N];     // 状压时表示子树中选了的叶子结点个数  
LL g[MAX];      // g[s]:状态为 s 时 %P 后的答案 
DB f[MAX];      // f[s]:状态为 s 时 %p 前的答案  
bool exi[N], islef[N];                      // isleaf[] 记录在原树中此点是否是叶子节点 ，exi[] 记录此点能否被删除  
vector <int> V[N];                          // 用以存虚树  void dfs(int u, int fa){                    // 求出 isleaf[]和 exi[]  int son = 0; siz[u] = 1;for(int p=head[u], v; p; p=e[p].next) if(e[p].to!=fa){son++;v = e[p].to;dfs(v, u);siz[u] += siz[v];}if(!son) islef[u]=true;if(son==1) exi[u] = true;
}void DFS(int u, int fa, int _fa, int len){      // 求出 lef[],hav[] 和虚树 if(!exi[u]){cnt++;hav[cnt] = len;if(_fa) V[_fa].push_back(cnt); if(islef[u]) lef[leaf++]=cnt;len = 0;_fa = cnt;}for(int p=head[u]; p; p=e[p].next) if(e[p].to!=fa) DFS(e[p].to, u, _fa, len+1);
}int main(){scanf("%d",&n);for(int i=1, u, v; i<n; ++i){read(u); read(v);add(u, v); add(v, u);}dfs(1, 0); DFS(1, 0, 0, 0);// 计算 sz2[]  for(int i=0; i<leaf; ++i) sz2[lef[i]]=1;for(int i=cnt; i; --i){for(int j=0, sz=V[i].size(); j<sz; ++j){sz2[i] += sz2[V[i][j]]; }}// 在倒着的dfs序上树形DP，模拟dfs过程 ，结合状压DP  f[0] = g[0] = 1; int total = (1<<leaf)-2; DB tf;for(int i=0, k, j, sz, now, v; i<=total; ++i){fill(sig+0, sig+cnt+5, 0);// 计算 sig[] for(j=0; j<leaf; ++j) if(i&(1<<j)) sig[lef[j]]=1;now = 1;    // now：当标完选的这些叶子结点后，下一个叶子结点要标成几  for(j=cnt; j; --j){for(k=0, sz=V[j].size(); k<sz; ++k){sig[j] += sig[V[j][k]];}if(sig[j]==sz2[j]){now+=hav[j];}}// 状压DP 刷表法 tf = f[i]*now;for(j=0; j<leaf; ++j){if(!(i&(1<<j)) && tf>f[v=(i|(1<<j))]){f[v] = tf;g[v] = g[i]*1ll*now%P;}}}printf("%d\n",g[total+1]);while(1);
}