CF1707D Partial Virtual Trees 題解

知識點

樹形 DP，二項式反演，容斥。

分析

容斥

考慮先處理容斥的部分，也就是把集合關系中的 \(\subsetneq\) 轉為 \(\subseteq\)，這里需要用到容斥和反演。

設：

• \(G(k)\) 表示題目要求的答案。
• \(F(k)\) 表示把題目要求集合關系中的 \(\subsetneq\) 轉為 \(\subseteq\) 后的答案。

則有：

實際組合意義：表示 \(i\) 個 \(\subseteq\) 中選出 \(j\) 個轉為 \(\subsetneq\) 的。

那么根據二項式反演，有：

DP

設 \(f_{u,i}\) 表示在 \(S_i\) 中仍有 \(u\) 子樹中的點的方案數，由于題目的特殊性質，要分兩種情況討論，其中第二種容易遺漏。

\(u\) 在 \(S_i\) 中

暴力 \(O(n^3)\)，前綴和優化至 \(O(n^2)\)。

\(u\) 不在 \(S_i\) 中

發現此時在集合 \(son(u)\) 中只能有一個點 \(v_0\) 滿足 \(S_i\) 中有 \(v_0\) 子樹中的點，同時還要考慮 \(i\) 在哪個集合刪除，則有：

暴力 \(O(n^5)\)，前綴和、前后綴積優化至 \(O(n^2)\)。

求 \(F(i)\)

注意最后求答案的時候不能簡單的把 \(f\) 拿來直接用，因為題目限定了 \(S_k = \set{1}\)，所以要再 DP 一下。

暴力 \(O(n^3)\)，前綴和優化至 \(O(n^2)\)。

代碼

//#define Plus_Cat ""
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~i;y=(g)[(i=(g)[i].nxt)>0?i:0].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(2e3+10);

namespace IOEcat {
	//Fast IO...
} using namespace IOEcat;

namespace Modular {
	int Mod;
	int C[N][N];
	ll MOD;

	//Modular...

	int Pow(int a,int b=Mod-2) {
		int res(1);
		for(a%=Mod; b; b>>=1,tomul(a,a))if(b&1)tomul(res,a);
		return res;
	}

	void Init(const int n=N-5) {
		FOR(i,0,n) {
			C[i][0]=1;
			FOR(j,1,i)C[i][j]=add(C[i-1][j-1],C[i-1][j]);
		}
	}
} using namespace Modular;

int n,m;
int F[N];
int f[N][N];
vector<int> g[N];

void dfs(int u,int fa) {
	for(const int &v:g[u])if(v^fa)dfs(v,u);
	int tot(0);
	static int son[N],sum[N];
	for(const int &v:g[u])if(v^fa)son[++tot]=v;
	f[u][0]=1;
	FOR(i,1,m) {
		/*DE("Update");*/
		int cur(1);
		static int pre[N];
		FOR(j,pre[0]=1,tot)pre[j]=mul(pre[j-1],f[son[j]][i-1]);
		DOR(j,tot,1)toadd(sum[son[j]],mul(pre[j-1],cur)),tomul(cur,f[son[j]][i-1]);
		/*DE("Trans");*/
		f[u][i]=1;
		FOR(j,1,tot)tomul(f[u][i],f[son[j]][i]);
		FOR(j,1,tot)toadd(f[u][i],mul(add(f[son[j]][i],Mod-f[son[j]][i-1]),sum[son[j]]));
		toadd(f[u][i],f[u][i-1]);
	}
}

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	I(n,Mod),m=n-1,MOD=((__int128)1<<64)/Mod,Init();
	FOR(i,2,n) {
		int u,v;
		I(u,v),g[u].push_back(v),g[v].push_back(u);
	}
	for(const int &v:g[1])dfs(v,1);
	FOR(i,1,m) {
		F[i]=1;
		for(const int &v:g[1])tomul(F[i],f[v][i-1]);
	}
	FOR(i,1,m) {
		int ans(0);
		FOR(j,1,i)(i^j)&1?toadd(ans,Mod-mul(C[i][j],F[j])):toadd(ans,mul(C[i][j],F[j]));
		O(ans,' ');
	}
	return 0;
}