題解[ABC207F Tree Patrolling]

題目

ABC207F

Sol

這道題非常的好。

題目大意：給你一棵\(n\)個點的樹，在一個點設立守衛能夠覆寫到所有與這個點相連的點，問所有的\(2^n\)種設立守衛的方案中，覆寫到\(k\)個點的方案有多少個。

對于所有\(k\in[1,n]\)，求出答案。

Step1設狀态

設\(f[0][i][j]\)​為在\(i\)​節點的子樹中有\(j\)​​個點被覆寫，且節點\(i\)​未設立守衛且未被覆寫的方案數。

設\(f[1][i][j]\)為在\(i\)節點的子樹中有\(j\)個點被覆寫，且節點\(i\)設立守衛。

設\(f[2][i][j]\)​為在\(i\)​節點的子樹中有\(j\)​個點被覆寫，且節點\(i\)​​未設立守衛且被覆寫的方案數。

Step2邊界條件

\(f[0][i][0]=f[1][st][1]=1\)

放則有一個點，不放就沒有點。

Step3考慮轉移

這一部分不難，代碼很好了解，多想一想就可以寫出來。

有一點點繁瑣。

//p:父親節點子樹内的被看守的點的個數
//q:兒子節點子樹内的被看守的點的個數
(f[0][st][p+q]+=f[0][st][p]*f[0][ed][q]%P)%=P;
(f[0][st][p+q]+=f[0][st][p]*f[2][ed][q]%P)%=P;
(f[1][st][p+q]+=f[1][st][p]*f[1][ed][q]%P)%=P;
(f[1][st][p+q]+=f[1][st][p]*f[2][ed][q]%P)%=P;
(f[2][st][p+q]+=f[2][st][p]*f[1][ed][q]%P)%=P;
(f[2][st][p+q]+=f[2][st][p]*f[0][ed][q]%P)%=P;
(f[2][st][p+q]+=f[2][st][p]*f[2][ed][q]%P)%=P;
(f[2][st][p+q+1]+=f[0][st][p]*f[1][ed][q]%P)%=P;//新增節點st
(f[1][st][p+q+1]+=f[1][st][p]*f[0][ed][q]%P)%=P;//新增節點ed
           

Step4考慮優化

Code

#include<bits/stdc++.h>
#define N (3010)
#define ll long long
#define int long long
using namespace std;
const ll P=1000000007;
int n;
ll sz[N],f[4][N][N];
vector<int>e[N];
inline void dfs(int st,int fa){
	sz[st]=1,f[0][st][0]=f[1][st][1]=1;
	for(int i=0;i<(int)e[st].size();i++){
		int ed=e[st][i];
		if(ed==fa) continue;
		dfs(ed,st);
	}
	for(int i=0;i<(int)e[st].size();i++){
		int ed=e[st][i];
		if(ed==fa) continue;
		for(int p=sz[st];p>=0;p--){
			for(int q=sz[ed];q>=0;q--){
				if(!q){
					(f[1][st][p+q+1]+=f[1][st][p]*f[0][ed][q]%P)%=P;
					continue;
				}
				(f[0][st][p+q]+=f[0][st][p]*f[0][ed][q]%P)%=P;
				(f[0][st][p+q]+=f[0][st][p]*f[2][ed][q]%P)%=P;
				(f[1][st][p+q]+=f[1][st][p]*f[1][ed][q]%P)%=P;
				(f[1][st][p+q]+=f[1][st][p]*f[2][ed][q]%P)%=P;
				(f[2][st][p+q]+=f[2][st][p]*f[1][ed][q]%P)%=P;
				(f[2][st][p+q]+=f[2][st][p]*f[0][ed][q]%P)%=P;
				(f[2][st][p+q]+=f[2][st][p]*f[2][ed][q]%P)%=P;
				(f[2][st][p+q+1]+=f[0][st][p]*f[1][ed][q]%P)%=P;
				(f[1][st][p+q+1]+=f[1][st][p]*f[0][ed][q]%P)%=P;				
			}
			f[1][st][p]=0;
		}
		sz[st]+=sz[ed];
	}
	return;
}
signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v),e[v].push_back(u);
	}
	dfs(1,0);
	for(int i=0;i<=n;i++) printf("%lld\n",(f[0][1][i]+f[1][1][i]+f[2][1][i])%P);
	return 0;
}
           

完結撒花❀