Loading... ## 前言 之前从来没学习过容斥模型，这次这个题作为我的第一个容斥例题学习。 ## 正文 ### 0x00 问题分析 这个问题可以抽象为：给定一个图 $G$ 和一棵树 $Tree$ 要求对于树重新编号，编号是一个 $n$ 的排列，假如树上任意一个父亲编号为 $x$ 任意其儿子的编号为 $y$ 则需要满足在图 $G$ 上有编号为 $x$ 和 $y$ 的连边。 显然有一个状压 dp ，即定义 $dp_{i,x,S}$ 为树上原本标号为 $i$ 的节点被标号为 $x$ ，并且其子树使用了 $S$ 这个集合中的编号。这样直接计算时间复杂度为 $\mathcal{O}\left(n^33^n\right)$ 这样会直接 T 掉考虑优化。 可以发现时间复杂度卡在要考虑 $S$ 这个限制。那么考虑去除 $S$ 一维，直接跑多次 dp 每次限定一个可用于编号的集合 $S$ 。但是这样就没有限制了，并没有办法保证排列了，但是可以保证边的限制合法。但是这样是典型的交容斥，如何理解呢？ 考虑每一个解(不管是否是排列，只需要这个解边的限制合法)作为元素(这个元素是一个集合就是标号的一个子集，即 $S$ )设所有解的集合为 $U$ ，将这个解的 $S$ 中的点作为其属性，我们要求的就是每一个含有这个属性(即编号)的集合 $T$ ，设包含 $i$ 这个编号属性的元素集合为 $T_i$ 。要求的就是所有 $T$ 的交。 ### 0x01 容斥推导 根据容斥公式有： $$ \left|\bigcap_{i=1}^{n}T_i\right|=\left|U\right|-\left|\bigcup_{i=1}^{n}\overline{T_i}\right| $$ 且对于任意集合 $P_i$ 有： $$ \left|\bigcup_{i=1}^{n}P_i\right|=\sum_{m=1}^n\left(-1\right)^{m-1}\sum_{a_i<a_{i+1}}\left|\bigcup_{i=1}^{m}P_{a_i}\right| $$ 即 $$ \left|\bigcup_{i=1}^{n}\overline{T_i}\right|=\sum_{m=1}^n\left(-1\right)^{m-1}\sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^{m}\overline{T_{a_i}}\right| $$ 实际上 $\left|U\right|$ 就是可以用任意标号去标。 而对于 $$ \sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^{m}\overline{T_{a_i}}\right| $$ 相当于在任意选了 $m$ 个点不选的解的数量。发现这个统计是容易的即 $\left|S\right|=n-m$ 时的解的数量。 记 $Cnt_i$ 表示 $\left|S\right|=i$ 时的解的数量，最终得到了： $Ans=Cnt_n-Cnt_{n-1}+Cnt_{n-2}\cdots$ ### 0x02 DP细化 现在可以放心的 DP 了，假设当前钦定可用于标号的点集为 $S$ ，有： $$ Dp_{u,x}=\prod_{y\in S} \sum_{v\in son_u} Dp_{u,y}\times\left[G_{x,y}\right] $$ 其中 $\left[G_{x,y}\right]$ 表示在图 $G$ 上是否有边 $\left(x,y\right)$ 。 DFS DP 即可 ### 0x03 代码实现 AC CODE ```cpp #include<bits/stdc++.h> // #define ONLINE_JUDGE #define INPUT_DATA_TYPE int #define OUTPUT_DATA_TYPE long long INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){register char s[20];register int i=0;if(x<0){x=-x;putchar('-');}if(x==0){putchar('0');return;}while(x){s[i++]=x%10;x/=10;}while(i){putchar(s[--i]+'0');}return;} int n,m; long long f[20][20]; std::vector<int> tree[20],scur; std::bitset<20> graph[20]; void addEdge_tree(int u,int v){tree[u].push_back(v);tree[v].push_back(u);return;} void addEdge_graph(int u,int v){graph[u][v]=graph[v][u]=1;return;} void dfs(int u,int p){ for(auto v:tree[u]) if(v!=p) dfs(v,u); register long long sum; for(auto x:scur){ f[u][x]=1; for(auto v:tree[u]){ if(v==p) continue; sum=0; for(auto y:scur) sum+=f[v][y]*graph[x][y]; f[u][x]*=sum; } } return; } int main(){ #ifndef ONLINE_JUDGE freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); #endif register int i,u,v,s,maxs; register long long ans=0; n=read(); m=read(); for(i=0;i<m;++i){ u=read()-1; v=read()-1; addEdge_graph(u,v); } for(i=1;i<n;++i){ u=read()-1; v=read()-1; addEdge_tree(u,v); } maxs=(1<<n); for(s=0;s<maxs;++s){ scur.clear(); for(i=0;i<n;++i) if((s>>i)&1) scur.push_back(i); dfs(0,0); if((n-scur.size())&1) for(auto id:scur) ans-=f[0][id]; else for(auto id:scur) ans+=f[0][id]; } print(ans); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; } ``` ## 总结 容斥的题首先要想到一个次优的解法，并且想要优化的过程中需要发现其符合容斥的性质才能完成。 最后修改：2023 年 11 月 10 日 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏
1 条评论
我喜欢MuC，大佬能教我怎么追吗？