自动搬运

查看原文

来自洛谷，原作者为

	hhoppitree 成功的秘诀只有一个：加训。故古语有云：日拱一卒，功不唐捐；玉汝于成，溪达四海。

搬运于2025-08-24 21:59:07，当前版本为作者最后更新于2020-12-29 17:24:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述：

求在 $n$ 条有色（$n-1$ 种颜色）边中选 $n-1$ 条 颜色各异 的边使它们构成一颗树的方案数。

题目解法：

前置知识：矩阵树定理

不会不行，有关系。

看到数据范围 $(n\le17)$，果断想到时间复杂度为 $O(F2^n)$，其中 $F$ 为一个关于 $n$ 的小（请感性理解）多项式。

我们看到，求生成树的个数，根据以往知识，肯定要用 $\rm Matrix-Tree$ 定理了。

然后就是这个颜色各异条件特别烦，我们考虑枚举用的边从何处选出。

如果枚举用啥边，时间复杂度是 $\mathcal{O}(\prod m_i n^3)$ 的，还不如暴力。

仔细想想，是因为 重复计数 了，每种情况都枚举了。

根据以往的经验，这道题数据规模又很小，所以用 容斥原理 就行了。

具体而言，就是 $\mathcal{O}(2^n)$ 枚举只取其中几种颜色的边，然后瞎算一下就行了。

记 $f$ 为只考虑某几种颜色时生成树的个数，则可以在 $\mathcal{O}(n^3)$ 的时间复杂度算出一种选择方案所对应的 $f$ 值。

更具体点，就是 $\sum\limits_{\text{取 1 个}}f-\sum\limits_{\text{取 2 个}}f+\sum\limits_{\text{取 3 个}}f-\sum\limits_{\text{取 4 个}}f\cdots\pm\sum\limits_{\text{取 (n-1) 个}}f$。

很显然，这个正负号取决于选的个数的奇偶性。

所以状压一下从 $1$ 枚举到 $2^{n-1}-1$（$\rm dfs$ 也行）顺便统计一下选的个数 $\text{(cnt)}$ 然后容斥就行了。

具体详见代码。

正确代码：

#include<bits/stdc++.h>
#define mp(x,y) make_pair(x,y)
#define mod 1000000007
using namespace std;
int TMP3301;
inline int read(){
    int res=0;
    char c;
    bool zf=0;
    while(((c=getchar())<'0'||c>'9')&&c!= '-');
    if(c=='-')zf=1;
    else res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';
    if(zf)return -res;
    return res;
}
int n;
int dta[21][21];
typedef pair<int,int>P;
vector<P>q[21];
inline void _swap(int x,int y){
	for(register int i=1;i<=n;++i){
		#define swap(x,y) TMP3301=x,x=y,y=TMP3301;
		swap(dta[i][x],dta[i][y]);
		#undef swap
	}
	return;
}
inline int det(){
	int ans=1;
	for(register int i=1;i<=n;++i){
		int p=-1;
		for(register int j=i;j<=n;++j)
			if(dta[i][j]){
				p=j;
				break;
			}
		if(!~p){
			return 0;
		}
		if(p!=i){
			_swap(i,p);
			ans*=-1;
		}
		for(register int j=i+1;j<=n;++j){
			while(dta[j][i]){
				int tmp=dta[j][i]/dta[i][i];
				for(register int k=i;k<=n;++k){
					dta[j][k]-=1ll*tmp*dta[i][k]%mod;
					dta[j][k]=(dta[j][k]%mod+mod)%mod;
				} 
				if(!dta[j][i]){
					break;
				}
				swap(dta[i],dta[j]);
				ans*=-1;
			}
		}
		ans=1ll*ans*dta[i][i]%mod;
	}
	return ans;
}
signed main(){
	n=read()-1;
	for(register int i=1;i<=n;++i){
		int cnt=read();
		while(cnt--){
			int x=read(),y=read();
			q[i].push_back(mp(x,y));
		}
	}
	int ans=0;
	for(register int i=1;i<(1<<n);++i){
		memset(dta,0,sizeof(dta));
		int cnt=0;
		for(register int j=1;j<=n;++j){
			if(!(i&(1<<(j-1)))){
				continue;
			}
			++cnt;
			for(register int k=0;k<q[j].size();++k){
				int x=q[j][k].first,y=q[j][k].second;
				++dta[x][y],++dta[y][x],--dta[x][x],--dta[y][y];
			}
		}
		ans=(ans+((cnt&1)?-1:1)*det())%mod;
	}
	printf("%d\n",(ans%mod+mod)%mod);
	return 0;
} 

如果您没有看懂这篇题解，可以在评论区问我，我将会回答您的问题并且修改这篇题解，使它变得更加通俗易懂，服务更多的 $\text{OIer}$。
如果您看懂了这篇题解，可以点个赞，使这篇题解的排名上升，服务更多的 $\text{OIer}$。