【2023NOI模拟赛10】鸽子的老家 做题记录

鸽子的老家是一棵 $n$ 个节点的树，节点编号为 $1\sim n$。这是鸽子三年来第一次回老家，鸽子发现树的边受了些损伤。设损伤的边集为 $S$，$P(a,b)$ 表示节点 $a$ 和 $b$ 之间简单路径的边集，鸽子用下面这个函数表示树的受损程度：

$f(S)=\sum\limits_{1\le a_1<a_2<⋯<a_m\le n}\left[\left(\prod\limits_{1\le i,j\le m}|P(a_i,a_j)\cap S|\right)\ge 1.242803739^{(m−1)(m−2)}\right]$

鸽子会告诉你树边 $e_1,e_2,\dots,e_{n−1}$。

你需要依次求出 $f(\{e_1\}),f(\{e_1,e_2\}),\dots,f(\{e_1,e_2,\dots,e_{n−1}\})$，答案对 $1914270647$ 取模。

$1\le n\le 10^5$，$1\le m\le 10$。

诈骗题。

首先考虑依照没坏的边把原图分成多个连通块，这些连通块之间通过坏掉的边形成一棵树。那么选出的 $m$ 个点一定不能在同一个连通块中，否则会有某个 $|P(a_i,a_j)\cap S|$ 为 $0$。

观察到这样的 $(i,j)$ 一共有 $\binom{m}{2}=\frac{m(m-1)}{2}$ 对，由于 $m$ 个点组成的是一个树形结构，最多有 $m-1$ 对点的 $|P(a_i,a_j)\cap S|$ 是 $1$。并且由于 $1.242803739^2<2$，那么有：

$2^{\binom{m}{2}-(m-1)}=2^{\frac{m(m-1)}{2}-(m-1)}=2^{\frac{(m-1)(m-2)}{2}}\ge 2^{\frac{(m-1)(m-2)}{2}}\ge (1.242803739^2)^{\frac{(m-1)(m-2)}{2}}\ge 1.242803739^{(m-1)(m-2)}$

所以只要选出的 $m$ 个点不属于一个连通块就行了，$1.242803739$ 就是诈骗的。

考虑怎么求出 $f(\{e_1\}),f(\{e_1,e_2\}),\dots,f(\{e_1,e_2,\dots,e_{n−1}\})$，显然可以倒过来变成加边，然后用退背包退掉合并前连通块的贡献。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=100005,MS=15;
const long long p=1914270647;

int n,m;
int xs[S],ys[S];
int fa[S],siz[S];
long long dp[MS],pd[MS];
long long ans[S];

int fnd(int u)
{
	return fa[u]==u?u:fa[u]=fnd(fa[u]);
}

inline void meg(int x,int y)
{
	int rx=fnd(x),ry=fnd(y);
	fa[rx]=ry;
	siz[ry]+=siz[rx];
}

inline void add(long long &x,long long y)
{
	x+=y;
	if(x>=p) x-=p;
}

int main()
{
	freopen("hometown.in","r",stdin);
	freopen("hometown.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n-1;i++) scanf("%d%d",&xs[i],&ys[i]);
	for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
	dp[0]=1;
	for(int i=1;i<=n;i++) for(int j=m;j>=1;j--) add(dp[j],dp[j-1]);
	for(int i=n-1;i>=1;i--)
	{
		ans[i]=dp[m];
		int x=xs[i],y=ys[i];
		int sx=siz[fnd(x)],sy=siz[fnd(y)];
		for(int j=0;j<=m;j++)
		{
			pd[j]=dp[j];
			if(j>=1) add(pd[j],p-pd[j-1]*sx%p);
		}
		for(int j=0;j<=m;j++) dp[j]=pd[j];
		for(int j=0;j<=m;j++)
		{
			pd[j]=dp[j];
			if(j>=1) add(pd[j],p-pd[j-1]*sy%p);
		}
		for(int j=0;j<=m;j++) dp[j]=pd[j];
		for(int j=m;j>=1;j--) add(dp[j],dp[j-1]*(sx+sy)%p);
		meg(x,y);
	}
	for(int i=1;i<=n-1;i++) printf("%lld\n",ans[i]);
	return 0;
}