OI - Sandy and Nuts(Codeforces) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - Sandy and Nuts(Codeforces)

发表于 分类于 Valine：

不想码代码的时候就写博客……（每天水写两篇）

# 题面

> Linked Codeforces 599E

点击展开/折叠代码

你曾经有一棵（以 $1$ 号点为根的）树，但你却忘记了它的形态，只记得其中的 $m$ 条边，以及 $q$ 对关系：$a_i$ 号点和 $b_i$ 号点的 LCA 为 $c_i$ 号点。现在你想知道有多少种满足这些条件的树。

# 解析

DP状态比较正常，$f_{u,S}$ 表示当前子树包含 $S$ 中的节点，根为 $u$。

转移则枚举 $S$ 的一个不包含 $u$ 的点集 $T$，但是为了避免算重（这里算重主要是因为 $u$ 的子树之间是无序的），我们需要固定 $S-\{u\}$ 中的编号最小点（当然也可以最大，反正要是一个唯一确定的点）在 $T$ 中。

> Tab. 下面用 $E$ 表示输入给定的边集

这样枚举出的 $T$ 并不一定满足限制，分析两个限制：

  1. 边的限制
    • 若边的一端为 $u$，如果 $|\{v\mid (u,v)\in E\cap v\in T\}|\ge 2$，显然是不可能的，因为一棵子树中只可能有一个点与 $u$ 有边；
    • 若边 $(a,b)$ 的两端都不为 $u$，如果 $a\in T\cap b\not\in T$ 也是不可能的；
  2. LCA 的限制
    • 若 $\operatorname{LCA}(a,b)=u$，则 $a,b$ 不同时出现在 $T$ 中；
    • 若 $\operatorname{LCA}(a,b)\in T$，则必须 $a,b\in T$；

满足以上限制就可以了。

对于边的限制，因为边数是 $O(n)$ 的，可以直接暴力枚举判断。

对于 LCA 的限制，直接枚举我觉得理论上过不了（但是事实说明它还是过了）。我就先处理出 ban[u][S] 和 alw[u]：

  • 当 $u$ 是当前子树的根时，若 ban[u][S]==true 则选取 $S$ 为子树的方案不可行，原因是存在 $a,b\in S$ 且 $\operatorname{LCA}(a,b)=u$；
  • 若存在 $u\in T$ 且 (alw[u]&T)!=alw[u]，则选取 $T$ 为子树的方案是不合法的；因为若 $u\in T$，且 $\operatorname{LCA}(a,b)=u$ ，则必须 $a,b\in T$。

具体看看代码 awa

# 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int Ri(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return r;
}

typedef long long ll;
const int N=13;

ll f[N][1<<N];
int lnk[N],edg[N][2],lg2[1<<N],cnt1[1<<N],alw[N];
bool ban[N][1<<N];
int n,p,q;

bool Check(int T){
	for(int u=0;u<n;u++)
		if((T>>u&1) && (T&alw[u])!=alw[u])
			return true;
	return false;
}
bool CheckEdge(int T,int u){
	for(int i=1;i<=p;i++)
		if(edg[i][0]!=u && edg[i][1]!=u && (T>>edg[i][0]&1)!=(T>>edg[i][1]&1))
			return true;
	return false;
}
ll DP(int u,int S){
	if(cnt1[S]==1) return f[u][S]=1;
	if(~f[u][S]) return f[u][S];
	f[u][S]=0;
	int s=S^(1<<u);
	int x=lg2[s&-s];
	for(int T=s;T;T=(T-1)&s)
		if(T>>x&1){
			if(cnt1[T&lnk[u]]>1) continue;
			//Edge (u,v): no more than one 'v' exsits in one subtree
			if(ban[u][T]) continue;
			//LCA(a,b)=u: a,b cannot appear in the same subtree
			if(Check(T)) continue;
			//LCA(a,b) in T but a or b isn't int T
			if(CheckEdge(T,u)) continue;
			//Edge (a,b): a,b isn't in the same subtree
			if(T&lnk[u]) f[u][S]+=DP(lg2[T&lnk[u]],T)*DP(u,S^T);
			else{
				ll tot=0;
				for(int v=0;v<n;v++)
					if(T>>v&1)
						tot+=DP(v,T);
				ll res=DP(u,S^T);
				f[u][S]+=tot*res;
			}
		}
	return f[u][S];
}
int main(){
	for(int i=0;i<N;i++) lg2[1<<i]=i;
	cnt1[0]=0;
	for(int i=1;i<(1<<N);i++) cnt1[i]=cnt1[i^(i&-i)]+1;
	n=Ri(),p=Ri(),q=Ri();
	for(int i=1;i<=p;i++){
		int u=Ri()-1,v=Ri()-1;
		lnk[u]|=(1<<v),lnk[v]|=(1<<u);
		edg[i][0]=u,edg[i][1]=v;
	}
	for(int i=1;i<=q;i++){
		int a=Ri()-1,b=Ri()-1,c=Ri()-1;
		ban[c][(1<<a)|(1<<b)]=true;
		alw[c]|=(1<<a)|(1<<b);
	}
	for(int i=0;i<n;i++)
		for(int S=0;S<(1<<n);S++)
			for(int j=0;j<n;j++)
				if(S>>j&1)
					ban[i][S]|=ban[i][S^(1<<j)];
	memset(f,-1,sizeof f);
	printf("%lld\n",DP(0,(1<<n)-1));
	return 0;
}

THE END

Thanks for reading!