题解 CF599E 【Sandy and Nuts】
tzc_wk
2020-03-18 11:58:19
> Codeforces 599E
> 题意：有一棵以 $1$ 为根的树。你忘记了它的形态，只记得 $m$ 条边 $(u_i,v_i)$，和 $k$ 条形如 " $a_i$ 和 $b_i$ 的 LCA 为 $c_i$ 的限制。求有多少棵符合要求的树。
> $1 \leq n,m \leq 13$，$1 \leq k \leq 100$
这道题分明有些毒瘤为什么 CF 上难度只有 2100？/yiw
首先看到 $1 \leq n \leq 13$ 就可以想到状压 $dp$。
设 $dp[i][j]$ 表示以 $i$ 为根的子树中，包含了状态集合为 $j$ 的合法的树的个数。$j$ 是一个二进制数，第 $0$ 位（最低位）为 $1$ 表示节点 $1$ 在状态集合中，第 $1$ 位为 $1$ 表示节点 $2$ 在状态集合中，以此类推。
状态转移方程：
- $dp[i][j]=dp[v][k] \times dp[i][j\ \operatorname{xor}\ k]$
其中 $k$ 是 $j$ 的子集。
由于题目对于边和 $lca$ 有限制，所以我们不能想怎么转移就怎么转移（废话），因此我们需要判断合法性：
那么有以下四种情况是不合法的：
1. 对于题目中给定的边，如果满足其中一个端点是 $i$，另一个端点属于状态集合 $k$ 当中，这样的边的个数 $\geq 2$，那么就是不合法的。原因是：$i$ 只能跟集合 $k$ 当中的一个点连边，那个点就是 $v$。因此我们可以枚举 $i,j$ 之后，外层枚举 $k$，再看看有几条边满足条件。如果有一条边满足条件，那么 $v$ 只能等于那条边的另一个端点。否则内层枚举 $v$ 然后转移。
2. 对于题目中给定的边 $(x,y)$，如果 $x \neq i$，$v \neq i$，但是 $u$ 在 $k$ 中，$v$ 不在 $k$ 中，这种条件也是不合法的。因为除了 $i$ 之外，集合 $k$ 中的点不能跟不在集合 $k$ 中的点之间有边。
3. 对于 LCA 的限制 $(a,b,c)$，如果 $c$ 在集合 $k$ 中，但是 $a$ 或 $b$ 不在，那么就不行。这个应该是最好理解的了。
4. 对于 LCA 的限制 $(a,b,c)$，如果 $c=i$，但是 $a,b$ 都在 $k$ 中也不行。因为这样一来 $lca(a,b)$ 一定是 $k$ 中的另外一个点而不是 $i$ 了。
边界 $dp[i+1][2^{i}]=1$
最终的答案就是 $dp[1][2^n-1]$
时间复杂度：枚举子集 $3^n$，内层枚举 $v$ 并判断最坏是 $nk$ 的，所以总复杂度是 $\mathcal O(nk3^n)$
注意事项：
1. 由于 $dp[i][j\ \operatorname{xor}\ k]$，会转移到 $dp[i][j]$，所以需要外层枚举 $j$，内层枚举 $i$
2. 对于同一棵树，我们枚举了一次它的第一棵子树，接着又枚举了它第二棵子树，这样同一棵树会被重复计算。因此我们需要任取一个 $j$ 中与 $i$ 不相等的点 $fst$，并强制它在 $msk$ 中，这样就不会重复计算了。
~~写题解不容易，给个赞呗~~
```cpp
//Coded by tzc_wk
/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a) a.begin(),a.end()
#define giveup(...) return printf(__VA_ARGS__),0;
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,0x3f,sizeof(a))
#define fillsmall(a) memset(a,0xcf,sizeof(a))
#define mask(a) (1ll<<(a))
#define maskx(a,x) ((a)<<(x))
#define _bit(a,x) (((a)>>(x))&1)
#define _sz(a) ((int)(a).size())
#define filei(a) freopen(a,"r",stdin);
#define fileo(a) freopen(a,"w",stdout);
#define fileio(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define put(x) putchar(x)
#define eoln put('\n')
#define space put(' ')
#define y1 y_chenxiaoyan_1
#define y0 y_chenxiaoyan_0
#define int long long
typedef pair<int,int> pii;
inline int read(){
int x=0,neg=1;char c=getchar();
while(!isdigit(c)){
if(c=='-') neg=-1;
c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*neg;
}
inline void print(int x){
if(x<0){
putchar('-');
print(abs(x));
return;
}
if(x<=9) putchar(x+'0');
else{
print(x/10);
putchar(x%10+'0');
}
}
inline int qpow(int x,int e,int _MOD){
int ans=1;
while(e){
if(e&1) ans=ans*x%_MOD;
x=x*x%_MOD;
e>>=1;
}
return ans;
}
int n=read(),m=read(),q=read();
int a[105],b[105],c[105],u[15],v[15];
vector<int> g[15];
int dp[14][8193];
signed main(){
fz(i,1,m) u[i]=read(),v[i]=read(),g[u[i]].push_back(v[i]),g[v[i]].push_back(u[i]);
fz(i,1,q) a[i]=read(),b[i]=read(),c[i]=read();
for(int j=0;j<(1<<n);j++){
for(int i=1;i<=n;i++){
if(__builtin_popcount(j)==1&&_bit(j,i-1)){
dp[i][j]=1;
continue;
}
if(!_bit(j,i-1)) continue;
int msk=j-mask(i-1);
int fst=0;
for(int t=1;t<=n;t++)
if(_bit(msk,t-1)){
fst=t;
break;
}
// cout<<msk<<endl;
// cout<<"fst="<<fst<<endl;
for(int k=msk;k;k=msk&(k-1)){
if(_bit(k,fst-1)){
int l=k^j;
int cnt=0,s=0;
foreach(it,g[i]){
int p=*it;
if(_bit(k,p-1)) s=p,cnt++;
}
if(cnt>=2) continue;
bool flag=1;
for(int p=1;p<=m;p++){
if(u[p]==i||v[p]==i) continue;
if(_bit(k,u[p]-1)&&!_bit(k,v[p]-1)) flag=0;
if(_bit(k,v[p]-1)&&!_bit(k,u[p]-1)) flag=0;
}
for(int r=1;r<=q;r++){
if(_bit(k,c[r]-1)&&(!_bit(k,a[r]-1)||!_bit(k,b[r]-1))) flag=0;
if(c[r]==i&&_bit(k,a[r]-1)&&_bit(k,b[r]-1)) flag=0;
}
if(!flag) continue;
// int tmp=dp[i][j];
if(!cnt){
for(int o=1;o<=n;o++){
if(i!=o&&_bit(k,o-1)) dp[i][j]+=dp[i][l]*dp[o][k];
}
}
else{
dp[i][j]+=dp[i][l]*dp[s][k];
}
// cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j]-tmp<<endl;
}
}
// cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
}
}
cout<<dp[1][(1<<n)-1]<<endl;
return 0;
}
```